Field Trip Vote
Your class is choosing a field trip. Every student writes the code of one destination on a slip: 4 for the aquarium, 9 for the science museum, 17 for the climbing wall, and so on. The slips go into a box and are read out one by one.
The school rule says a trip only goes ahead if one destination gets more than half of all votes. This time the teacher already knows it happened. You just need to say which destination won.
Your task
Write winningTrip(votes). Return the destination code that appears more than votes.length / 2 times.
Such a destination always exists, so there is always exactly one correct answer.
winningTrip(votes: int[]) → int
Examples
votes = [9, 4, 9, 17, 9]
9
Five votes, so the winner needs at least 3. The museum, code 9, got 3. The aquarium and the climbing wall got one each.
votes = [4, 4, 17, 17, 17, 17, 4]
17
Seven votes, so the winner needs at least 4. Code 17 got exactly 4. The first vote read out was a 4, but that does not make it the winner.
Constraints
- 1 ≤ votes.length ≤ 50,000
- 1 ≤ votes[i] ≤ 1,000,000
- One value appears more than votes.length / 2 times.
Start with brute force
For each vote, scan the whole box and count how many slips match it. Return the first code whose count is more than half.
Every vote can trigger a full scan, so this is O(n²). With 50,000 votes that is up to 2.5 billion comparisons. Sorting also works, because the winner must fill the middle position, but it costs O(n log n) and reorders the slips.
Hints
0 of 4 shown- Hint 1
With 7 votes, how many does the winner need? Once some destination reaches that number, could anything still beat it?
- Hint 2
You need to know how many votes each destination has so far. A tally sheet with one line per destination is enough.
- Hint 3
Which structure keeps a count per destination code, with no idea in advance which codes will show up?
- Hint 4
Walk the votes once with a map from code to count. After adding each vote, check whether that count is now more than
votes.length / 2. If it is, return that code right away.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Read the slips once and keep a running tally per destination, like marks on a whiteboard. The moment one destination passes half the class, it has won.
Trace [9, 4, 9, 17, 9]. Half of 5 is 2.5, so the winner needs 3.
- 9: tally 9 → 1.
- 4: tally 4 → 1.
- 9: tally 9 → 2. Not yet more than 2.5.
- 17: tally 17 → 1.
- 9: tally 9 → 3, which is more than 2.5. Return 9.
Use the total number of votes in the check, not the number read so far. After the first slip, that one destination has 100% of the votes read, but it has not won anything.
There is also a neat O(1) memory trick: keep one candidate and a counter, add 1 when a vote matches the candidate, subtract 1 when it does not, and switch candidate when the counter hits 0. Each losing vote cancels one winning vote, and the winner has more votes than everyone else combined, so it is the one left standing.
function winningTrip(votes) {
const count = new Map(); // destination -> votes so far
for (const v of votes) {
const c = (count.get(v) || 0) + 1;
count.set(v, c);
if (c > votes.length / 2) return v; // nobody can catch up now
}
return -1; // never reached: a winner always exists
}def winning_trip(votes):
count = {} # destination -> votes so far
for v in votes:
count[v] = count.get(v, 0) + 1
if count[v] > len(votes) / 2: # nobody can catch up now
return v
return -1 # never reached: a winner always existsRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.