[Python3] Binary Search | Clean & Concise | O(mlogm)
Approach\nPython 3 solution to the approach given in @k487237\'s post.\n Describe your approach to solving the problem. \n\n# Complexity\n- Time complexity: O(m
# Approach\nPython 3 solution to the approach given in [@k487237\'s post](https://leetcode.com/problems/earliest-second-to-mark-indices-i/solutions/4778573/c-binary-search-easy-understand-o-mlogm/).\n<!-- Describe your approach to solving the problem. -->\n\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        n, m = len(nums), len(changeIndices)\n        start, end = 0, m - 1\n        while start + 1 < end:\n            mid = (start + end) // 2\n            if self.check(nums, changeIndices, mid):\n                end = mid\n            else:\n                start = mid\n        if self.check(nums, changeIndices, start):\n            return start + 1\n        elif self.check(nums, changeIndices, end):\n            return end + 1\n        else:\n            return -1\n    \n    def check(self, nums, changeIndices, index):\n        tmp, seen = [], set()\n        for i in range(index, -1, -1):\n            if changeIndices[i] not in seen:\n                seen.add(changeIndices[i])\n                tmp.append((changeIndices[i], i))\n        if len(tmp) < len(nums):\n            return False\n        tmp = tmp[::-1]\n        curr = 0\n        for changeIndex, index in tmp:\n            curr += nums[changeIndex - 1]\n            if index < curr:\n                return False\n            curr += 1\n        return True\n```
['Python3']