Python | Binary Search (m * log(m)) | Iterate from Back
Complexity\n- Time complexity: O(m * log(m))\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(m)\n Add your space complexity here, e.g. O(n)
# Complexity\n- Time complexity: O(m * log(m))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:\n        left, right = 0, len(changeIndices)+1\n        while left < right:\n            mid = left + (right-left)//2\n            if self.isOK(mid, nums, changeIndices):\n                right = mid\n            else:\n                left = mid+1\n        if left == len(changeIndices)+1: return -1\n        return left\n            \n            \n    def isOK(self, steps, nums, changeIndices):\n        n = len(nums)\n        visited = set()\n        ops = 0\n        for i in range(steps-1, -1, -1):\n            j = changeIndices[i]\n            if j not in visited:\n                ops += nums[j-1]\n                visited.add(j)\n            elif ops:\n                ops -= 1\n        if len(visited) < n: return False\n        return ops == 0\n```\n\n# Code Explain\nThe basic structure of the solution is binary search. We could guess whether `mid` seconds is enough to mark all indices.\n\n```python\nleft, right = 0, len(changeIndices)+1\nwhile left < right:\n    mid = left + (right-left)//2\n    if self.isOK(mid, nums, changeIndices):\n        right = mid\n    else:\n        left = mid+1\nif left == len(changeIndices)+1: return -1\nreturn left\n```\n\nThen the next question is how to check is it possible to mark all indices within seconds. That\'s think about how to mark all indices?\n- All indices have to be in `changeIndices`.\n- When we meet last index in `changeIndices`, `nums[index]` has to be zero.\n\nThe point is that before the last `check point`, `nums[index]` has to be zero! After that moment, decreasing on index is meaningless. So why not just iterate from last second to first to delay mark operation of each index until we meet last `check point` and to see is there enough seconds to make all numbers equal to zero.\n- If we have not seen index `j`, it means it\'s the last `check point`. We add value of `nums[index]` to `ops`, assuming we could perform mark operation on `j` at this second. Here `ops` means sum of decreasing operations we should perform.\n- Otherwis, we try to decrease a number.\n```\ndef isOK(self, steps, nums, changeIndices):\n    n = len(nums)\n    visited = set()\n    ops = 0\n    for i in range(steps-1, -1, -1):\n        j = changeIndices[i]\n        if j not in visited:\n            ops += nums[j-1]\n            visited.add(j)\n        elif ops:\n            ops -= 1\n    if len(visited) < n: return False\n    return ops == 0\n```
['Binary Search', 'Python3']