# Earliest Second to Mark Indices II
**Difficulty:** HARD
[External](https://leetcode.com/problems/earliest-second-to-mark-indices-ii)
Canonical: https://scaleengineer.com/dsa/problems/earliest-second-to-mark-indices-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Heap (Priority Queue)
**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`.
* Set `nums[changeIndices[s]]` to any **non-negative** value.
* Choose an index `i` in the range `[1, n]`, where `nums[i]` is **equal** to `0`, and **mark** index `i`.
* 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 = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
**Output:** 6
**Explanation:** In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
Second 4: Mark index 1, since nums[1] is equal to 0.
Second 5: Mark index 2, since nums[2] is equal to 0.
Second 6: Mark index 3, since nums[3] 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 2:**

**Input:** nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
**Output:** 7
**Explanation:** In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Mark index 1, since nums[1] is equal to 0.
Second 2: Mark index 2, since nums[2] is equal to 0.
Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
Second 6: Mark index 3, since nums[3] is equal to 0.
Second 7: Mark index 4, since nums[4] 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 7th second.
Hence, the answer is 7.

**Example 3:**

**Input:** nums = [1,2,3], changeIndices = [1,2,3]
**Output:** -1
**Explanation:** In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. 
Hence, the answer is -1.

**Constraints:**

* `1 <= n == nums.length <= 5000`
* `0 <= nums[i] <= 109`
* `1 <= m == changeIndices.length <= 5000`
* `1 <= changeIndices[i] <= n`

# Approaches
## Linear Scan + Greedy Check
A straightforward approach is to check each possible second `s` starting from 1 up to `m` and find the first `s` for which it's possible to mark all indices. Since marking `n` indices requires at least `n` seconds, we can start our search from `s = n`.
**Time:** O(m * (n + m)). The outer loop runs up to `m` times. Inside, `canMarkAll` takes O(s + n) which is O(m+n) in the worst case. This gives a total of O(m * (m+n)). · **Space:** O(n) to store the `last` occurrence array.
**Pros:** Simple to understand and implement.; Correctly solves the problem.
**Cons:** Less efficient due to the linear scan over `s`, leading to repeated calculations inside the `canMarkAll` function.
### Explanation
The core of this approach is a helper function, `canMarkAll(s)`, which determines if it's possible to mark all `n` indices within `s` seconds. We can iterate `s` from `n` to `m`. The first `s` for which `canMarkAll(s)` returns `true` is our answer. If the loop finishes without finding such an `s`, it's impossible.

### `canMarkAll(s)` Logic:

The strategy within `canMarkAll(s)` is based on a greedy choice. For a given time `s`, we have `s` seconds to perform operations. The most powerful operation is setting `nums[i]` to 0, which saves `nums[i]` decrement operations at the cost of one second. This is a net saving of `nums[i] - 1` operations. This saving is beneficial only if `nums[i] > 1`.

1.  First, calculate the total number of operations required if we only use decrements and marks. This would be `n` (for marks) + `sum(nums)`.
2.  For the given `s` seconds, identify all indices that can be set to 0. An index `i` can be set to 0 if it appears in `changeIndices` at least once within the first `s` seconds. To make the best use of this operation, we should use it at the latest possible second for each such index, but the greedy choice doesn't depend on the timing, just on its availability.
3.  For each index `i` that can be set to 0, we greedily decide whether to use the 'set' operation. We use it if it reduces the total number of operations, which happens when `nums[i] - 1 > 0`, or `nums[i] > 1`.
4.  We calculate the total savings from these greedy choices and subtract it from the initial total operations needed.
5.  If the final number of operations needed is less than or equal to `s`, then it's possible. Otherwise, it's not.

### Algorithm:

1.  Iterate `s` from `n` to `m`.
2.  For each `s`, call `canMarkAll(s)`:
    a. Calculate `totalSum = sum(nums[i])` for all `i`.
    b. Calculate `opsNeeded = n + totalSum`.
    c. Find the last occurrence `last[i]` for each index `i` within `changeIndices[1...s]`.
    d. For each index `i` that has a `last[i] > 0`:
        i. If `nums[i-1] > 1`, we choose to use the 'set' operation. The saving is `nums[i-1] - 1`.
        ii. Subtract this saving from `opsNeeded`.
    e. If `s >= opsNeeded`, then it's possible. Return `s` as the answer.
3.  If the loop completes, it's impossible. Return -1.

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

        for (int s = n; s <= m; s++) {
            if (canMarkAll(s, nums, changeIndices)) {
                return s;
            }
        }
        return -1;
    }

    private boolean canMarkAll(int s, int[] nums, int[] changeIndices) {
        int n = nums.length;
        int[] last = new int[n + 1];
        for (int i = 0; i < s; i++) {
            last[changeIndices[i]] = i + 1;
        }

        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        long opsNeeded = (long)n + totalSum;
        int settableCount = 0;
        for(int i=1; i<=n; ++i) {
            if(last[i] > 0) {
                settableCount++;
            }
        }
        if(settableCount < n) { // Not all indices appear
            // This check is not strictly necessary as the main logic handles it,
            // but it highlights that some indices must be decremented.
        }

        for (int i = 1; i <= n; i++) {
            if (last[i] > 0) { // If index i is settable
                if (nums[i - 1] > 1) {
                    opsNeeded -= (nums[i - 1] - 1);
                }
            }
        }

        return s >= opsNeeded;
    }
}
```
### Algorithm
- Iterate through possible seconds `s` from `n` to `m`.
- For each `s`, check if it's possible to mark all indices using a helper function `canMarkAll(s)`.
- The `canMarkAll(s)` function implements a greedy strategy:
  - Calculate the baseline operations needed: `n` marks + `sum(nums)` decrements.
  - Determine which indices can be reset to 0 within `s` seconds.
  - For each such index `i`, if `nums[i] > 1`, using the 'set' operation saves `nums[i] - 1` operations. Greedily take all such savings.
  - Sum up the total savings and reduce the `opsNeeded`.
  - If `s` is greater than or equal to the final `opsNeeded`, it's possible.
- Return the first `s` for which `canMarkAll(s)` is true.

## Binary Search + Greedy Check
This approach improves upon the linear scan by recognizing that the feasibility of marking all indices is monotonic. If we can mark all indices in `s` seconds, we can also do it in `s+1` seconds. This property allows us to use binary search on the answer `s`.
**Time:** O((n + m) * log m). The binary search performs `log m` iterations. Each iteration calls `canMarkAll`, which takes O(s + n) time, where `s` is at most `m`. So, each check is O(m+n). · **Space:** O(n) to store the `last` occurrence array within the `canMarkAll` function.
**Pros:** Significantly more efficient than the linear scan approach.; Optimal time complexity for the given constraints.
**Cons:** Slightly more complex to implement due to the binary search framework.
### Explanation
We can binary search for the minimum `s` in the range `[1, m]`. For each `mid` value in the binary search, we use the same `canMarkAll(mid)` helper function as in the previous approach to check if it's a feasible number of seconds.

- If `canMarkAll(mid)` is true, it means `mid` could be our answer, but there might be an even smaller `s` that works. So, we try smaller values by setting `high = mid - 1` and storing `mid` as a potential answer.
- If `canMarkAll(mid)` is false, `mid` seconds are not enough. We need more time, so we set `low = mid + 1`.

The `canMarkAll(s)` function remains the same, employing the greedy strategy of minimizing total operations.

### Algorithm:

1.  Initialize `low = 1`, `high = m`, and `ans = -1`.
2.  While `low <= high`:
    a. `mid = low + (high - low) / 2`.
    b. Call `canMarkAll(mid)`.
    c. If `canMarkAll(mid)` is true:
        i. `mid` is a potential answer. Store it: `ans = mid`.
        ii. Try for a smaller `s`: `high = mid - 1`.
    d. Else (`canMarkAll(mid)` is false):
        i. Need more time: `low = mid + 1`.
3.  Return `ans`.

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

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

    private boolean canMarkAll(int s, int[] nums, int[] changeIndices) {
        int n = nums.length;
        // A quick check: we need at least n seconds to mark n indices.
        if (s < n) {
            return false;
        }

        int[] last = new int[n + 1];
        for (int i = 0; i < s; i++) {
            last[changeIndices[i]] = i + 1;
        }

        // Check if all indices appear at least once if their value > 0
        // This is a necessary condition for the greedy strategy to work
        // as we need a 'set' operation for large nums values.
        // However, the main logic below implicitly handles this.
        int settableCount = 0;
        for(int i=1; i<=n; ++i) {
            if(last[i] > 0) {
                settableCount++;
            }
        }
        // If an index has a large value and never appears in changeIndices, it might be impossible.
        // The total ops logic handles this correctly.

        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        long opsNeeded = (long)n + totalSum;

        for (int i = 1; i <= n; i++) {
            if (last[i] > 0) { // If index i is settable
                // The 'set' operation costs 1 second and saves nums[i-1] decrements.
                // Net saving is nums[i-1] - 1. We do this if saving is positive.
                if (nums[i - 1] > 1) {
                    opsNeeded -= (nums[i - 1] - 1);
                }
            }
        }

        return s >= opsNeeded;
    }
}
```
### Algorithm
- The problem has a monotonic property: if all indices can be marked in `s` seconds, they can also be marked in `s+1` seconds.
- This allows for binary searching on the answer `s` in the range `[1, m]`.
- For each `mid` value of `s` in the binary search, use the same greedy `canMarkAll(s)` function from the previous approach.
- If `canMarkAll(mid)` is true, we try to find an even earlier second by searching in the lower half `[low, mid-1]`.
- If `canMarkAll(mid)` is false, we need more seconds, so we search in the upper half `[mid+1, high]`.