PYTHON || Runtime 103 ms Beats 99.73% of users with Python3
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves determining the earliest moment at which a certain number of indic
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves determining the earliest moment at which a certain number of indices can be marked based on a sequence of operations. The initial intuition is to simulate the process by iteratively marking indices and updating the available points. The goal is to find the earliest moment when the required number of indices can be marked.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCalculate the minimum number of turns required to mark all indices. This is achieved by summing up the values in the nums array and adding the length of the array (n).\nIf the minimum turns exceed the number of change indices (m), it is impossible to mark all indices, so return -1.\nIterate through the possible turns starting from the minimum turns up to m + 1.\nFor each turn, simulate the marking process by maintaining a set of marked indices and updating the available points.\nCheck if it is possible to mark all required indices in the given number of turns. If possible, return the current number of turns.\nIf no valid solution is found, return -1.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m\u22C5n), where m is the number of change indices and n is the length of the nums array. The algorithm iterates through each possible turn and updates the marked indices set.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m), where m is the number of change indices. The marked indices set stores the indices that have been marked.\n\n# Code\n```\nclass Solution:\n    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:\n        n = len(nums)\n        m = len(changeIndices)\n        \n        minTurns = sum(nums) + n\n        \n        if minTurns > m:\n            return -1\n        \n        for turns in range(minTurns, m + 1):\n            marked = set()\n            points = minTurns\n            possible = True\n            \n            for turn in range(turns - 1, -1, -1):\n                if points > turn + 1:\n                    possible = False\n                    break\n                \n                changeIndex = changeIndices[turn]\n                \n                if changeIndex not in marked:\n                    marked.add(changeIndex)\n                    \n                    points -= (nums[changeIndex - 1] + 1)\n            \n            if possible and points == 0:\n                return turns\n            \n        return -1\n```
['Array', 'Hash Table', 'Two Pointers', 'Binary Search', 'Greedy', 'Tree', 'Binary Tree', 'Python', 'Python3']