2780. Minimum-Index-Of-A-Valid-Split

The question gives us a 0-indexed array num of length n with ONE dominant element.

This means that for the brute force approach, we can first iterate through all the elements of the array and find this dominant element (effectively, the element that appears the most times).

Once we find the dominant element, we can go through all of the indexes and calculate in O(1) time whether or not the dominant element is still the dominant element in the two resulting subarrays that we get when we split by that index. This can be done with some calculations involving the length of the array, the number of dominant element in the left array and index.

Calculations:

• length of array: n
• dominant element: x
• number of dominant element in the whole arr: num_x
• length of left arr: i + 1
• length of righ arr: n - i - 1
• number of x in the left arr: left_x

Given these variables and an index i, we can check:

• if left_x * 2 > i + 1, x is dominant in the left sub array
• if (num_x - left_x) * 2 > n - i - 1, x is dominant in the right sub array Therefore, we just need to return the first i where both of these conditions are True.

class Solution(object):
    def minimumIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        count_x = {}
        x = nums[0]

        for k in nums:
            count_x[k] = count_x.get(k, 0) + 1
            if count_x[k] > count_x[x]:
                x = k

        num_x = count_x[x]

        left_x = 0
        for i in range(n - 1):
            if nums[i] == x:
                left_x += 1

            left_dominant = left_x * 2 > i + 1
            right_dominant = (num_x - left_x) * 2 > n - i - 1

            if left_dominant and right_dominant:
                return i

        return -1

Time Complexity: O(n)

Space Complexity: O(n)

Side Note:

I knew about the Boyer-Moore Majority Voting Algorithm existed in order to find the largest element in O(1) space. However, I completely forgot how to implement it (I know classic L), therefore, I compromised with this solution (thank god it passed). At least, it made me revisit the Boyer-Moore algorithm again.