[100%] A O(m) greedy solution with explanation & codes
Motivation\nI prepare this post to share a O(m) solution. \n\nAlgorithm\nI start to solve this problem following a binary search manner. As you could found in o
**Motivation**\nI prepare this post to share a ***O(m)*** solution. \n\n**Algorithm**\nI start to solve this problem following a binary search manner. As you could found in other posts, we just need to solve a similar problem: **Given two arrays nums & changeIndices, can we mark all the indices?**.\n\nI use a greedy approach. We scan **changeIndices** left to right to remember the last time to mark **changeIndices[y]** as **dp[changeIndices[y]]=y**. Then we can sort the indices **x=1, ..., n** w.r.t. the values of **dp[x]** and achieve a list: **greedy={(x_i, dp[x_i])}, i=1,...,n**. We can successfully mark all indices, as long as **Condition i: nums[x_1]+...+nums[x_i]+i<=dp[x_i]** is holded for every **i=1,...,n**.\n\nDo we really need to sort? Or do we really need to maintain the list **greedy**? ***No***. We use **two pointers cur & rem**. **cur**  is used to update the value of **dp**, or you can image that we associate the index **changeIndices[cur]** to **cur**. And **rem** is used to mark indices, when **changeIndices[rem]** is associated to **rem**. Meanwhile, we calculate the **sum** of **nums[i]** for all **i** marked and counter of indices already marked as **cnt**.\n\nThe algorithm uses two loops:\n* Outer Loop: we scan **changeIndices** from left to right, **cur=1,...,m**.\n\t* Let **i=changeIndices[cur]**\n\t* If **dp[i]>=0** and **dp[i]<rem**,  then the index **i** is marked. We need to reset the index **i**\n\t\t* **cnt-=1**\n\t\t* **sum-=nums[i]**\n\t* We assign **dp[i]=cur**\n\t* Inner Loop: we scan **changeIndices** from left to right, **rem=1,...,cur**.\n\t\t* Let **j=changeIndices[rem]**\n\t\t* If **dp[j]==rem**, we try to mark the index **j** at the time of **rem**\n\t\t\t* If **sum+cnt+nums[j]+1<=rem** (this is variant of the aforementioned conditon), we mark **j**\n\t\t\t\t* **cnt+=1**\n\t\t\t\t* **sum+=nums[j]**\n\t\t\t* otherwise, break the inner loop\n\t* If **cnt==n**, **Done**.\n\n**Complexity**\n```\nTime: O(m)\nRuntime: 0 ms, faster than 100.00% of C++ online submissions for Earliest Second to Mark Indices I.\nSpace: O(n)\nMemory Usage: 39.4 MB, less than 99.30% of C++ online submissions for Earliest Second to Mark Indices I.\n```\n![image](https://assets.leetcode.com/users/images/ee9394cc-0bbd-4662-ada5-29a8cf98150d_1709270445.6346366.png)\nhttps://leetcode.com/submissions/detail/1190303910/\nhttps://leetcode.com/submissions/detail/1190299952/\nhttps://leetcode.com/submissions/detail/1188450617/\n\n**Code**\n*Node*: we rename some variables for short.\n```\nint dp[2000];\nclass Solution {\npublic:\n    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& tars) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n        long sum=0;\n        int n=nums.size(), m=tars.size(), cur=0, rem=0, cnt=0;\n        for(int i=0; i<n; dp[i++]=INT_MAX) {}\n        for(; cur<m && cnt<n; ++cur) {\n            if(dp[--tars[cur]]<rem) {\n                --cnt;\n                sum-=nums[tars[cur]];\n            }\n            dp[tars[cur]]=cur;                \n            for(; cnt<n && rem<=cur; ++rem) {\n                if(dp[tars[rem]]==rem) {\n                    if(sum+cnt+nums[tars[rem]]<=rem) {\n                        sum+=nums[tars[rem]];\n                        ++cnt;                        \n                    } else {\n                        break;\n                    }\n                }\n            }\n        }\n        return cnt==n? rem : -1;\n    }\n};\n```\n
['Two Pointers', 'Greedy']