Greedy | python
Intuition\nThe approach follows a greedy strategy.\n\n# Approach\nGiven the constraints, we can iterate over all the seconds and check if it\'s possible to mark
# Intuition\nThe approach follows a greedy strategy.\n\n# Approach\nGiven the constraints, we can iterate over all the seconds and check if it\'s possible to mark all the indices.\n\nTo determine if we can mark all the indices with $X$ seconds, we use a greedy approach. Since marking depends on the existence of index $i$ in `changeIndices`, the optimal strategy is to delay marking index $i$ until the last possible second. In other words, mark index $i$ at the maximum second $j$ such that `changeIndices[j] == i`. This allows us to accumulate the maximum number of operations of the first type.\n\nIt doesn\'t matter which index $i$ we decrease when $j$ doesn\'t correspond to any of the last occurrences. We can simply accumulate and, when we reach the last occurrence of $i$ in `changeIndices`, validate that we have enough operations to set `nums[i] = 0`.\n\nIn simpler terms, the algorithm works as follows:\n\n- Iterate over all seconds from $1$ to $M$ as possible answers or apply binary search over the answer.\n- For each possible answer ($\\text{ans}$), check if we can mark all the indices:\n    - Find the last occurrence for each index $i$ in $[0, n-1]$ let\'s call $last$. If some index doesn\'t have an occurrence, it\'s impossible to solve for that possible answer.\n    \n    - Iterate from $1 \\leq s \\leq \\text{ans}$ and check if $s$ corresponds to the last occurrence of some $i$ in `nums` or if $s == last[changeIndices[s]]$ :\n        - If not, increment $cnt$ by $1$ (where $cnt$ is the number of operations of type $1$ that we can make).\n        - If yes, check if your counter is big enough to set `nums[changeIndices[s]] = 0`, i.e., $cnt \\geq \\text{nums[changeIndices[s]]}$, and consume those operations, i.e., $cnt -= \\text{nums[changeIndices[s]]}$. Also, increment $mark$ by $1$.\n    - Finally, check if we consumed/mark all the last occurrences, i.e., $idx == n$. If this condition is met, $ans$ is valid and we can return it.\n\n# Complexity\n- Time complexity: $O(M^2)$. This can be reduced to $O(M \\log{M})$ using binary search over the answer, but it\'s not necessary given the provided limits.\n# Code\n```python\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums: List[int], CI: List[int]) -> int:\n        m = len(CI)\n        n = len(nums)\n        \n        CI = [x-1 for x in CI]\n\n        \n        for ans in range(1,m+1):\n            last = [-1]*n\n            \n            for i in range(ans):\n                last[CI[i]] = i\n\n            if last[0] ==-1:continue \n                \n            mark = 0\n            cnt = 0 \n            \n            for s in range(ans):\n                if s == last[CI[s]]: \n                    if cnt>=nums[CI[s]]:\n                        cnt-=nums[CI[s]]\n                        mark+=1\n                    else: \n                        break\n                else: \n                    cnt+=1 \n                    \n            \n            if mark == n: \n                return ans\n            \n\n        return -1\n```\n\n# With Binary search\n```python\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums: List[int], CI: List[int]) -> int:\n        m = len(CI)\n        n = len(nums)\n        \n        CI = [x-1 for x in CI]\n\n        def check(ans):\n            last = [-1]*n\n            \n            for i in range(ans):\n                last[CI[i]] = i\n\n            if last[0] ==-1:\n                return False \n                \n            mark = 0\n            cnt = 0 \n            \n            for s in range(ans):\n                if s == last[CI[s]]: \n                    if cnt>=nums[CI[s]]:\n                        cnt-=nums[CI[s]]\n                        mark+=1\n                    else: \n                        return False\n                else: \n                    cnt+=1 \n                    \n            \n            return mark == n\n\n            \n        l,r = (0,m+1)\n\n        while l+1<r:\n            mid = (l+r)>>1\n            if check(mid): r = mid \n            else: l = mid \n\n        return -1 if r == m+1 else r\n```
['Python3']