🔗 Complete the Marathon

A huge number of runners took part in a marathon. Every runner except a single one finished the race.

Given an array participant containing the names of the runners who took part, and an array completion containing the names of the runners who finished, write a solution function that returns the name of the runner who did not finish.

• The number of runners who took part in the marathon is between 1 and 100,000.
• The length of completion is exactly 1 less than the length of participant.
• Each participant's name consists of 1 to 20 lowercase alphabet characters.
• There may be participants with the same name.

Example #1

"leo" is on the participant list but not on the completion list, so "leo" did not finish.

Example #2

"vinko" is on the participant list but not on the completion list, so "vinko" did not finish.

Example #3

There are two people named "mislav" on the participant list, but only one on the completion list, so one of them did not finish.

The problem asks us to find the runner who did not finish the marathon. The completion list completion is always exactly one element shorter than the participant list participant. In other words, there is guaranteed to be exactly one runner who did not finish.

Also, since there may be duplicate names, a structure that stores unique values, like HashSet, isn't suitable.

Since there is exactly one runner who did not finish, counting each finisher's name and its occurrence count in a HashMap will let us handle both finishers and duplicate names.

JAVA
HashMap<String, Integer> map = new HashMap<>();

for (String name : participant)
{
	map.put(name, map.getOrDefault(name, 0) + 1);
}

for (String name : completion)
{
	map.put(name, map.get(name) - 1);
}

Declare a HashMap with String keys and Integer values. Iterate over the participant elements, using each participant's name as the key and incrementing its value by 1.

By default each participant will have a value of 1, but if there's a duplicate name like nikola, then nikola's value in map becomes 2.

Then iterate over the completion elements, using each finisher's name as the key and decrementing its value by 1. In this process, the runner who did not finish will not have their value decremented, so they end up with a value of 1.

Iterate over map to find the key with a value of 1 and return it.

JAVA
import java.util.HashMap;

/**
 * Complete the Marathon class
 *
 * @author RWB
 * @since 2021.12.10 Fri 21:13:57
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param participant: [String[]] participating runners
	 * @param completion: [String[]] runners who finished
	 *
	 * @return [String] name of the runner who did not finish
	 */
	public String solution(String[] participant, String[] completion)
	{
		String answer = "";
		
		HashMap<String, Integer> map = new HashMap<>();
		
		for (String name : participant)
		{
			map.put(name, map.getOrDefault(name, 0) + 1);
		}
		
		for (String name : completion)
		{
			map.put(name, map.get(name) - 1);
		}
		
		for (String key : map.keySet())
		{
			// If the value is at least 1
			if (map.get(key) > 0)
			{
				answer = key;
				break;
			}
		}
		
		return answer;
	}
}