Ctrl K

Cut With the Same Leader

Medium
Call a value the **leader** of a list if it fills strictly more than half of the positions. Not every list has a leader, but the given list votes does. You can cut the list after index i into two non-empty parts, votes[0..i] and votes[i+1..]. A cut is good if both parts have a leader and it is the same value. Return the smallest index i that gives a good cut, or -1 if no cut is good.
Example 1
votes=[5, 4, 4, 5, 4, 4] → 2

Cutting after index 2 gives [5, 4, 4] and [5, 4, 4], and 4 takes 2 of 3 places in both. Cuts after indices 0 and 1 fail: [5] is led by 5 and [5, 4] has no leader at all.

Example 2
votes=[2, 2, 2, 3, 3] → -1

Whatever the cut, 2 never takes more than half of the right part, so no cut works.

Example 3
votes=[9] → -1

A single element cannot be cut into two non-empty parts.

Constraints
  • 1 ≤ len(votes) ≤ 10⁵
  • 1 ≤ votes[i] ≤ 10⁹
  • votes has a leader
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsAnagram Buckets MediumMore Than a Third of the Votes MediumMost Common Values MediumA Subsequence of One Word Only MediumPairs With a Fixed Gap Medium
loading Python…
Input
votes=[5, 4, 4, 5, 4, 4]
Expected
2

Run checks the first 3 tests in your browser. Submit checks all 11 tests on the server, hidden ones included.