🤯 Binary Search + Min-Heap || Greedy || O(n*logn*logm) Solution || Beats 100% Time👏 || C++
Intuition:\n- We know that our answer will lie within the range [1,m] , if it exists.\n- Thus, the approach that comes in our mind is to binary search within th
# Intuition:\n- We know that our answer will lie within the range [1,m] , if it exists.\n- Thus, the approach that comes in our mind is to binary search within this range, and find the optimum (least possible) time where we can mark all the indices [1,n].\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- We use a min-heap in order to keep track of the next element that we need to reduce to 0; \n- As we have to reduce a number latest by its last occurence in the subarray that we are considering , so that we can mark it at that point ; Thereby, we use a min-heap.\n- If it is not possible to reduce a number before its last occurence in the range[1,mid] , we return false as we\'ll never be able to mark all indices from [1,n] , and move our binary search space towards the right, making our subarray [1,mid] more relaxed;\n- However, If that\'s not the case, we return true and reduce our binary search space towards the left side.\n\n# Complexity\n- Time complexity:\nO(logm * (n + n*logn))\n\n- Space complexity:     \nO(n)\n\n---\n\n\n> Upvote if it was helpful \uD83E\uDDE7\n\n---\n\n# Code\n```\n#define ll long long\n\nclass Solution {\npublic:\n    \n    bool isPossible(vector<int>& nums, vector<int>& ci,int n,int m,ll sum,int ind){\n        if(ind<sum-1) return false;\n        \n        unordered_map<int,int> mp;\n        for(int i=0;i<=ind;i++) mp[ci[i]]=i;\n        if(mp.size()!=n) return false;\n        \n        int time=0;\n        //{last occ,time};\n        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;\n        for(auto it:mp) pq.push({it.second , nums[it.first]});\n        \n        while(!pq.empty()){\n            int last=pq.top().first , t=pq.top().second;\n            pq.pop();\n            if(last-time<t) return false;\n            time+=t+1;\n        }\n        \n        return true;\n    }\n    \n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& ci) {\n        int n=nums.size() , m=ci.size();\n        for(int i=0;i<m;i++) ci[i]--;\n        \n        ll mini=0 , maxi=m-1 , out=-1;\n        ll sum=0;\n        for(auto num:nums) sum+=num;\n        \n        while(mini<=maxi){\n            ll mid=mini+((maxi-mini)>>1);\n            if(isPossible(nums,ci,n,m,sum,mid)){\n                out=mid+1;\n                maxi=mid-1;\n            }\n            else mini=mid+1;\n        }\n        \n        return out;\n    }\n};\n```\n\n---\n\n\n> Thanks for Reading, Upvote if it helped \uD83C\uDF97\n\n---\n\n\n![upvote xd.jpeg](https://assets.leetcode.com/users/images/0b8cb50e-8169-4a2d-ba45-90484a3c195d_1708835133.6360857.jpeg)\n
['Binary Search', 'Greedy', 'Heap (Priority Queue)', 'C++']