C++ | binary search | easy understand | O(mlogm)
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can use binary search to find the earliest idx which can mark all indices in the giv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can use binary search to find the earliest idx which can mark all indices in the given arrays.\n\nIn `binarySearch` fuction, we first find the last occurrence of `changeIndices[i]` in the array. This is because we need to make `nums[changeIndices[i]]` zero before this index.\n\nAnd then, we check whether all the indices are present. If any are missing, it means that it is impossible to mark all the indices.\n\nNext, we use `cnt` to record the number of times we can do reduce operations. If the current index is the last occurrence of `changeIndices[i]`, then we check if there is a way to make `nums[changeIndices[i] - 1]` (note the -1, since it is 1-indexed) zero.\n\nIf `nums[changeIndices[i] - 1] > cnt`, it means that it cannot be reduced to zero. In this case, we return False.\n\nFinally, we can use binary search to find the earliest possible index that satisfies the requirements.\n\n# Time Complexity: \nO(m logm), where m is the length of changeIndices\n\n# Code\n```\nclass Solution {\npublic:\n    bool binarySearch(vector<int>& nums, vector<int>& changeIndices, int idx) {\n        unordered_map<int, int> last;\n        for (int i = 0; i < idx; i++) {\n            last[changeIndices[i]] = i;\n        }\n        if (last.size() != nums.size()) return false;\n        int cnt = 0; // record we can reduce how many number\n        for (int i = 0; i < idx; i++) {\n            // if it is last time we visit this idx, we must mark\n            // so check whether this idx already reduce to zero, if not, then return false.\n            if (i == last[changeIndices[i]]) {\n                if (cnt < nums[changeIndices[i] - 1]) return false;\n                else cnt -= nums[changeIndices[i] - 1];\n            } else {\n                cnt++;\n            }\n        }\n        return true;\n    }\n    \n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        int n = nums.size(), m = changeIndices.size();\n        int l = 0, r = m + 1;\n        while (l < r) {\n            int mid = l + (r - l) / 2;\n            if (binarySearch(nums, changeIndices, mid)) {\n                r = mid;\n            } else {\n                l = mid + 1;\n            }\n        }\n        return r == m + 1? -1 : r;\n    }\n};\n\n```
['C++']