2780. Minimum Index of a Valid Split

Intuition

The problem requires us to find the minimum index at which we can split an integer array such that both resulting subarrays have the same dominant element. An element is considered dominant if it appears more than half the time in the array. This means that for a valid split, both subarrays must contain the same dominant element.

Approach

To solve this problem, we can use the Boyer-Moore Voting Algorithm to identify the dominant element in the array. Once we have the dominant element, we can count its occurrences and check for valid splits. A valid split occurs when both subarrays contain the dominant element more than half the time.

1. Identify the Dominant Element:

   • Use the Boyer-Moore Voting Algorithm to find the element that appears most frequently
   • Keep track of a potential majority element and its count

2. Count Occurrences:

   • Count how many times this dominant element appears in the entire array
   • This is needed to verify it’s truly the majority element

3. Check for Valid Splits:

   • Iterate through the array and check if the dominant element appears more than half the time in both subarrays
   • For each potential split point, verify the majority condition in both resulting subarrays
   • Return the first valid split index

4. Return Result:

   • If no valid split is found, return -1

Code

function minimumIndex(nums: number[]): number {
    let majorityNum = nums[0]; // Initialize the majority number
    let currentCount = 0; // Counter for the majority number
    let majorityCount = 0; // Total count of the majority number
    let n = nums.length; // Length of the array
 
    // Boyer-Moore Voting Algorithm to find the majority element
    for (let num of nums) {
        if (num === majorityNum) {
            currentCount++; // Increment count if the number matches
        } else {
            currentCount--; // Decrement count if it doesn't match
        }
 
        // If count reaches zero, update the majority number
        if (currentCount === 0) {
            currentCount = 1; // Reset count
            majorityNum = num; // Update majority number
        }
    }
 
    // Count the occurrences of the majority element
    for (let num of nums) {
        if (num === majorityNum) majorityCount++; // Increment if it matches
    }
 
    currentCount = 0; // Reset current count for split checking
    // Check for valid splits
    for (let i = 0; i < n - 1; i++) {
        if (nums[i] === majorityNum) currentCount++; // Count in the first subarray
        let remainingCount = majorityCount - currentCount; // Count in the second subarray
        // Check if both subarrays have the majority element more than half the time
        if ((currentCount * 2 > i + 1) && (remainingCount * 2 > n - i - 1)) return i; // Valid split found
    }
 
    return -1; // No valid split found
}

Time Complexity

• Time Complexity: O(n)

  • n: length of the array
  • Finding the majority element takes O(n) time with the Boyer-Moore algorithm
  • Counting occurrences and checking for valid splits each take O(n) time

• Space Complexity: O(1)

  • The algorithm uses a constant amount of extra space regardless of the input size

This approach efficiently finds the minimum index of a valid split while ensuring that both resulting subarrays contain the same dominant element.