LeetCode 2780 - Minimum Index of a Valid Split

The problem asks us to find a minimum index at which a given integer array nums can be split into two non-empty contiguous subarrays, such that both subarrays share the same dominant element as the original array.

leetcodemediumarrayhash-tablesorting

LeetCode Problem 2780

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to find a minimum index at which a given integer array nums can be split into two non-empty contiguous subarrays, such that both subarrays share the same dominant element as the original array. A dominant element is one that occurs in more than half of the elements of an array.

The input is a single integer array nums of length n where 1 <= n <= 10^5, and each element can range up to 10^9. We are guaranteed that nums has exactly one dominant element. The expected output is the smallest index i where a valid split occurs, or -1 if no split satisfies the condition.

The constraints tell us the input array can be large, up to 10^5 elements, so a brute-force approach that examines every possible split and counts occurrences for each subarray will be too slow. Edge cases include arrays where the dominant element is at the very start or end, arrays where no valid split exists, or arrays where the dominant element occurs exactly at half the length in a subarray.

Approaches

Brute Force Approach

A brute-force solution iterates over each potential split index i from 0 to n-2. For each split, we count occurrences of each element in the left and right subarrays, then check if the original dominant element is dominant in both subarrays. While this guarantees correctness, it is extremely slow: counting occurrences in two subarrays repeatedly results in O(n^2) time complexity, which is not feasible for n = 10^5.

Optimal Approach

The key observation is that we do not need to check all elements; only the dominant element of the array matters. Let dom be the dominant element of nums. If we precompute the total count of dom in nums, then as we iterate from left to right, we can maintain a running count of dom in the left subarray. Using this, we can quickly determine if dom is dominant in the left subarray (2 * left_count > left_length) and the right subarray (2 * (total_count - left_count) > right_length).

This approach reduces the problem to a single pass through the array while keeping a running count of the dominant element, resulting in O(n) time complexity and O(1) extra space if we ignore the input array.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Count occurrences for each split; too slow
Optimal O(n) O(1) Single pass with running count of dominant element

Algorithm Walkthrough

  1. Identify the dominant element of the array. Since the problem guarantees exactly one dominant element, we can do this by counting occurrences of each element or using a Boyer-Moore majority vote algorithm.
  2. Count the total occurrences of the dominant element in nums.
  3. Initialize a variable left_count to 0. This will track occurrences of the dominant element in the left subarray as we iterate.
  4. Iterate through each index i from 0 to n-2. At each step:
  • If nums[i] equals the dominant element, increment left_count.
  • Compute left_length = i + 1 and right_length = n - left_length.
  • Check if the dominant element is dominant in both subarrays using 2 * left_count > left_length and 2 * (total_count - left_count) > right_length.
  • If both conditions hold, return i as the minimum valid split index.
  1. If no index satisfies the conditions, return -1.

Why it works: The algorithm maintains the invariant that left_count correctly represents the occurrences of the dominant element in the left subarray at each step. By only considering the original dominant element, we ensure correctness and efficiency.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        count = Counter(nums)
        # Find the dominant element
        dom = max(count, key=count.get)
        total_count = count[dom]
        left_count = 0
        n = len(nums)
        
        for i in range(n - 1):
            if nums[i] == dom:
                left_count += 1
            left_len = i + 1
            right_len = n - left_len
            if 2 * left_count > left_len and 2 * (total_count - left_count) > right_len:
                return i
        return -1

Explanation: We first compute the frequency of each element using Counter and extract the dominant element. As we iterate through the array, left_count is incremented when the current element matches the dominant. For each index, we check dominance conditions for both left and right subarrays and return the first valid index.

Go Solution

func minimumIndex(nums []int) int {
    count := make(map[int]int)
    n := len(nums)
    for _, num := range nums {
        count[num]++
    }

    // Find dominant element
    dom, total := 0, 0
    for num, c := range count {
        if c > total {
            dom = num
            total = c
        }
    }

    leftCount := 0
    for i := 0; i < n-1; i++ {
        if nums[i] == dom {
            leftCount++
        }
        leftLen := i + 1
        rightLen := n - leftLen
        if 2*leftCount > leftLen && 2*(total-leftCount) > rightLen {
            return i
        }
    }
    return -1
}

Go-specific notes: The map is used for counting instead of Counter. Integer arithmetic ensures correct comparisons. The loop structure is slightly different due to Go syntax, but the logic mirrors the Python version exactly.

Worked Examples

Example 1: nums = [1,2,2,2]

i left_count left_len right_len left_check right_check valid
0 0 1 3 False True No
1 1 2 2 True True Yes

The minimum valid index is 2.

Example 2: nums = [2,1,3,1,1,1,7,1,2,1]

Iterating until index 4:

i left_count left_len right_len left_check right_check valid
4 3 5 5 True True Yes

Minimum valid index is 4.

Example 3: nums = [3,3,3,3,7,2,2]

Iterating through all splits:

i left_count left_len right_len left_check right_check valid
No index satisfies both conditions; return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to count occurrences and another to check splits.
Space O(n) Counter/map stores frequencies of all elements; optimal space can be O(1) with Boyer-Moore.

Even for the largest inputs, the algorithm runs efficiently in linear time with a single scan of the array.

Test Cases

# Provided examples
assert Solution().minimumIndex([1,2,2,2]) == 2  # basic split with small array
assert Solution().minimumIndex([2,1,3,1,1,1,7,1,2,1]) == 4  # larger array
assert Solution().minimumIndex([3,3,3,3,7,2,2]) == -1  # no valid split

# Edge cases
assert Solution().minimumIndex([1]) == -1  # single element, cannot split
assert Solution().minimumIndex([2,2]) == 0  # smallest split possible
assert Solution().minimumIndex([1,1,1,1,1,1,1,1,1,1]) == 0  # all elements same
assert Solution().minimumIndex([1,2,1,2,1,2,1,2,1]) == 4  # alternating dominant element
Test Why
[1,2,2,2] Basic valid split, small array
[2,1,3,1,1,1,7,1,2,1] Valid split with larger array, checks counting logic
[3,3,3,3,7,2,2] No valid split exists
[1] Single-element array, cannot split
[2,2] Smallest possible split index
[1]*10 All elements same, first split is valid
Alternating [1,2,1,2,1...] Valid split at