# Earliest Second to Mark Indices I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/earliest-second-to-mark-indices-i)
Canonical: https://scaleengineer.com/dsa/problems/earliest-second-to-mark-indices-i
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## 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 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._

**Example 1:**

**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:**

**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:**

**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] <= 109`
* `1 <= m == changeIndices.length <= 2000`
* `1 <= changeIndices[i] <= n`

# Approaches
## Linear Scan with Greedy Check
This approach iterates through each possible second `k` from 1 to `m` and checks if it's possible to mark all indices by that second. The first `k` for which this is possible is the earliest second and our answer. The core of this approach is a helper function, `check(k)`, which determines if a solution exists for a given time `k`.
**Time:** O(m * (m + n)), where `m` is the length of `changeIndices` and `n` is the length of `nums`. The outer loop runs `m` times. Inside the loop, the `check` function takes O(k + n) time, where `k` can be up to `m`. This leads to a total complexity of O(m * (m + n)). · **Space:** O(n) to store the `lastTime` array for each call to the `check` function.
**Pros:** Relatively straightforward to understand and implement.; The logic for the `check` function is self-contained and reusable.
**Cons:** This approach is less efficient and may result in a 'Time Limit Exceeded' error on platforms with strict time limits, due to its quadratic nature in the worst-case.
### Explanation
The main function will loop through `k` from 1 to `m`. Inside the loop, it calls a function `check(k)`. If `check(k)` returns `true`, we have found the earliest second, so we return `k`. If the loop finishes without finding a suitable `k`, it's impossible, so we return -1.

**The `check(k)` function**:

The key idea is that to maximize our chances, we should perform the "mark" operation for any index `i` at the latest possible second available within the first `k` seconds. This strategy maximizes the number of seconds available for decrement operations.

1.  First, for a given `k`, we find the last second `s <= k` where `changeIndices[s]` points to index `i`. We can pre-calculate this by iterating from `s=1` to `k` and storing the last seen second for each index in a `lastTime` array. If any index `i` does not appear in `changeIndices` up to second `k`, it's impossible to mark it, so `check(k)` returns `false`.
2.  We then simulate the process from second 1 to `k`. We maintain a counter `freeSlots`, which tracks the number of seconds that are not designated for marking and can be used for decrements.
3.  We iterate from time `t = 1` to `k`. If second `t` is the designated marking time for some index `i` (i.e., `t` is the last time `i` appears), we must "pay" for the decrements needed for `nums[i]`. The cost is `nums[i]` decrements. We check if our accumulated `freeSlots` is sufficient. If `freeSlots >= nums[i]`, we use them by subtracting the cost and continue. Otherwise, it's impossible, and `check(k)` returns `false`.
4.  If second `t` is not a designated marking time for any index, it's a free slot that can be used for a decrement, so we increment `freeSlots`.
5.  If the simulation completes for all `k` seconds without failing, it means a valid schedule exists, and `check(k)` returns `true`.

```java
class Solution {
    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int n = nums.length;
        int m = changeIndices.length;

        for (int k = 1; k <= m; k++) {
            if (check(k, nums, changeIndices)) {
                return k;
            }
        }

        return -1;
    }

    private boolean check(int k, int[] nums, int[] changeIndices) {
        int n = nums.length;
        // lastTime[i] stores the last time (0-indexed) index i appears in changeIndices[0...k-1]
        int[] lastTime = new int[n];
        java.util.Arrays.fill(lastTime, -1);
        for (int t = 0; t < k; t++) {
            // changeIndices values are 1-based, convert to 0-based index
            lastTime[changeIndices[t] - 1] = t;
        }

        // Check if all indices can be marked within k seconds
        for (int i = 0; i < n; i++) {
            if (lastTime[i] == -1) {
                return false; // Index i is not in changeIndices[0...k-1]
            }
        }

        int freeSlots = 0;
        for (int t = 0; t < k; t++) {
            int index = changeIndices[t] - 1;
            if (t == lastTime[index]) {
                // This is the designated time to mark 'index'
                if (freeSlots < nums[index]) {
                    return false; // Not enough free slots to decrement nums[index] to 0
                }
                freeSlots -= nums[index];
            } else {
                // This is a free slot
                freeSlots++;
            }
        }
        
        return true;
    }
}
```
### Algorithm
1.  Iterate through each possible answer `k` from 1 to `m`.
2.  For each `k`, call a helper function `check(k)` to verify if it's possible to mark all indices within `k` seconds.
3.  If `check(k)` returns `true`, then `k` is the earliest possible time. Return `k` immediately.
4.  If the loop completes without finding any valid `k`, it's impossible. Return -1.
5.  The `check(k)` function works as follows:
    1.  Determine the last opportunity `lastTime[i]` to mark each index `i` within the first `k` seconds.
    2.  If any index cannot be marked (i.e., doesn't appear in `changeIndices[1...k]`), return `false`.
    3.  Simulate the `k` seconds, counting `freeSlots` (seconds not used for marking).
    4.  When a designated marking second for an index `i` is reached, check if `freeSlots` is enough to cover the `nums[i]` decrements. If not, return `false`.
    5.  If the simulation succeeds, return `true`.

## Binary Search on Time with Greedy Check
A more efficient approach leverages the monotonic nature of the problem. If it's possible to mark all indices by second `k`, it's also possible by any second `k' > k`. This property allows us to use binary search on the answer space, which is the range of seconds `[1, m]`, to find the earliest possible second.
**Time:** O(log(m) * (m + n)). The binary search performs O(log m) iterations. Each iteration involves a call to `check(k)`, which takes O(k + n) time. Since `k` is at most `m`, the complexity of `check` is O(m + n). · **Space:** O(n) to store the `lastTime` array within the `check` function.
**Pros:** Highly efficient due to the logarithmic reduction of the search space.; This is the optimal approach for this type of problem where the feasibility function is monotonic.
**Cons:** The concept of binary searching on the answer might be slightly less intuitive than a direct linear scan.
### Explanation
We can significantly speed up the search for the earliest second by using binary search instead of a linear scan.

1.  We define a search range for the answer, from `low = 1` to `high = m`.
2.  In each step of the binary search, we pick a middle second `mid = low + (high - low) / 2`.
3.  We use the same `check(mid)` helper function described in the previous approach to determine if it's possible to mark all indices by second `mid`.
4.  If `check(mid)` returns `true`, it means `mid` is a possible answer. We then try to find an even earlier second, so we record `mid` as a potential answer and shrink our search space to the lower half by setting `high = mid - 1`.
5.  If `check(mid)` returns `false`, it means `mid` is too early, and we need more time. We search in the upper half by setting `low = mid + 1`.
6.  The search continues until `low` exceeds `high`. The last valid `mid` we found is the earliest possible second. If no valid `mid` is found, it's impossible, and we return -1.

The `check(k)` function remains identical to the one in the linear scan approach, based on the greedy strategy of marking each index at its last possible opportunity.

```java
class Solution {
    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        int n = nums.length;
        int m = changeIndices.length;

        int low = 1, high = m, ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(mid, nums, changeIndices)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return ans;
    }

    private boolean check(int k, int[] nums, int[] changeIndices) {
        int n = nums.length;
        // lastTime[i] stores the last time (0-indexed) index i appears in changeIndices[0...k-1]
        int[] lastTime = new int[n];
        java.util.Arrays.fill(lastTime, -1);
        for (int t = 0; t < k; t++) {
            // changeIndices values are 1-based, convert to 0-based index
            lastTime[changeIndices[t] - 1] = t;
        }

        // Check if all indices can be marked within k seconds
        for (int i = 0; i < n; i++) {
            if (lastTime[i] == -1) {
                return false; // Index i is not in changeIndices[0...k-1]
            }
        }

        int freeSlots = 0;
        for (int t = 0; t < k; t++) {
            int index = changeIndices[t] - 1;
            if (t == lastTime[index]) {
                // This is the designated time to mark 'index'
                if (freeSlots < nums[index]) {
                    return false; // Not enough free slots to decrement nums[index] to 0
                }
                freeSlots -= nums[index];
            } else {
                // This is a free slot
                freeSlots++;
            }
        }
        
        return true;
    }
}
```
### Algorithm
1.  Define a search range for the answer: `low = 1`, `high = m`.
2.  Initialize the answer `ans = -1`.
3.  While `low <= high`:
    a.  Calculate `mid = low + (high - low) / 2`.
    b.  Call the `check(mid)` helper function.
    c.  If `check(mid)` is `true`:
        i.  `mid` is a potential answer. Store it: `ans = mid`.
        ii. Search for an earlier time: `high = mid - 1`.
    d.  Else (`check(mid)` is `false`):
        i.  `mid` is too early. Search for a later time: `low = mid + 1`.
4.  Return `ans`.

# Solutions
### Java

```java
class Solution { public int earliestSecondToMarkIndices ( int [] nums , int [] changeIndices ) { int l = 0 ; int r = changeIndices . length + 1 ; while ( l < r ) { final int m = ( l + r ) / 2 ; if ( canMark ( nums , changeIndices , m )) { r = m ; } else { l = m + 1 ; } } return l <= changeIndices . length ? l : - 1 ; } private boolean canMark ( int [] nums , int [] changeIndices , int second ) { int numMarked = 0 ; int decrement = 0 ; // indexToLastSecond[i] := the last second to mark the index i int [] indexToLastSecond = new int [ nums . length ]; Arrays . fill ( indexToLastSecond , - 1 ); for ( int i = 0 ; i < second ; ++ i ) { indexToLastSecond [ changeIndices [ i ] - 1 ] = i ; } for ( int i = 0 ; i < second ; ++ i ) { // Convert to 0-indexed. final int index = changeIndices [ i ] - 1 ; if ( i == indexToLastSecond [ index ]) { // Reach the last occurrence of the number. // So, the current second will be used to mark the index. if ( nums [ index ] > decrement ) { // The decrement is less than the number to be marked. return false ; } decrement -= nums [ index ]; ++ numMarked ; } else { ++ decrement ; } } return numMarked == nums . length ; } }
```

### CPP

```cpp
class Solution { public: int earliestSecondToMarkIndices ( vector < int >& nums , vector < int >& changeIndices ) { int n = nums . size (); int last [ n + 1 ]; auto check = [ & ]( int t ) { memset ( last , 0 , sizeof ( last )); for ( int s = 0 ; s < t ; ++ s ) { last [ changeIndices [ s ]] = s ; } int decrement = 0 , marked = 0 ; for ( int s = 0 ; s < t ; ++ s ) { int i = changeIndices [ s ]; if ( last [ i ] == s ) { if ( decrement < nums [ i - 1 ]) { return false ; } decrement -= nums [ i - 1 ]; ++ marked ; } else { ++ decrement ; } } return marked == n ; }; int m = changeIndices . size (); int l = 1 , r = m + 1 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( check ( mid )) { r = mid ; } else { l = mid + 1 ; } } return l > m ? - 1 : l ; } };
```

### Python

```python
class Solution : def earliestSecondToMarkIndices ( self , nums : List [ int ], changeIndices : List [ int ] ) -> int : def check ( t : int ) -> bool : decrement = 0 marked = 0 last = { i : s for s , i in enumerate ( changeIndices [: t ])} for s , i in enumerate ( changeIndices [: t ]): if last [ i ] == s : if decrement < nums [ i - 1 ]: return False decrement -= nums [ i - 1 ] marked += 1 else : decrement += 1 return marked == len ( nums ) m = len ( changeIndices ) l = bisect_left ( range ( 1 , m + 2 ), True , key = check ) + 1 return - 1 if l > m else l
```