C++ | Intuitive | Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \nBinary Search to check whether all the indices can be marked in x number of moves or no
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinary Search to check whether all the indices can be marked in x number of moves or not.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    bool isPos(int moves, vector<int> &nums, vector<int> &changeIndices)\n    {\n       int n = nums.size();\n       int m = changeIndices.size();\n        \n         // all 1 based indexing \n        vector<int> lastOccurence(n+1, -1);\n        for(int i = moves-1; i>=0; i--)\n        {\n            int ind = changeIndices[i];\n            if(lastOccurence[ind] == -1)\n            {\n                lastOccurence[ind] = i+1;\n            }\n        }\n        \n        for(int i = 1; i<=n; i++)\n        {\n            if(lastOccurence[i] == -1)\n                return false;\n        }\n        \n        vector<pair<int,int>> vpr;\n        for(int i = 1; i<=n; i++)\n        {\n            vpr.push_back({lastOccurence[i], i});\n        }\n        \n        sort(vpr.begin(), vpr.end());\n        \n        \n        long long cnt = 0;  \n        for(int i = 0; i< vpr.size(); i++)\n        {\n            int lastInd = vpr[i].first;\n            int ind = vpr[i].second;\n            int needed = nums[ind-1];\n            \n            int available = lastInd - 1- cnt;\n            if(available >= needed)\n            {\n                cnt += needed + 1;\n            }\n            else\n                return false;\n        }\n        \n        return true;\n        \n        \n    }\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        int n = nums.size();\n        int m = changeIndices.size();\n        long long  minNeeded = 0;\n        for(int i = 0; i< n ; i++)\n        {\n            minNeeded += nums[i] + 1;\n        }\n        \n        if(minNeeded > m)\n            return -1;\n        \n        int lo = minNeeded;\n        int hi = m;\n        // FFFFFTTTTTT, minimum true \n        while(hi - lo > 1)\n        {\n            int mid = (hi + lo)/2;\n            if(isPos(mid, nums, changeIndices))\n                hi = mid;\n            else\n                lo = mid + 1;\n        }\n        if(isPos(lo, nums, changeIndices))\n            return lo;\n        if(isPos(hi, nums, changeIndices))\n            return hi;\n        \n        return -1;\n        \n        \n    }\n};\n```
['C++']