Description
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 decrementnums[i]
by1
. - Set
nums[changeIndices[s]]
to any non-negative value. - Choose an index
i
in the range[1, n]
, wherenums[i]
is equal to0
, and mark indexi
. - Do nothing.
Return an integer denoting the earliest second in the range [1, m]
when all indices in nums
can be marked by choosing operations optimally, or -1
if it is impossible.
Example 1:
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:
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:
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] <= 109
1 <= m == changeIndices.length <= 5000
1 <= changeIndices[i] <= n
Solution
Python3
class Solution:
def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
N, M = len(nums), len(changeIndices)
if M < N: return -1
firsts = {}
for i, ci in enumerate(changeIndices):
ci -= 1
if nums[ci] > 0 and ci not in firsts:
firsts[ci] = i
firsts_inv = {i : ci for ci, i in firsts.items()}
def good(k):
pq = []
mark = 0
for i in range(k - 1, -1, -1):
if i in firsts_inv:
heappush(pq, nums[firsts_inv[i]])
if mark > 0:
mark -= 1
else:
heappop(pq) # sacrifice the lowest we have picked up earlier
mark += 1 # add back the mark as the "set" operation is voided
else:
mark += 1
# sum(nums) - sum(pq) refers to the sum of the numbers we havent cleared
# N - len(pq) refers to the total number of operations we have yet to "mark" it
return sum(nums) - sum(pq) + N - len(pq) <= mark
left, right = N, M + 1
while left < right:
mid = left + (right - left) // 2
if good(mid):
right = mid
else:
left = mid + 1
if left == M + 1: return -1
return left