Problem Informations

• Problem Index: 2780
• Problem Link: Minimum Index of a Valid Split
• Topics: Array, Hash Table, Sorting

Problem Description

An element $x$ of an integer array $arr$ of length $m$ is dominant if more than half the elements of $arr$ have a value of $x$.

You are given a 0-indexed integer array $nums$ of length $n$ with one dominant element.

You can split $nums$ at an index $i$ into two arrays $nums[0, \ldots, i]$ and $nums[i + 1, \ldots, n - 1]$, but the split is only valid if:

• $0 \leq i < n - 1$
• $nums[0, \ldots, i]$, and $nums[i + 1, \ldots, n - 1]$ have the same dominant element.

Here, $nums[i, \ldots, j]$ denotes the subarray of $nums$ starting at index $i$ and ending at index $j$, both ends being inclusive. Particularly, if $j < i$ then $nums[i, \ldots, j]$ denotes an empty subarray.

Return the minimum index of a valid split. If no valid split exists, return $-1$.

Example 1:

Input: nums = [1,2,2,2]
Output: 2
Explanation: We can split the array at index 2 to obtain arrays [1,2,2] and [2]. 
In array [1,2,2], element 2 is dominant since it occurs twice in the array and $2 \times 2 > 3$. 
In array [2], element 2 is dominant since it occurs once in the array and $1 \times 2 > 1$.
Both [1,2,2] and [2] have the same dominant element as nums, so this is a valid split. 
It can be shown that index 2 is the minimum index of a valid split.

Example 2:

Input: nums = [2,1,3,1,1,1,7,1,2,1]
Output: 4
Explanation: We can split the array at index 4 to obtain arrays [2,1,3,1,1] and [1,7,1,2,1].
In array [2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and $3 \times 2 > 5$.
In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and $3 \times 2 > 5$.
Both [2,1,3,1,1] and [1,7,1,2,1] have the same dominant element as nums, so this is a valid split.
It can be shown that index 4 is the minimum index of a valid split.

Example 3:

Input: nums = [3,3,3,3,7,2,2]
Output: -1
Explanation: It can be shown that there is no valid split.

Constraints:

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $nums$ has exactly one dominant element.

Intuition

The problem requires identifying the smallest index at which an array can be split into two subarrays, each having the same dominant element as the original array. The dominant element is defined as the one that appears more than half the times in its respective subarray. Given the constraints that there is exactly one dominant element and the array size, a solution can be constructed by leveraging a two-pass approach to track both the overall dominant element and its occurrences in potential sub-splits.

Approach

The algorithm follows these key steps:

1. Identify the Dominant Element:

   • Traverse the array and maintain a frequency map to record the appearance count of each element.
   • Simultaneously keep track of the most frequently occurring element, i.e., the dominant element.

2. Determine the Minimum Valid Split Index:

   • Use a second pass through the array while maintaining a count of occurrences of the dominant element in the first subarray as the algorithm iterates.
   • For each possible split index $i$, verify:
     • If the current count of the dominant element in the potential first subarray makes it dominant, satisfying $dominantCount \times 2 > (i + 1)$.
     • If the remaining occurrences in the potential second subarray also allow the element to remain dominant, satisfying $(frequencyMap[dominantElement] - dominantCount) \times 2 > (n - i - 1)$, where $n$ is the length of the array.
   • If both conditions are satisfied for a particular index, that index qualifies as a valid split point.

3. Return Result:

   • The index of the first valid split found is returned as the minimum index.
   • If no valid split is identified throughout the iteration, the algorithm returns $-1$.

The approach efficiently determines the minimal splitting index by leveraging frequency calculations and conditions that both subarrays must satisfy regarding dominance. This ensures the algorithm operates within O(n) complexity, meeting the problem’s constraints.

Code

C++

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        // Map to store the frequency of each element in the array
        map<int, int> frequencyMap;

        // Variable to keep track of the most frequent (dominant) element
        int dominantElement = nums.front();

        // Calculate the frequency of each element in the array
        for (int num : nums) {
            if (++frequencyMap[num] > frequencyMap[dominantElement]) {
                dominantElement = num; // Update the dominant element if current has higher frequency
            }
        }

        // Variable to track the frequency of the dominant element in the first part of the split
        int dominantCount = 0;

        // Iterate through the array to find the minimum valid split index
        for (int i = 0; i < nums.size() - 1; i++) {
            // Check if the current element is the dominant element
            if (nums[i] == dominantElement) {
                dominantCount++;
            }

            // Check if the split is valid at the current index
            if (
                dominantCount * 2 > i + 1 &&                                   // Dominant in the first subarray
                (frequencyMap[dominantElement] - dominantCount) * 2 > nums.size() - i - 1   // Dominant in the second subarray
               ) {
                return i; // Return the minimum index of a valid split
            }
        }

        return -1; // Return -1 if there is no valid split
    }
};

Python

class Solution:
    def minimumIndex(self, nums):
        # Map to store the frequency of each element in the array
        frequencyMap = {}

        # Variable to keep track of the most frequent (dominant) element
        dominantElement = nums[0]

        # Calculate the frequency of each element in the array
        for num in nums:
            frequencyMap[num] = frequencyMap.get(num, 0) + 1
            if frequencyMap[num] > frequencyMap.get(dominantElement, 0):
                dominantElement = num  # Update the dominant element if current has higher frequency

        # Variable to track the frequency of the dominant element in the first part of the split
        dominantCount = 0

        # Iterate through the array to find the minimum valid split index
        for i in range(len(nums) - 1):
            # Check if the current element is the dominant element
            if nums[i] == dominantElement:
                dominantCount += 1

            # Check if the split is valid at the current index
            if (
                dominantCount * 2 > i + 1 and  # Dominant in the first subarray
                (frequencyMap[dominantElement] - dominantCount) * 2 > len(nums) - i - 1  # Dominant in the second subarray
            ):
                return i  # Return the minimum index of a valid split

        return -1  # Return -1 if there is no valid split

Complexity

• Time complexity: $O(n)$

  The time complexity of the algorithm is $O(n)$, where $n$ is the length of the input array nums. This is due to the two sequential passes over the array. The first pass calculates the frequency of each element in the array using a map, which takes $O(n)$ time. The second pass iterates through the array to determine the minimum valid split index, which also requires $O(n)$ time. Since these two operations are sequential, the overall complexity remains linear.

• Space complexity: $O(n)$

  The space complexity is $O(n)$ due to the use of a map (frequencyMap) to store the frequency of each element in the array. In the worst case, where all elements are unique, the map will need to store a frequency count for each element, resulting in a space requirement proportional to the size of the array, $n$. However, apart from the map, only a constant amount of additional space is used for integer variables to track the dominant element and counts, so the overall space complexity is driven by the map.