C++ Binary Search Intuition
Intuition\n Describe your first thoughts on how to solve this problem. \n\nwhat does changeIndices array have ?\nit have index of nums arrays\n\nwhat dose time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n**what does changeIndices array have ?**\nit have index of nums arrays\n\n**what dose time (each second (s)) represent ?**\nindex of changeIndices;\n\n**What we can do at second (s)?**\n\neither we can decrease any nums[i];\nor if( nums[changeIndices[s]] == 0)\n   we can mark nums[i];\n\n**target ?**\n\nmark all index of nums[i] as early as possible\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nconsider 0 index array\nchangeIndices = [1,1,1,1,**2**,1,**1**,**0**]\n\nlast occurance of index in changeIndices (in bold)\nindex.   last occurance \n0           7\n1           6\n2           4\n\nthis is clear that we have to somehow mark nums[i] till the last occurance of "i index" in changeIndices to do so nums[i] should be zero before last occurance of "i index" in changeIndices\n\neg to mark nums[0] the nums[0] == 0 till index 7th second\n\n**who to check if we can make nums[i] == 0 till kth second?  -> method xxx**\n\n(k-(count of nums yet to be marked except nums[i] )-(sum of nums yet to be marked))>=0\n\nNow keep on decreasing the size of changeIndices from last (using binary search )\n\nfor each new changeIndices use method xxx and check whether new changeIndices can mark each nums[i]\n\n\n# Complexity\n- Time complexity: O(nlog m)\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    typedef long long int ll;\n    bool check (vector<int> & ind , int last, int n, ll sum,vector<int>& nums)\n    {\n       int vis[n];\n       memset(vis,0,sizeof(vis));\n       \n       int count = n; // count of nums yet to be marked \n\n       for(int i=last;i>=0;i--)\n       {\n          if(!vis[ind[i]])\n          {\n              vis[ind[i]]=1;\n\n              if((i-count-sum+1)>=0)   //(k-(count of nums yet to be marked except nums[i] )-(sum of nums yet to be marked))>=0\n\n // +1 bcz we want "count of nums yet to be marked except nums[i]"\n              {\n                 count--;\n                 sum -= nums[ind[i]];\n              }\n              else\n               return false;\n          }\n       }\n       return count>0?false:true;\n    }\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& ind) {\n        \n        int n = nums.size();\n        int m = ind.size();\n        ll sum = 0;\n\n        for(int i=0;i<n;i++)\n            sum+=nums[i];\n\n\n        for(int i=0;i<m;i++){\n            ind[i]--;\n        }\n\n        int ans = m+1;\n        int begin = 0;\n        int last = m-1; // end of changeIndices array\n\n        while(begin <=last)\n        {\n             int mid = (begin + last)/2;\n            cout<<mid<<" ";\n             if(check(ind,mid,n,sum,nums)) // true -> new changeIndices array can mark all nums[i]\n             {\n                 ans = min(ans,mid+1);\n                 last=mid-1;\n             }\n             else\n             {\n                 begin = mid+1;\n             }\n        }\n\n        return ans > m ?-1:ans;\n    }\n};\n```
['Binary Search', 'C++']