Problem

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 theearliest second in the range _[1, m]_whenall indices in _nums can be marked by choosing operations optimally, or-1 if it is impossible.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
Output: 8
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Choose index 1 and decrement nums[1] by one. nums becomes [1,2,0].
Second 2: Choose index 1 and decrement nums[1] by one. nums becomes [0,2,0].
Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [0,1,0].
Second 4: Choose index 2 and decrement nums[2] by one. nums becomes [0,0,0].
Second 5: Mark the index changeIndices[5], which is marking index 3, since nums[3] is equal to 0.
Second 6: Mark the index changeIndices[6], which is marking index 2, since nums[2] is equal to 0.
Second 7: Do nothing.
Second 8: Mark the index changeIndices[8], which is marking index 1, since nums[1] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 8th second.
Hence, the answer is 8.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input: nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Choose index 2 and decrement nums[2] by one. nums becomes [1,2].
Second 2: Choose index 2 and decrement nums[2] by one. nums becomes [1,1].
Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [1,0].
Second 4: Mark the index changeIndices[4], which is marking index 2, since nums[2] is equal to 0.
Second 5: Choose index 1 and decrement nums[1] by one. nums becomes [0,0].
Second 6: Mark the index changeIndices[6], which is marking index 1, since nums[1] is equal to 0.
Now all indices have been marked.
It can be shown that it is not possible to mark all indices earlier than the 6th second.
Hence, the answer is 6.

Example 3

1
2
3
4

Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: In this example, it is impossible to mark all indices because index 1 isn't in changeIndices.
Hence, the answer is -1.

Constraints

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 10^9
  • 1 <= m == changeIndices.length <= 2000
  • 1 <= changeIndices[i] <= n

Solution

Method 1 – Greedy Simulation

Intuition

We want to mark all indices in nums as soon as possible. Since we can only mark an index when its value is zero at the second specified by changeIndices, we need to optimally decrement values so that all indices reach zero at the right time. We simulate the process, always decrementing the largest nonzero values first, and try all possible seconds to see if it’s possible to mark all indices by that time.

Approach

  1. Use binary search on the answer: the earliest second in [1, m] where all indices can be marked.
  2. For each candidate second t, simulate the process:
    • For each index, find the last second ≤ t when it can be marked (i.e., when changeIndices[s] == i for some s ≤ t).
    • For each index, count how many decrements are needed before its mark time.
    • If the total number of decrements needed is ≤ the number of available operations (t - n), it’s possible.
  3. Return the minimum such t, or -1 if impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        int n = nums.size(), m = changeIndices.size();
        auto check = [&](int t) -> bool {
            vector<int> last(n, -1);
            for (int i = 0; i < t; ++i) last[changeIndices[i] - 1] = i;
            for (int i = 0; i < n; ++i) if (last[i] == -1) return false;
            vector<int> ops;
            for (int i = 0; i < n; ++i) ops.push_back(last[i] - nums[i]);
            sort(ops.begin(), ops.end());
            for (int i = 0; i < n; ++i) if (ops[i] < i) return false;
            return true;
        };
        int l = n, r = m, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func earliestSecondToMarkIndices(nums []int, changeIndices []int) int {
    n, m := len(nums), len(changeIndices)
    check := func(t int) bool {
        last := make([]int, n)
        for i := range last {
            last[i] = -1
        }
        for i := 0; i < t; i++ {
            last[changeIndices[i]-1] = i
        }
        for i := 0; i < n; i++ {
            if last[i] == -1 {
                return false
            }
        }
        ops := make([]int, n)
        for i := 0; i < n; i++ {
            ops[i] = last[i] - nums[i]
        }
        sort.Ints(ops)
        for i := 0; i < n; i++ {
            if ops[i] < i {
                return false
            }
        }
        return true
    }
    l, r, ans := n, m, -1
    for l <= r {
        mid := (l + r) / 2
        if check(mid) {
            ans = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int n = nums.length, m = changeIndices.length;
        int l = n, r = m, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(nums, changeIndices, mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
    private boolean check(int[] nums, int[] changeIndices, int t) {
        int n = nums.length;
        int[] last = new int[n];
        Arrays.fill(last, -1);
        for (int i = 0; i < t; ++i) last[changeIndices[i] - 1] = i;
        for (int i = 0; i < n; ++i) if (last[i] == -1) return false;
        int[] ops = new int[n];
        for (int i = 0; i < n; ++i) ops[i] = last[i] - nums[i];
        Arrays.sort(ops);
        for (int i = 0; i < n; ++i) if (ops[i] < i) return false;
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun earliestSecondToMarkIndices(nums: IntArray, changeIndices: IntArray): Int {
        val n = nums.size
        val m = changeIndices.size
        fun check(t: Int): Boolean {
            val last = IntArray(n) { -1 }
            for (i in 0 until t) last[changeIndices[i] - 1] = i
            if (last.any { it == -1 }) return false
            val ops = IntArray(n) { last[it] - nums[it] }.sorted()
            for (i in 0 until n) if (ops[i] < i) return false
            return true
        }
        var l = n
        var r = m
        var ans = -1
        while (l <= r) {
            val mid = (l + r) / 2
            if (check(mid)) {
                ans = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def earliestSecondToMarkIndices(self, nums: list[int], changeIndices: list[int]) -> int:
        n, m = len(nums), len(changeIndices)
        def check(t: int) -> bool:
            last = [-1] * n
            for i in range(t):
                last[changeIndices[i] - 1] = i
            if -1 in last:
                return False
            ops = sorted(last[i] - nums[i] for i in range(n))
            for i in range(n):
                if ops[i] < i:
                    return False
            return True
        l, r, ans = n, m, -1
        while l <= r:
            mid = (l + r) // 2
            if check(mid):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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 mut l = n;
        let mut r = m;
        let mut ans = -1;
        while l <= r {
            let mid = (l + r) / 2;
            if check(&nums, &change_indices, mid) {
                ans = mid as i32;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        ans as i32
    }
}
fn check(nums: &Vec<i32>, change_indices: &Vec<i32>, t: usize) -> bool {
    let n = nums.len();
    let mut last = vec![-1; n];
    for i in 0..t {
        last[change_indices[i] as usize - 1] = i as i32;
    }
    if last.iter().any(|&x| x == -1) {
        return false;
    }
    let mut ops: Vec<i32> = last.iter().enumerate().map(|(i, &v)| v - nums[i]).collect();
    ops.sort();
    for (i, &v) in ops.iter().enumerate() {
        if v < i as i32 {
            return false;
        }
    }
    true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    earliestSecondToMarkIndices(nums: number[], changeIndices: number[]): number {
        const n = nums.length, m = changeIndices.length;
        function check(t: number): boolean {
            const last = Array(n).fill(-1);
            for (let i = 0; i < t; ++i) last[changeIndices[i] - 1] = i;
            if (last.includes(-1)) return false;
            const ops = last.map((v, i) => v - nums[i]).sort((a, b) => a - b);
            for (let i = 0; i < n; ++i) if (ops[i] < i) return false;
            return true;
        }
        let l = n, r = m, ans = -1;
        while (l <= r) {
            const mid = (l + r) >> 1;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m log m + n log n), where m is the length of changeIndices and n is the length of nums. Each check is O(n log n), and binary search is O(log m).
  • 🧺 Space complexity: O(n), for auxiliary arrays.