Problem statement

You are given a 1-indexed array nums of length n and a 1-indexed array changeIndices of length m. Every index of nums starts unmarked; the goal is to mark all of them.

Seconds run from 1 to m. In second s you may do exactly one of the following:

• pick any index i and decrease nums[i] by 1;
• if nums[changeIndices[s]] is 0, mark the index changeIndices[s];
• do nothing.

Return the earliest second in [1, m] by which every index can be marked when the operations are chosen optimally, or -1 if that is impossible.

Example 1

Input: nums = [1,0], changeIndices = [2,1,1]
Output: 3
Explanation: Second 1 marks index 2 (already 0), second 2 lowers index 1 to 0, second 3 marks index 1.

Example 2

Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
Output: 8

Example 3

Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: Index 1 never appears in `changeIndices`, so it can never be marked.

Constraints

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

Hints for Earliest Second to Mark Indices I

1. Hint 1

   If everything can be marked by second s, it can also be marked by any later second — so binary-search s.

2. Hint 2

   Within the first s seconds, it is never worse to mark an index at its last appearance: that leaves every earlier second free for decrements.

3. Hint 3

   Sweep seconds 1..s: a last appearance spends its accumulated free seconds on that index's value (fail if there are not enough); every other second adds one free second.

How to solve Earliest Second to Mark Indices I

Binary search the answer s. To test a prefix of s seconds, mark each index at its last appearance inside the prefix and check, sweeping left to right, that enough spare seconds have accumulated to bring that index to zero first.

Approach

1. feasible(s): record the last second (within the first s) at which each index appears; if some index never appears, fail.
2. Sweep t = 1..s with a counter free = 0. If t is the last appearance of i = changeIndices[t], require free >= nums[i], then do free -= nums[i] (second t itself is the mark). Otherwise free += 1.
3. If feasible(m) is false return -1; otherwise binary-search the smallest feasible s in [1, m].

Why it works

Marking index i earlier than its last appearance never helps: moving the mark to the last appearance frees a second earlier on and only shortens no deadline. With marks fixed at last appearances, the sweep is an earliest-deadline-first schedule of unit decrements, which succeeds whenever any schedule does. Extending the prefix only moves deadlines later and adds seconds, so feasibility is monotone.

Complexity

• Time — O((n + m) log m)
• Space — O(n)

Pitfalls

• Both arrays are 1-indexed — subtract 1 before indexing nums.
• Values up to 10^9 simply make the prefix infeasible; compare before subtracting, never loop over them.
• The marking second cannot also be used for a decrement.

Reference solution

Python

from typing import List

def earliestSecondToMarkIndices(nums: List[int], changeIndices: List[int]) -> int:
    n, m = len(nums), len(changeIndices)

    def feasible(s):
        last = [-1] * n
        for t in range(s):
            last[changeIndices[t] - 1] = t
        if min(last) < 0:
            return False
        free = 0
        for t in range(s):
            i = changeIndices[t] - 1
            if last[i] == t:
                if free < nums[i]:
                    return False
                free -= nums[i]
            else:
                free += 1
        return True

    if not feasible(m):
        return -1
    lo, hi = 1, m
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

public static int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
    int m = changeIndices.length;
    if (!markable(nums, changeIndices, m)) return -1;
    int lo = 1, hi = m;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (markable(nums, changeIndices, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

static boolean markable(int[] nums, int[] changeIndices, int s) {
    int n = nums.length;
    int[] last = new int[n];
    Arrays.fill(last, -1);
    for (int t = 0; t < s; t++) last[changeIndices[t] - 1] = t;
    for (int v : last) if (v < 0) return false;
    long free = 0;
    for (int t = 0; t < s; t++) {
        int i = changeIndices[t] - 1;
        if (last[i] == t) {
            if (free < nums[i]) return false;
            free -= nums[i];
        } else {
            free++;
        }
    }
    return true;
}

C++

bool markable(const vector<int>& nums, const vector<int>& changeIndices, int s) {
    int n = nums.size();
    vector<int> last(n, -1);
    for (int t = 0; t < s; t++) last[changeIndices[t] - 1] = t;
    for (int v : last) if (v < 0) return false;
    long long freeSec = 0;
    for (int t = 0; t < s; t++) {
        int i = changeIndices[t] - 1;
        if (last[i] == t) {
            if (freeSec < nums[i]) return false;
            freeSec -= nums[i];
        } else {
            freeSec++;
        }
    }
    return true;
}

int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
    int m = changeIndices.size();
    if (!markable(nums, changeIndices, m)) return -1;
    int lo = 1, hi = m;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (markable(nums, changeIndices, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

JavaScript

var earliestSecondToMarkIndices = function(nums, changeIndices) {
    var n = nums.length, m = changeIndices.length;
    var feasible = function(s) {
        var last = new Array(n).fill(-1);
        for (var t = 0; t < s; t++) last[changeIndices[t] - 1] = t;
        for (var i = 0; i < n; i++) if (last[i] < 0) return false;
        var free = 0;
        for (var u = 0; u < s; u++) {
            var idx = changeIndices[u] - 1;
            if (last[idx] === u) {
                if (free < nums[idx]) return false;
                free -= nums[idx];
            } else {
                free++;
            }
        }
        return true;
    };
    if (!feasible(m)) return -1;
    var lo = 1, hi = m;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (feasible(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

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

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium