Minimum Index of a Valid Split — LeetCode 2780 Python Solution

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 -1

Complexity

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