Greedy + Binary Search | Beats 100% | TC | SC | Intutition to Solution
Intuition\nSo first afall ask yourself what is range of second, considering that the answer is possible, this means that there exists an S such that till the ti
# Intuition\nSo first afall ask yourself what is range of second, considering that the answer is possible, this means that there exists an S such that till the time we can reach S, we can make every nums = 0, and also Mark all the indexes. OK\n\nNow let us think my answer S to be 4, this means that till my S = 4, i need to mark all my making each of the element equal to 0,\nWhat we can do is greedy mark the last position of the occurance of the number in my lastIndex vector till second s.\nLike this what we can do is, greedy count the power that we can have and only use whenutmost needed, like this if we are able to mark all the numbers, then we would return true. else false.\n\n# Complexity\n- Time complexity:\nO(mlogm)\n\n- Space complexity:\nO(n*m)\n\n# Code\n```\nclass Solution {\nprivate:\n    bool isPossible(vector<int> nums, vector<int> &changeIndice, int s){\n        int n = nums.size();\n        // keep the last forceful index \n        vector<int> lastIndex(n, -1);\n        for(int i=0; i<=s; i++){\n            lastIndex[changeIndice[i]] = i;\n        }\n\n        int power = 0;\n        int completed = 0;\n\n        for(int i=0; i<=s; i++){\n            if(i == lastIndex[changeIndice[i]]){\n                power -= nums[changeIndice[i]];\n                if(power < 0) return false;\n                completed++;\n            }\n            else{\n                power++;\n            }\n        }\n        return completed == n;\n    }\npublic:\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {\n        int n = nums.size();\n        int m = changeIndices.size();\n\n        for(auto &el: changeIndices) el--;\n\n        int l = 0;\n        int h = m-1;\n        int s = -1;\n        while(l <= h){\n            int mid = (l + (h-l)/2);\n\n            if(isPossible(nums, changeIndices, mid)){\n                s = mid;\n                h = mid - 1;\n            }\n            else l = mid+1;\n        }\n        return s+1 == 0 ? -1 : s+1;\n    }\n};\n```
['Binary Search', 'Greedy', 'C++']