Earliest Second to Mark Indices I - Solution & Explanation
Problem Statement
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
iin the range[1, n]and decrementnums[i]by1. - If
nums[changeIndices[s]]is equal to0, mark the indexchangeIndices[s]. - 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 = [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] <= n
Approach Overview
Problem 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 1: Greedy Decrement Strategy
This approach focuses on decrementing the numbers in the nums array until they reach zero. Once at zero, we mark the index using the changeIndices only if the condition is satisfied. The task is, therefore, to strategically decrement indices in nums to eventually allow marking. The main idea is to iterate through changeIndices, adjusting and marking off nums as efficiently as possible.
In this C implementation, we maintain an array 'marked' to keep track of which numbers have been marked at zero. We decrement the numbers in the nums array based on the current index indicated by changeIndices. If a number reduces to zero and hasn't been marked yet, we mark it and check if all indices are marked.
Complexity
Time Complexity: O(m) where m is the number of operations; Space Complexity: O(n) for the 'marked' array.
Approach 2: Recursive Backtracking
This approach views the problem as a combination of dynamic and recursive decision-making. At each possible second, decide whether to decrement a number in nums, and carry out a backtracking recursive call exploring decision paths. If a state of zero unmarked nums is reached, return. This method, while slower, explores all potential efficient ways to mark the indices.
In this C approach, the function backtrack is recursively called at each second to decide whether to decrement a number or mark an index. The state is maintained through recursive returns, and the process is repeated until a valid marking sequence is achieved.
Complexity
Time Complexity: Potentially exponential; Space Complexity: O(m) due to recursion.
Approach 3: Greedy Decrement and Marking
This approach involves greedily decrementing the specified elements in nums to zero at each second if possible, and marking indices when they reach zero based on changeIndices array. The goal is to mark all indices as early as possible by using the operations optimally within each second.
This solution in C uses a boolean array to track which indices in nums have been marked. It iterates through the changeIndices array and decrements the element in nums unless it is zero. If it becomes zero and isn't marked yet, it marks it. It checks if all indices are marked in each second.
Complexity
The time complexity is O(n + m) because in the worst case we process each element in nums and changeIndices arrays once. The space complexity is O(n) due to the boolean array used for marking.
Approach 4: Binary Search on Time
This approach uses binary search to find the earliest second when all indices in nums can be marked. The idea is to test different times by decrementing numbers optimally and marking whenever possible, to see if all numbers can be marked.
This C function checks if it’s feasible to mark all indices by a certain second using binary search. It applies a testing function, can_mark_all, evaluating the marking feasibility at each candidate second, narrowing down the search range with binary methodology until finding a minimal viable time.
Complexity
Time complexity is O(log(m) * m) with binary search running over m seconds, each time checking marking feasibility. Space use is O(n) for auxiliary marking arrays during feasibility checks.
Approach 5: Binary Search
We notice that if we can mark all indices within t seconds, then we can also mark all indices within t' geq t seconds. Therefore, we can use binary search to find the earliest seconds.
We define the left and right boundaries of binary search as l = 1 and r = m + 1, where m is the length of the array changeIndices. For each t = \frac{l + r}{2}, we check whether we can mark all indices within t seconds. If we can, we move the right boundary to t, otherwise we move the left boundary to t + 1. Finally, we judge whether the left boundary is greater than m, if it is, return -1, otherwise return the left boundary.
The key to the problem is how to judge whether we can mark all indices within t seconds. We can use an array last to record the latest time each index needs to be marked, use a variable decrement to record the current number of times that can be reduced, and use a variable marked to record the number of indices that have been marked.
We traverse the first t elements of the array changeIndices, for each element i, if last[i] = s, then we need to check whether decrement is greater than or equal to nums[i - 1], if it is, we subtract nums[i - 1] from decrement, and add one to marked; otherwise, we return False. If last[i] neq s, then we can temporarily not mark the index, so we add one to decrement. Finally, we check whether marked is equal to n, if it is, we return True, otherwise return False.
The time complexity is O(m times log m), and the space complexity is O(n). Where n and m are the lengths of nums and changeIndices respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Decrement Strategy | Time Complexity: O(m) where m is the number of operations; Space Complexity: O(n) for the 'marked' array. |
| Recursive Backtracking | Time Complexity: Potentially exponential; Space Complexity: O(m) due to recursion. |
| Greedy Decrement and Marking | The time complexity is O(n + m) because in the worst case we process each element in |
| Binary Search on Time | Time complexity is O(log(m) * m) with binary search running over |
| Binary Search | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3048. Earliest Second to Mark Indices I | Binary Search | Greedy | Weekly Contest 386 • Aryan Mittal • 4,566 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Earliest Second to Mark Indices I easy or hard?
Earliest Second to Mark Indices I Python or Java solution?
What is the best approach for Earliest Second to Mark Indices I?
How to solve Earliest Second to Mark Indices I in O((n+m) log m)?
What data structure is used in Earliest Second to Mark Indices I?
What is the time complexity of Earliest Second to Mark Indices I?
Is Earliest Second to Mark Indices I asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Earliest Second to Mark Indices I with our built-in code editor and test cases.
Practice on FleetCode