# Minimum Index of a Valid Split
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-index-of-a-valid-split)
Canonical: https://scaleengineer.com/dsa/problems/minimum-index-of-a-valid-split
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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, ..., i]` and `nums[i + 1, ..., n - 1]`, but the split is only **valid** if:

* `0 <= i < n - 1`
* `nums[0, ..., i]`, and `nums[i + 1, ..., n - 1]` have the same dominant element.

Here, `nums[i, ..., 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, ..., 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 * 2 > 3. 
In array [2], element 2 is dominant since it occurs once in the array and 1 * 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 * 2 > 5.
In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3 * 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 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `nums` has exactly one dominant element.

# Approaches
## Brute Force with Nested Loops
This approach iterates through every possible split index `i`. For each split, it independently calculates the dominant element for the left subarray `nums[0...i]` and the right subarray `nums[i+1...n-1]`. If both subarrays have a dominant element and they are the same, the index `i` is a valid split. The first such index found is the minimum.
**Time:** O(n^2). The outer loop runs `n-1` times. Inside the loop, `findDominant` for the left part takes `O(i)` time and for the right part takes `O(n-i)` time. The total time for one iteration is `O(i + n - i) = O(n)`. Thus, the overall complexity is `O(n * n) = O(n^2)`. · **Space:** O(n). In each iteration, two HashMaps are created. The combined size of these maps can be up to O(n) in the worst case (when all elements are unique).
**Pros:** Simple to understand and implement.; Correctly solves the problem without relying on the pre-condition that the whole array has a dominant element.
**Cons:** Highly inefficient due to repeated calculations. The frequency of elements is recounted in every iteration.; Fails to leverage the crucial problem constraint that `nums` has a dominant element, leading to unnecessary work.
### Explanation
The algorithm iterates with an outer loop for `i` from `0` to `n-2`. Inside the loop, two helper functions are used: one to find the dominant element of the left part (`nums[0...i]`) and one for the right part (`nums[i+1...n-1]`). Each helper function would typically use a frequency map (like a HashMap) to count element occurrences within its given subarray range. It then iterates through the map to see if any element's count is more than half the subarray's length. If both helper functions return a dominant element and these elements are equal, we have found a valid split. Since we are iterating `i` from the beginning, the first valid split found is the minimum, so we return `i`. If the loop completes without finding any valid split, it means none exist, and we return `-1`.

```java
import java.util.List;
import java.util.Map;
import java.util.HashMap;

class Solution {
    // Helper to find dominant element in a subarray range
    private int findDominant(List<Integer> nums, int start, int end) {
        if (start > end) {
            return -1; // Empty subarray
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = start; i <= end; i++) {
            counts.put(nums.get(i), counts.getOrDefault(nums.get(i), 0) + 1);
        }
        int len = end - start + 1;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() * 2 > len) {
                return entry.getKey();
            }
        }
        return -1; // No dominant element
    }

    public int minimumIndex(List<Integer> nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            int dom_left = findDominant(nums, 0, i);
            int dom_right = findDominant(nums, i + 1, n - 1);

            if (dom_left != -1 && dom_left == dom_right) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Loop for `i` from `0` to `nums.length - 2`.
- Define the left subarray from index `0` to `i`.
- Find the dominant element `dom_left` of the left subarray. This involves:
    - Creating a frequency map for elements in `nums[0...i]`.
    - Checking if any element count `c` satisfies `c * 2 > (i + 1)`.
- Define the right subarray from index `i + 1` to `n - 1`.
- Find the dominant element `dom_right` of the right subarray. This involves:
    - Creating a frequency map for elements in `nums[i+1...n-1]`.
    - Checking if any element count `c` satisfies `c * 2 > (n - 1 - i)`.
- If `dom_left` and `dom_right` both exist and `dom_left == dom_right`, return `i`.
- If the loop finishes, return `-1`.

## Two-Pass with Frequency Counting
This approach improves upon the brute-force method by first identifying the dominant element of the entire array `nums`. A valid split can only occur if both subarrays share this same dominant element. We can find this element and its total count in a single pass. Then, in a second pass, we iterate through possible split points, keeping a running count of the dominant element in the left subarray and checking the dominance conditions for both subarrays.
**Time:** O(n). The first pass to build the frequency map and find the dominant element takes O(n). The second pass to check for a valid split also takes O(n). The total is `O(n) + O(n) = O(n)`. · **Space:** O(k), where `k` is the number of unique elements in `nums`. In the worst case, `k` can be `n`, so the space complexity is O(n) for the HashMap.
**Pros:** Much more efficient than the brute-force approach with linear time complexity.; Logically straightforward and easy to follow.
**Cons:** Requires extra space for the frequency map, which can be up to O(n).
### Explanation
**Pass 1: Find Dominant Element and Total Count.**
We iterate through the `nums` array once to build a frequency map (e.g., a HashMap). From this map, we identify the dominant element `dom` (the one with frequency > `n/2`) and store its total count `total_count`. The problem guarantees such an element exists.

**Pass 2: Find Minimum Valid Split Index.**
We initialize a counter `left_count` to `0`. We iterate through `nums` from index `i = 0` to `n-2`. At each index `i`, if `nums[i]` is the dominant element `dom`, we increment `left_count`. The count of `dom` in the right subarray (`nums[i+1...n-1]`) can be calculated as `right_count = total_count - left_count`. We then check if `dom` is dominant in both subarrays:
1. Left subarray `nums[0...i]`: `left_count * 2 > (i + 1)`
2. Right subarray `nums[i+1...n-1]`: `right_count * 2 > (n - 1 - i)`
If both conditions are met, `i` is a valid split index. Since we are iterating from `0`, the first one we find is the minimum, so we return `i`. If the loop finishes without finding a valid split, we return `-1`.

```java
import java.util.List;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int minimumIndex(List<Integer> nums) {
        int n = nums.size();
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int dom = -1;
        int totalCount = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() * 2 > n) {
                dom = entry.getKey();
                totalCount = entry.getValue();
                break;
            }
        }

        int leftCount = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums.get(i) == dom) {
                leftCount++;
            }
            int rightCount = totalCount - leftCount;
            // Check for dominance in left part
            if (leftCount * 2 > (i + 1)) {
                // Check for dominance in right part
                if (rightCount * 2 > (n - 1 - i)) {
                    return i;
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
- Create a frequency map to count occurrences of each number in `nums`.
- Iterate through the map to find the dominant element `dom` and its `total_count`.
- Initialize `left_count = 0`.
- Loop for `i` from `0` to `nums.length - 2`.
- If `nums[i] == dom`, increment `left_count`.
- Calculate `right_count = total_count - left_count`.
- Check if `left_count * 2 > (i + 1)` AND `right_count * 2 > (nums.length - 1 - i)`.
- If the condition is true, return `i`.
- If the loop finishes, return `-1`.

## Two-Pass with Boyer-Moore Voting Algorithm
This is the most optimal approach in terms of space complexity. It uses the same two-pass logic as the previous approach but finds the dominant element using the Boyer-Moore Voting Algorithm, which requires only constant extra space. The rest of the logic remains the same.
**Time:** O(n). Although it seems like three passes (one for Boyer-Moore, one for counting, one for checking splits), each pass is linear. The total time complexity is `O(n) + O(n) + O(n) = O(n)`. · **Space:** O(1). This approach uses only a few variables to store the candidate, counts, and loop indices, regardless of the input size.
**Pros:** Optimal space complexity of O(1).; Maintains an efficient linear time complexity.
**Cons:** Slightly more complex to understand due to the Boyer-Moore algorithm.; The constant factor for time complexity might be slightly higher than the HashMap approach due to multiple passes, but this is usually negligible.
### Explanation
**Pass 1: Find Dominant Element and Total Count.**
Instead of a HashMap, we use the Boyer-Moore Voting Algorithm to find a *candidate* for the dominant element. This algorithm iterates through the array once, maintaining a candidate and a counter. It works in `O(n)` time and `O(1)` space. Since the problem guarantees a dominant element, the candidate found by this algorithm is guaranteed to be the dominant element. After finding the dominant element `dom`, we perform a second scan through the array to get its `total_count`.

**Pass 2: Find Minimum Valid Split Index.**
This pass is identical to the second pass of the previous approach. We iterate from `i = 0` to `n-2`, maintain a `left_count` of the dominant element, and check the dominance conditions for the left and right subarrays at each potential split point.

```java
import java.util.List;

class Solution {
    public int minimumIndex(List<Integer> nums) {
        int n = nums.size();

        // Pass 1: Find dominant element candidate using Boyer-Moore
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        int dom = candidate;

        // Pass 2: Count total occurrences of the dominant element
        int totalCount = 0;
        for (int num : nums) {
            if (num == dom) {
                totalCount++;
            }
        }

        // Pass 3: Find the minimum valid split index
        int leftCount = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums.get(i) == dom) {
                leftCount++;
            }
            int rightCount = totalCount - leftCount;
            if (leftCount * 2 > (i + 1) && rightCount * 2 > (n - 1 - i)) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- **Find Dominant Element Candidate:**
    - Initialize `candidate = -1` and `count = 0`.
    - Iterate through `nums`. If `count` is `0`, set `candidate` to the current number and `count` to `1`. Otherwise, if the current number matches `candidate`, increment `count`; else, decrement `count`.
    - The final `candidate` is the dominant element `dom`.
- **Get Total Count:**
    - Initialize `total_count = 0`.
    - Iterate through `nums` and count all occurrences of `dom`.
- **Find Split Index:**
    - Initialize `left_count = 0`.
    - Loop for `i` from `0` to `nums.length - 2`.
    - If `nums[i] == dom`, increment `left_count`.
    - Calculate `right_count = total_count - left_count`.
    - Check if `left_count * 2 > (i + 1)` AND `right_count * 2 > (nums.length - 1 - i)`.
    - If the condition is true, return `i`.
- If the loop finishes, return `-1`.

# Solutions
### Java

```java
class Solution {
public
  int minimumIndex(List<Integer> nums) {
    int x = 0, cnt = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int v : nums) {
      int t = freq.merge(v, 1, Integer : : sum);
      if (cnt < t) {
        cnt = t;
        x = v;
      }
    }
    int cur = 0;
    for (int i = 1; i <= nums.size(); ++i) {
      if (nums.get(i - 1) == x) {
        ++cur;
        if (cur * 2 > i && (cnt - cur) * 2 > nums.size() - i) {
          return i - 1;
        }
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumIndex(vector<int> &nums) {
    int x = 0, cnt = 0;
    unordered_map<int, int> freq;
    for (int v : nums) {
      ++freq[v];
      if (freq[v] > cnt) {
        cnt = freq[v];
        x = v;
      }
    }
    int cur = 0;
    for (int i = 1; i <= nums.size(); ++i) {
      if (nums[i - 1] == x) {
        ++cur;
        if (cur * 2 > i && (cnt - cur) * 2 > nums.size() - i) {
          return i - 1;
        }
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def minimumIndex(self, nums: List[int]) -> int: x, cnt = Counter(nums). most_common(1)[0] cur = 0 for i, v in enumerate(nums, 1): if v == x: cur += 1 if cur * 2 > i and (cnt - cur) * 2 > len(nums) - i: return i - 1 return - 1

```