binary search on answers
Intuition\n Describe your first thoughts on how to solve this problem. \nBinary Search\n\n# Approach\n Describe your approach to solving the problem. \nStore al
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinary Search\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStore all the last times of marking in a map for every index by iterating the change indices array backwards. Calculate if it is possible to mark all the indices in the given time and find last time using BS\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->0(mlog m)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(m)\n\n# Code\n```\nclass Solution {\npublic:\nbool isPossible(vector<int>& nums,vector<int>& c,int mid){\n    set<int> st;\n    map<int,int> last;\n    for (int i=mid;i>=0;i--){\n        if (!st.count(c[i])){\n            st.insert(c[i]);\n            last[i]=c[i];\n        }\n    }\n\n    if (last.size()<nums.size()) return false;\n    int curr=-1;\n    for (auto it:last){\n        int t=it.first;\n        int ind=it.second;\n        int val=nums[ind];\n        if (val+curr<t){\n            curr=curr+val+1;\n        } else return false;\n    }\n    return true;\n}\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& c) {\n        int m=c.size();\n        for (int i=0;i<m;i++){\n            c[i]--;\n        }\n        int l=0,r=m-1,ans=1e9,n=nums.size();\n        while (l<r){\n            int mid=l+(r-l)/2;\n            if (isPossible(nums,c,mid)){\n                ans=min(ans,mid+1);\n                r=mid;\n            }\n            else l=mid+1;\n        }\n        if (isPossible(nums,c,l)) ans=min(ans,l+1);\n        if (ans==1e9) return -1;\n        else return ans;\n    }\n};\n```
['C++']