Earliest second to mark indices i

Array Binary Search

36.5% acceptance

Feb 25, 2026

202

You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively. Initially, all indices in nums are unmarked. Your task is to mark all indices in nums. In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations: Choose an index i in the range [1, n] and decrement nums[i] by 1. If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s]. Do nothing. Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn earliest_second_to_mark_indices(nums: Vec<i32>, change_indices: Vec<i32>) -> i32 {
    let n = nums.len();
    let m = change_indices.len();
    let can = |t: usize| -> bool {
      let mut last_occ = vec![0usize; n + 1];
      for s in 0..t { last_occ[change_indices[s] as usize] = s + 1; }
      for i in 1..=n { if last_occ[i] == 0 { return false; } }
      let mut free = 0i64;
      for s in 1..=t {
        let idx = change_indices[s - 1] as usize;
        if last_occ[idx] == s {
          if free < nums[idx - 1] as i64 { return false; }
          free -= nums[idx - 1] as i64;
        } else {
          free += 1;
        }
      }
      true
    };
    let mut lo = 1usize;
    let mut hi = m + 1;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if can(mid) { hi = mid; } else { lo = mid + 1; }
    }
    if lo > m { -1 } else { lo as i32 }
  }
}