Problem

You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively.

Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.

In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:

  • Choose an index i in the range [1, n] and decrement nums[i] by 1.
  • Set nums[changeIndices[s]] to any non-negative value.
  • Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i.
  • Do nothing.

Return _an integer denoting theearliest second in the range _[1, m]_whenall indices in _nums can be marked by choosing operations optimally, or-1 if it is impossible.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


    
    
    Input: nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
    Output: 6
    Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
    Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
    Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
    Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
    Second 4: Mark index 1, since nums[1] is equal to 0.
    Second 5: Mark index 2, since nums[2] is equal to 0.
    Second 6: Mark index 3, since nums[3] is equal to 0.
    Now all indices have been marked.
    It can be shown that it is not possible to mark all indices earlier than the 6th second.
    Hence, the answer is 6.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


    
    
    Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
    Output: 7
    Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
    Second 1: Mark index 1, since nums[1] is equal to 0.
    Second 2: Mark index 2, since nums[2] is equal to 0.
    Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
    Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
    Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
    Second 6: Mark index 3, since nums[3] is equal to 0.
    Second 7: Mark index 4, since nums[4] is equal to 0.
    Now all indices have been marked.
    It can be shown that it is not possible to mark all indices earlier than the 7th second.
    Hence, the answer is 7.

Example 3

1
2
3
4
5
6
7
8


    
    
    Input: nums = [1,2,3], changeIndices = [1,2,3]
    Output: -1
    Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. 
    Hence, the answer is -1.

Constraints

  • 1 <= n == nums.length <= 5000
  • 0 <= nums[i] <= 10^9
  • 1 <= m == changeIndices.length <= 5000
  • 1 <= changeIndices[i] <= n

Solution

Method 1 – Greedy with Min Heap

Intuition

We want to mark all indices in nums as soon as possible. Since we can set any index to any non-negative value at the specified seconds, we can use a min-heap to always mark the index that can be marked the earliest. We simulate the process, always marking the index with the smallest required time, and use the set operation optimally to reset values if needed.

Approach

  1. For each index, track the last second it can be marked (i.e., when changeIndices[s] == i for some s).
  2. Use a min-heap to always pick the index that can be marked the earliest.
  3. For each second, if possible, mark an index whose value is zero, or use the set operation to reset an index to zero if it cannot be marked otherwise.
  4. Continue until all indices are marked or time runs out.
  5. Return the earliest second when all indices are marked, or -1 if impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import heapq
class Solution:
    def earliestSecondToMarkIndices(self, nums: list[int], changeIndices: list[int]) -> int:
        n, m = len(nums), len(changeIndices)
        last = [-1] * n
        for i, idx in enumerate(changeIndices):
            last[idx - 1] = i
        if -1 in last:
            return -1
        heap = []
        for i in range(n):
            heapq.heappush(heap, (last[i], i))
        marked = set()
        used = [False] * n
        for t in range(m):
            while heap and heap[0][0] < t:
                heapq.heappop(heap)
            if not heap:
                break
            _, i = heapq.heappop(heap)
            if nums[i] == 0 and not used[i]:
                marked.add(i)
                used[i] = True
            else:
                nums[i] = 0
                marked.add(i)
                used[i] = True
            if len(marked) == n:
                return t + 1
        return -1

Complexity

  • ⏰ Time complexity: O(m log n), where m is the length of changeIndices and n is the length of nums. Each heap operation is O(log n).
  • 🧺 Space complexity: O(n), for the heap and auxiliary arrays.