Minimum Index of a Valid Split

Medium
1803.

Minimum Index of a Valid Split

Minimum Index of a Valid Split is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

An element x is dominant in an array arr when it occurs more than half the time: 2 · freq(x) > arr.length. An array has at most one dominant element.

You are given an integer array nums (0-indexed) that is guaranteed to have a dominant element. Splitting at index i (0 <= i < n - 1) produces nums[0..i] and nums[i + 1..n - 1]; the split is valid if both parts have the same dominant element.

Return the minimum index of a valid split, or -1 if there is none.

Example 1

Input
nums = [1,2,2,2]
Output
2
Explanation
Splitting after index 2 gives `[1,2,2]` and `[2]`, both dominated by 2. Splitting at 0 or 1 leaves a left part with no dominant element.

Example 2

Input
nums = [2,1,3,1,1,1,7,1,2,1]
Output
4
Explanation
`[2,1,3,1,1]` and `[1,7,1,2,1]` are both dominated by 1.

Example 3

Input
nums = [3,3,3,3,7,2,2]
Output
-1
Explanation
Any left part dominated by 3 leaves too few 3s on the right.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums has exactly one dominant element
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumIndex = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Index of a Valid Split — Problem & Solution

Minimum Index of a Valid Split solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Index of a Valid Split is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Sorting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An element x is dominant in an array arr when it occurs more than half the time: 2 · freq(x) > arr.length. An array has at most one dominant element.

You are given an integer array nums (0-indexed) that is guaranteed to have a dominant element. Splitting at index i (0 <= i < n - 1) produces nums[0..i] and nums[i + 1..n - 1]; the split is valid if both parts have the same dominant element.

Return the minimum index of a valid split, or -1 if there is none.

Example 1

Input: nums = [1,2,2,2]
Output: 2
Explanation: Splitting after index 2 gives `[1,2,2]` and `[2]`, both dominated by 2. Splitting at 0 or 1 leaves a left part with no dominant element.

Example 2

Input: nums = [2,1,3,1,1,1,7,1,2,1]
Output: 4
Explanation: `[2,1,3,1,1]` and `[1,7,1,2,1]` are both dominated by 1.

Example 3

Input: nums = [3,3,3,3,7,2,2]
Output: -1
Explanation: Any left part dominated by 3 leaves too few 3s on the right.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums has exactly one dominant element

Hints for Minimum Index of a Valid Split

  1. Hint 1

    If both halves share a dominant element y, then y occurs more than half the time in the whole array — so it must be the array's own dominant element.

  2. Hint 2

    Find that element d and its total count first (a hash map, or Boyer–Moore voting).

  3. Hint 3

    Scan the split point left to right, keeping how many copies of d are on the left. The split at i is valid when 2 · left > i + 1 and 2 · (total − left) > n − i − 1.

How to solve Minimum Index of a Valid Split

Only the array's dominant element d can dominate both halves: if y is more than half of each part, it is more than half of the whole. So count d once, then sweep the split point with a running prefix count of d.

Approach

  1. Find the dominant element d (Boyer–Moore majority vote) and its total count total.
  2. Sweep i from 0 to n - 2, adding 1 to left whenever nums[i] == d.
  3. Return the first i with 2 · left > i + 1 and 2 · (total − left) > n − i − 1.
  4. If no index qualifies, return −1.

Why it works

If both parts are dominated by y, then freq(y) > (i + 1)/2 + (n − i − 1)/2 = n/2, so y = d. Conversely the two inequalities say exactly that d is dominant on each side. The first index where they hold is the answer.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Recomputing each half's dominant element from scratch is O(n^2).
  • The last valid split index is n - 2; the right part must be non-empty.
  • Use strict inequalities — exactly half is not dominant.

Reference solution

Python

from typing import List

def minimumIndex(nums: List[int]) -> int:
    d, votes = nums[0], 0
    for v in nums:
        if votes == 0:
            d = v
        votes += 1 if v == d else -1
    total = nums.count(d)
    n = len(nums)
    left = 0
    for i in range(n - 1):
        if nums[i] == d:
            left += 1
        if 2 * left > i + 1 and 2 * (total - left) > n - i - 1:
            return i
    return -1

Java

public static int minimumIndex(int[] nums) {
    int n = nums.length;
    int d = nums[0], votes = 0;
    for (int v : nums) {
        if (votes == 0) d = v;
        votes += v == d ? 1 : -1;
    }
    int total = 0;
    for (int v : nums) if (v == d) total++;
    int left = 0;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == d) left++;
        if (2 * left > i + 1 && 2 * (total - left) > n - i - 1) return i;
    }
    return -1;
}

C++

int minimumIndex(vector<int>& nums) {
    int n = nums.size();
    int d = nums[0], votes = 0;
    for (int v : nums) {
        if (votes == 0) d = v;
        votes += v == d ? 1 : -1;
    }
    int total = 0;
    for (int v : nums) if (v == d) total++;
    int left = 0;
    for (int i = 0; i < n - 1; i++) {
        if (nums[i] == d) left++;
        if (2 * left > i + 1 && 2 * (total - left) > n - i - 1) return i;
    }
    return -1;
}

JavaScript

var minimumIndex = function(nums) {
    var n = nums.length;
    var d = nums[0], votes = 0;
    for (var i = 0; i < n; i++) {
        if (votes === 0) d = nums[i];
        votes += nums[i] === d ? 1 : -1;
    }
    var total = 0;
    for (var j = 0; j < n; j++) if (nums[j] === d) total++;
    var left = 0;
    for (var k = 0; k < n - 1; k++) {
        if (nums[k] === d) left++;
        if (2 * left > k + 1 && 2 * (total - left) > n - k - 1) return k;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets