We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Index of a Valid Split

Number: 2888

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a 0-indexed integer array nums that has exactly one dominant element (an element that appears more than half of the time in the array), find the minimum index i (with 0 <= i < n - 1) to split nums into two non-empty subarrays such that both subarrays have the same dominant element as nums. If no valid split exists, return -1.

Key Insights

  • The entire array has exactly one dominant element. This element must be the dominant one in both subarrays if a valid split exists.
  • Start by identifying the dominant element by counting its total occurrences in nums.
  • While iterating through the array indices, maintain a running count (prefix sum) of the dominant element.
  • For a split at index i to be valid:
    • The dominant element should appear more than (i + 1) / 2 times in the left subarray.
    • The remaining occurrences in the right subarray must be more than (n - i - 1) / 2.
  • The problem can be solved in one pass through the array after counting the total occurrences, resulting in an overall O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (excluding input space)

Solution

The solution begins by finding the dominant element in the entire nums array by counting its occurrences. During a single traversal (from index 0 to n-2), we maintain a prefix count of the dominant element. At each possible split index i, we check if the count in the left subarray is more than half the length of the left subarray and if the remaining count in the right subarray is more than half the length of the right subarray. The first valid index i is returned. If no valid split is found, return -1.

Code Solutions

# Python Solution
class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        n = len(nums)
        # First, find the dominant element by counting occurrences.
        from collections import Counter
        count = Counter(nums)
        dominant, totalCount = max(count.items(), key=lambda x: x[1])
        
        # Running count of the dominant element in the left subarray.
        leftCount = 0
        for i in range(n - 1):
            if nums[i] == dominant:
                leftCount += 1
            
            # Check dominant condition for left: more than half of the subarray
            if leftCount * 2 > (i + 1):
                # Right subarray length is n - i - 1 and occurrences are totalCount - leftCount.
                if (totalCount - leftCount) * 2 > (n - i - 1):
                    return i
        return -1
← Back to All Questions