Minimum index of a valid split

Array Hash Table Sorting

75.5% acceptance

Feb 25, 2026

818

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_index(nums: Vec<i32>) -> i32 {
    // Find dominant element using Boyer-Moore majority vote
    let n = nums.len();
    let (mut candidate, mut cnt) = (nums[0], 1i32);
    for &v in &nums[1..] {
      if cnt == 0 { candidate = v; cnt = 1; }
      else if v == candidate { cnt += 1; }
      else { cnt -= 1; }
    }
    let total = nums.iter().filter(|&&x| x == candidate).count();
    let mut left_cnt = 0usize;
    for i in 0..n - 1 {
      if nums[i] == candidate { left_cnt += 1; }
      let left_size = i + 1;
      let right_cnt = total - left_cnt;
      let right_size = n - left_size;
      if left_cnt * 2 > left_size && right_cnt * 2 > right_size {
        return i as i32;
      }
    }
    -1
  }
}