[C++] Binary Search + Greedy
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we say at second, s, it can satisfiy the requirement, it implies:\n1. changeIndices[
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we say at second, `s`, it can satisfiy the requirement, it implies:\n1. `changeIndices[:s]` contains all indices `0` to `n-1` (0-indexed)\n2. for every indice, we want to mark it at the last seen index, and we have enough `count` before\n\nSo we can do binary search to check if a given second, `s`, fulfill the requirements\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBinary Search\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(mlogm)$$ // The hash table, `last`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    bool check(int index, vector<int>& nums, vector<int>& changeIndices) {\n        const int n = nums.size();\n        unordered_map<int,int> last;\n\n        for (int i = 0; i <= index; i++) {\n            int cur = changeIndices[i];\n            last[cur] = i;\n        }\n        if (last.size() != n) return false;\n        int count = 0;\n        for (int i = 0; i <= index; i++) {\n            int cur = changeIndices[i];\n            if (i == last[cur]) {\n                int need = nums[cur];\n                count -= need;\n                if (count < 0) return false;\n            }\n            else {\n                count++;\n            }\n        }\n        return true;\n    }\n\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        const int m = changeIndices.size();\n\n        for (int i = 0; i < changeIndices.size(); i++) {\n            changeIndices[i]--;\n        }\n\n        int left = 0; int right = m-1;\n        while (left <= right) {\n            int mid = left + (right-left) / 2;\n            if (check(mid, nums, changeIndices)) {\n                right = mid - 1;\n            }\n            else {\n                left = mid + 1;\n            }\n        }\n\n        return left < m ? left+1 : -1;\n    }\n};\n```
['C++']