☑️☑️ Binary search solution with explanation☑️☑️
Intuition\n Describe your first thoughts on how to solve this problem. \nif the answer is possible at index i then it is also possible at i + 1 , i + 2 and so o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nif the answer is possible at index i then it is also possible at i + 1 , i + 2 and so on hence we can use this characterstic of the problem to use binary search \n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will binary search and our search space will be 0 till changesIndices size. \nNow we need a predicate function to use Binary Search \n\n**PREDICATE FUNCTION**\n\nFor any index mid , we will first store the last index at which we can mark occurence of element of nums with in the range [0 , mid] . Now till these last indexes the element must have zero value only then we can mark it . So we will iterate over the changesIndices and indexes which have been chosen as the mark point should be evaluated.\n\nFor more clear explanation you can refer to comments in the code\n\n# Complexity\n- Time complexity:O(NlogN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    bool check( int mid , vector<int>&changesIndices , vector<int>&nums)\n    {   \n        \n        \n        // this will store the lastIndex of all element of nums till \n        // which that element must have became zero \n        map<int,int>lastIndex;\n             \n        set<int>st;\n\n        for( int j = 0 ; j <= mid ; j++)\n        {\n            lastIndex[changesIndices[j]-1] = j; \n        }\n\n        // this store all the indexes which are choosen as a lastindex \n        // for element of nums\n        for( auto ele : lastIndex)\n        {\n            st.insert(ele.second);    \n        }\n\n        int sumSoFar = 0;\n        bool possible = true;\n        int covered = 0;\n        for( int j = 0 ; j <= mid ; j++)\n        {   \n            // if current index is present in set it means it is chosen as \n            // the point at which the current element should be marked \n            // hence check if we have enough time so far to get this \n            // element to be converted to zero so that it can be marked now\n            if(st.find(j) != st.end())\n            {   \n                if(sumSoFar < nums[changesIndices[j]-1])\n                {\n                    possible = false;\n                }\n                else\n                {\n                    sumSoFar -= nums[changesIndices[j]-1];\n                    covered += 1;\n                }\n            }\n            else\n            {\n                sumSoFar += 1;\n            }\n        }\n        // if sum becane negative return false\n        if(sumSoFar < 0) possible = false;\n        \n        // if we have marked all element then return true\n        if(possible && nums.size() == covered) return true;\n        \n        // if we are not succesful in marking all element till this index then\n        //  also return false\n        return false;\n    }\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changesIndices) {\n        // The pattern for our search looks like this \n        // F F F F T T T T \n        // we need to find first true\n        int start = 0;\n        int end = changesIndices.size();\n\n        while( start < end)\n        {\n            int mid = start + (end-start)/2;\n\n            if(check( mid , changesIndices , nums) == true)\n            {\n                end = mid;\n            }\n            else\n            {\n                start = mid + 1;\n            }\n        }\n\n        return end == changesIndices.size() ? -1 : end + 1;\n    }\n};\n```
['C++']