Binary Search on Time || beats 99%
Intuition\n Describe your first thoughts on how to solve this problem. \nwe create a possible function that tells us if it is possible to markall indices with g
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe create a possible function that tells us if it is possible to markall indices with given time.If it is then we store out answer and try to reduce the time using BS, otherwise we increase the time (standard BS) \n# Approach\n<!-- Describe your approach to solving the problem. -->\nconsider an index i of the changeIndices, it indicates that the last time to mark index changeIndices[i]-1 in the nums array is i.\n\nfor a given time in the possible function, we create a lastime array which gives lastime[i]- the lastime to mark index i.\nthen we go over all possible times and do a decrement operation if the current time is not the last time to mark some index, otherwise we have to mark index changeIndices[i]-1. if the value at that index is greater than ops then we return false. at the end we check if the number of marked element equals total no of element and return accordingly.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(MlogM)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nclass Solution {\npublic:\n    bool possible(int time,vector<int>& nums, vector<int>& changeIndices){\n        vector<int>lastime(nums.size(),-1);//lastime to mark each index in nums\n        for(int i=0;i<time;i++){\n            lastime[changeIndices[i]-1]=i;\n        }\n\n        int ops=0;\n        int marked=0;\n        for(int i=0;i<time;i++){\n            if(i==lastime[changeIndices[i]-1]){ //this is the lastime to mark index changeIndices[i]-1\n                if(nums[changeIndices[i]-1]>ops) return false;\n                ops-=nums[changeIndices[i]-1];\n                marked++;\n            }else{\n                ops++;\n            }\n        }\n        return marked==nums.size();\n    }\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;\n        int ans;\n        while(l<=r){\n            int mid=l+(r-l)/2;\n            if(possible(mid,nums,changeIndices)){\n                ans=mid;\n                r=mid-1;\n            }else{\n                l=mid+1;\n            }\n        }\n        return ans<=m?ans:-1;\n    }\n};\n```
['C++']