Solution Approach

The solution uses binary search combined with a greedy checking function to find the minimum time needed.

Binary Search Template Setup

We use the standard binary search template to find the first time that is sufficient:

left, right = 1, m
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if can_mark_all(mid):  # feasible(mid) = "can mark all indices in mid seconds"
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index if first_true_index != -1 else -1

The feasible(t) function returns True if time t is sufficient to mark all indices. This directly fits the template pattern.

The Feasible Function Implementation

For a given time t, we verify if all indices can be marked within t seconds:

1. Build the last dictionary:

   last = {i: s for s, i in enumerate(changeIndices[:t])}

   This maps each index to its last occurrence position within the first t elements.

2. Traverse through the first t seconds: For each second s and its corresponding index i:

3. Decision at each second:

   • If last[i] == s (this is the last chance to mark index i):

     • Check if we have enough decrements: if decrement < nums[i - 1]: return False
     • If sufficient, consume the decrements: decrement -= nums[i - 1]
     • Mark this index: marked += 1

   • Otherwise (not the last chance for this index):

     • Add this second to our decrement budget: decrement += 1

4. Final validation:

   return marked == len(nums)

Time Complexity:

• Binary search runs O(log m) iterations
• Each check function runs in O(t) time where t ≤ m
• Overall: O(m log m)

Space Complexity: O(n) for the last dictionary storing at most n unique indices.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

• nums = [3, 2, 3] (1-indexed, so index 1 has value 3, index 2 has value 2, index 3 has value 3)
• changeIndices = [1, 3, 2, 2, 2, 2, 3] (length m = 7)

Goal: Find the earliest second when all three indices can be marked.

Step 1: Binary Search Setup We'll search for the minimum time in range [1, 8). Let's check if time t = 4 is sufficient.

Step 2: Check if t = 4 works

First, we look at changeIndices[:4] = [1, 3, 2, 2] and build the last dictionary:

• Index 1 appears at position 0 (last occurrence)
• Index 3 appears at position 1 (last occurrence)
• Index 2 appears at positions 2 and 3 (last at position 3)

So last = {1: 0, 3: 1, 2: 3}

Now we traverse second by second:

Second 0 (changeIndices[0] = 1):

• This is the last chance to mark index 1 (last[1] = 0)
• We need nums[0] = 3 decrements to reduce it to 0
• Current decrement = 0, but we need 3
• Return False - time 4 is insufficient!

Step 3: Check if t = 7 works

Looking at changeIndices[:7] = [1, 3, 2, 2, 2, 2, 3]:

• Build last = {1: 0, 3: 6, 2: 5}

Traverse second by second:

Second 0 (changeIndices[0] = 1):

• Last chance for index 1 (last[1] = 0)
• Need 3 decrements, have 0
• Return False - Still insufficient!

Actually, let's reconsider with a better strategy. Since index 1 must be marked at second 0, we need to have already decremented it to 0 before we start. This is impossible.

Step 4: Reanalyze the problem

Looking more carefully at the full changeIndices = [1, 3, 2, 2, 2, 2, 3]:

• We need at least 3 + 2 + 3 = 8 total operations (decrements) plus 3 marks
• That's 11 operations minimum, but we only have 7 seconds
• Return -1 - It's impossible!

Let's try a simpler example where it's actually possible:

Modified Example:

• nums = [2, 1, 1]
• changeIndices = [1, 2, 3, 2, 1, 3]

Check if t = 6 works:

Build last = {1: 4, 2: 3, 3: 5} (using 0-based indexing)

Second 0 (index 1): Not last occurrence, decrement = 1 Second 1 (index 2): Not last occurrence, decrement = 2 Second 2 (index 3): Not last occurrence, decrement = 3 Second 3 (index 2): Last chance for index 2!

• Need nums[1] = 1 decrement
• Have 3 decrements available
• Use 1, mark index 2: decrement = 2, marked = 1

Second 4 (index 1): Last chance for index 1!

• Need nums[0] = 2 decrements
• Have 2 decrements available
• Use 2, mark index 1: decrement = 0, marked = 2

Second 5 (index 3): Last chance for index 3!

• Need nums[2] = 1 decrement
• Have 0 decrements available
• Return False - Not enough!

Since t = 6 fails, binary search would try larger values. Eventually it would find that we need more time to accumulate enough decrements before marking all indices.

Time and Space Complexity

Time Complexity: O(m × log m)

The algorithm uses binary search on the range [1, m+1] where m is the length of changeIndices. The binary search performs O(log m) iterations. For each iteration, the check function is called, which:

• Creates a dictionary last by iterating through changeIndices[:t], taking O(t) time where t ≤ m
• Iterates through changeIndices[:t] once more to validate the marking process, taking O(t) time

Since t can be at most m, each call to check takes O(m) time. Therefore, the total time complexity is O(m × log m).

Space Complexity: O(n)

The space complexity comes from:

• The last dictionary which stores at most n key-value pairs (where n is the length of nums), since there are n unique indices that can be marked
• The local variables decrement and marked use O(1) space

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template

Pitfall: Not using the standard binary search template with first_true_index tracking.

Common mistakes:

# WRONG: Using while left < right with different update rules
while left < right:
    mid = (left + right) >> 1
    if can_mark_all(mid):
        right = mid
    else:
        left = mid + 1
return left if left <= m else -1

Correct approach using template:

# CORRECT: Standard template with first_true_index
left, right = 1, m
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if can_mark_all(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index if first_true_index != -1 else -1

2. Index Confusion Between 0-based and 1-based Systems

The most common pitfall in this problem is mixing up the indexing systems:

• nums array uses 0-based indexing
• changeIndices contains 1-based index values

Pitfall Example:

# WRONG: Forgetting to convert from 1-based to 0-based
required_decrements = nums[current_index]  # Should be nums[current_index - 1]

Solution:

required_decrements = nums[current_index - 1]  # Correct conversion

3. Not Handling Indices That Never Appear

Pitfall Example: If an index from nums never appears in changeIndices[:seconds], it won't be in the last_occurrence dictionary, leading to incorrect results.

Solution: The algorithm naturally handles this because marked_count won't reach len(nums) if some indices never appear.

4. Incorrect Greedy Logic for Accumulating Decrements

Pitfall Example:

# WRONG: Accumulating decrements even when marking
if last_occurrence[current_index] == current_second:
    available_decrements -= nums[current_index - 1]
    available_decrements += 1  # WRONG: shouldn't add here

Solution: Only accumulate decrements when NOT marking:

if last_occurrence[current_index] == current_second:
    available_decrements -= nums[current_index - 1]
    marked_count += 1
else:
    available_decrements += 1  # Only add when not marking