Splits That Share a Leader
MediumArrays & Hashing
Problem
The leader of a sequence is a value that occupies more than half of its positions; not every sequence has one.
For the array nums, count the split points s (0 ≤ s < n - 1) such that the left part nums[0..s] and the right part nums[s+1..n-1] both have a leader and it is the same value. Use O(1) extra space.
Example 1
- Input:
- nums = [4, 3, 4, 4, 4, 2]
- Output:
- 2
s = 0: [4] | [3, 4, 4, 4, 2], leader 4 on both sides. s = 2: [4, 3, 4] | [4, 4, 2]. No other split works.
Example 2
- Input:
- nums = [1, 2, 3]
- Output:
- 0
No part longer than one element has a leader that matches.
Example 3
- Input:
- nums = [7, 7, 7, 7]
- Output:
- 3
Constraints
- 1 ≤ nums.length ≤ 10^5
- -10^9 ≤ nums[i] ≤ 10^9
Hint
Show the first hint
If both parts have leader v, how often does v appear in the whole array?
Walkthrough
How to approach it
01Clarify before coding
- Must the leader be a strict majority of each part? Yes, more than half of that part's length.
- Must both parts be non-empty? Yes, so s ranges over 0..n-2.
- What if the array has no leader at all? Then no split works; return 0.
02Brute force
For every split, find the leader of each side by counting.
Cost: O(n²) time even with incremental counting per split, and a hash map per side.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.