Scale Engineer

Minimum Index of a Valid Split

Med
#2493Time: 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).
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem