Binary Search O((n + m) * lgm): 2ms beating 100%
IntuitionUse binary search for the range [n, m].Approach
For simplicity, let's assume both arrays are 0-indexed. We can do the conversion easily.
For each test
# Intuition
Use binary search for the range [n, m].
# Approach
1. For simplicity, let's assume both arrays are 0-indexed. We can do the conversion easily.
2. For each test point mid in the range [n, m], use a verifier function canDo(mid) to check whether mid can do.
3. Inside the function canDo(mid), define an array table of size n, recording which indices in nums have been handled.
4. Also define an array road of size mid, recording the required 'payload' for some indices.
5. In changeIndices, go from index mid - 1 down to 0. When at index i we encounter a value changeAt that has not been met before, we set table[changeAt] = true, and road[i] = nums[changeAt] to put the 'payload' there.
6. If beyond 0, table has not yet been filled completely, it means some indices in nums can never be marked, so we directly return false.
7. Otherwise, we go thru road from left to right with freeCount = 0. When we encounter an undefined, we increment freeCount by 1. When we encounter a number ('payload'), we decrement freeCount by that 'payload' value. If freeCount becomes negative, it means there are not enough decreasing operations, so we return false.
8. Otherwise, return true in the canDo(mid) function to indicate the success of checking.
9. The above is the logic of the canDo(mid) function. Use it for the range [n, m].
# Complexity
- Time complexity:
O((n + m) * lgm)
- Space complexity:
O(n + m)
# Code
```javascript []
/**
 * @param {number[]} nums
 * @param {number[]} changeIndices
 * @return {number}
 */
var earliestSecondToMarkIndices = function(nums, changeIndices) {
    const len = nums.length, size = changeIndices.length
    function canDo(mid) {
        const road = new Array(mid)
        const table = new Array(len)
        let doneCount = 0
        for (let i = mid - 1; i > -1; i--) {
            const changeAt = changeIndices[i] - 1
            if (table[changeAt] === undefined) {
                table[changeAt] = true
                road[i] = nums[changeAt]
                doneCount++
                if (doneCount === len)
                    break
            }
        }
        if (doneCount < len)    return false

        for (let i = 0, freeCount = 0; i < mid; i++) {
            const val = road[i]
            if (val === undefined) {
                freeCount++
            } else {
                freeCount -= val
                if (freeCount < 0)    return false
            }
        }

        return true
    }


    let low = len, high = size
    // find earliest high where
    // canDo(high) === true
    if (!canDo(high))   return -1
    while (low < high) {
        const mid = (low + high) >> 1
        if (canDo(mid)) high = mid
        else    low = 1 + mid
    }


    return high
};
```
['JavaScript']