Watch 9 video solutions for Earliest Second to Mark Indices I, a medium level problem involving Array, Binary Search. This walkthrough by Aryan Mittal has 4,500 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i in the range [1, n] and decrement nums[i] by 1.nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].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 = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1] Output: 8 Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices: Second 1: Choose index 1 and decrement nums[1] by one. nums becomes [1,2,0]. Second 2: Choose index 1 and decrement nums[1] by one. nums becomes [0,2,0]. Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [0,1,0]. Second 4: Choose index 2 and decrement nums[2] by one. nums becomes [0,0,0]. Second 5: Mark the index changeIndices[5], which is marking index 3, since nums[3] is equal to 0. Second 6: Mark the index changeIndices[6], which is marking index 2, since nums[2] is equal to 0. Second 7: Do nothing. Second 8: Mark the index changeIndices[8], which is marking index 1, since nums[1] 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 8th second. Hence, the answer is 8.
Example 2:
Input: nums = [1,3], changeIndices = [1,1,1,2,1,1,1] Output: 6 Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices: Second 1: Choose index 2 and decrement nums[2] by one. nums becomes [1,2]. Second 2: Choose index 2 and decrement nums[2] by one. nums becomes [1,1]. Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [1,0]. Second 4: Mark the index changeIndices[4], which is marking index 2, since nums[2] is equal to 0. Second 5: Choose index 1 and decrement nums[1] by one. nums becomes [0,0]. Second 6: Mark the index changeIndices[6], which is marking index 1, since nums[1] 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 3:
Input: nums = [0,1], changeIndices = [2,2,2] Output: -1 Explanation: In this example, it is impossible to mark all indices because index 1 isn't in changeIndices. Hence, the answer is -1.
Constraints:
1 <= n == nums.length <= 20000 <= nums[i] <= 1091 <= m == changeIndices.length <= 20001 <= changeIndices[i] <= nProblem Overview: You are given an array representing required decrements for each index and a sequence describing which index can be marked at each second. The goal is to determine the earliest second when all indices can be marked after performing enough decrement operations beforehand.
Approach 1: Recursive Backtracking (Exponential Time, Exponential Space)
The brute force idea is to simulate every possible sequence of actions. At each second you either decrement a value or mark the index if its value is already zero. Recursively explore all valid choices and track whether every index can eventually be marked within the allowed time. This approach directly models the rules of the problem but the branching factor grows quickly because every second may allow multiple operations. Time complexity becomes exponential in the number of seconds, and recursion stack usage leads to exponential space in the worst case. This version mainly helps you understand the constraints before optimizing.
Approach 2: Greedy Decrement Strategy (O(n + m) Time, O(n) Space)
A better approach treats the process greedily. When you know a specific second is used to mark an index, all required decrements for that index must occur before that moment. Track remaining decrements for each index and process the timeline from left to right. When a mark event appears, check whether enough earlier seconds exist to finish its decrements; otherwise the schedule is impossible. This strategy uses simple counters and iteration over the array of operations. Space complexity stays linear because you only maintain decrement counts and bookkeeping for which indices are completed.
Approach 3: Binary Search on Time + Greedy Check (O((n + m) log m) Time, O(n) Space)
The optimal strategy recognizes that the answer is the earliest feasible second. That makes the problem ideal for binary search over the time range. For a candidate second t, simulate whether it is possible to complete all decrements and marks using only the first t operations. The validation step uses the greedy decrement logic: traverse the operations, schedule marks when allowed, and ensure each index had enough earlier time to reduce its value to zero. If marking all indices is feasible within t, search the left half; otherwise search the right half. This converts the scheduling challenge into repeated feasibility checks and keeps each check linear.
Recommended for interviews: The binary search plus greedy validation is the solution interviewers expect. It shows you recognize the monotonic property of the answer and can combine binary search with a greedy feasibility check. Mentioning the brute-force backtracking approach first demonstrates understanding of the state space, but the optimized search-based solution shows stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | Exponential | Exponential | Conceptual understanding or very small inputs |
| Greedy Decrement Simulation | O(n + m) | O(n) | Checking feasibility when time limit is already fixed |
| Binary Search + Greedy Validation | O((n + m) log m) | O(n) | Finding the earliest valid second in the general case |