MediumNo. 2780
Minimum Index of a Valid Split — LeetCode 2780 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
An element x of an integer array arr of length m is dominant if more than half the elements of arr have a value of x. You are given a 0-indexed integer array nums of length n with one dominant element.
Example
- Input
- nums = [1,2,2,2]
- Output
- 2
- Explanation
- We can split the array at index 2 to obtain arrays [1,2,2] and [2].
Python solution
class Solution:
def minimumIndex(self, nums: List[int]) -> int:
x, cnt = Counter(nums).most_common(1)[0]
cur = 0
for i, v in enumerate(nums, 1):
if v == x:
cur += 1
if cur * 2 > i and (cnt - cur) * 2 > len(nums) - i:
return i - 1
return -1Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2780. Minimum Index of a Valid Split is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2784 | Check if Array is Good | Easy |
| 0049 | Group Anagrams | Medium |
| 0169 | Majority Element | Easy |
| 0217 | Contains Duplicate | Easy |
| 0229 | Majority Element II | Medium |
| 0268 | Missing Number | Easy |
Frequently asked questions
- How hard is LeetCode 2780. Minimum Index of a Valid Split?
LeetCode 2780. Minimum Index of a Valid Split is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2780. Minimum Index of a Valid Split?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2780. Minimum Index of a Valid Split?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2780. Minimum Index of a Valid Split cover?
LeetCode 2780. Minimum Index of a Valid Split is tagged Array, Hash Table and Sorting on LeetCode.