Earliest Second to Mark Indices I

Link

Solution

See reference (Chinese).

class Solution {
public:
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        int n = nums.size(), m = changeIndices.size();
        if (n > m) return -1;

        vector<int> lastIndex(n);

        auto check = [&](int mx) -> bool {
            fill(lastIndex.begin(), lastIndex.end(), -1);
            for (int t = 0; t < mx; t++) {
                lastIndex[changeIndices[t] - 1] = t;
            }
            if (find(lastIndex.begin(), lastIndex.end(), -1) != lastIndex.end()) {
                return false;
            }

            int count = 0;
            for (int i = 0; i < mx; i++) {
                int idx = changeIndices[i] - 1;
                if (i == lastIndex[idx]) {
                    if (nums[idx] > count)
                        return false;
                    count -= nums[idx];
                } else {
                    count++;
                }
            }

            return true;
        };

        int left = n - 1, right = m + 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (check(mid)) right = mid;
            else left = mid;
        }

        return right > m ? -1 : right;
    }
};