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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Index of a Valid Split

Difficulty: Medium

Problem Description

Given an integer array nums of length n with one dominant element, determine the minimum index i at which you can split the array into two subarrays such that both subarrays contain the same dominant element. A dominant element is defined as an element that appears more than half the time in the array.

Key Insights

  • A valid split requires both subarrays to have the same dominant element.
  • The dominant element must appear more than half the time in both subarrays.
  • The problem can be solved by tracking the frequency of the dominant element as we iterate through the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a single pass through the array to count occurrences of the dominant element and determine potential split points. The strategy is to maintain a count of the dominant element in both the left and right subarrays as we iterate through the array.

  1. Identify the dominant element and its total count in the array.
  2. Iterate through the array, maintaining a count of the dominant element in the left subarray.
  3. For each index i, check if the left subarray has more than half of its elements as the dominant element and if the right subarray also meets the same condition.
  4. If both conditions are satisfied, return the index i.
  5. If no valid split exists, return -1.

Code Solutions

def min_valid_split(nums):
    from collections import Counter

    # Count occurrences of each element
    count = Counter(nums)
    dominant_element = max(count, key=count.get)
    total_count = count[dominant_element]
    
    left_count = 0
    n = len(nums)

    # Iterate through nums to find the valid split index
    for i in range(n - 1):
        if nums[i] == dominant_element:
            left_count += 1
        
        left_size = i + 1
        right_size = n - left_size

        # Check if left and right subarrays have the dominant element
        if left_count > left_size // 2 and (total_count - left_count) > right_size // 2:
            return i

    return -1
← Back to All Questions