3048. Earliest Second to Mark Indices I
Problem Description
You are provided with two integer arrays, nums
with a 1-indexed length of n
, and changeIndices
with a length of m
. At the beginning, no index in nums
is marked, and your goal is to mark every index in it.
Each second, from 1
to m
(both included), you have the option to perform one of these operations:
- Choose an unmarked index
i
within the range[1, n]
and decrement the value ofnums[i]
by1
. - If
nums[changeIndices[s]]
is0
, mark the indexchangeIndices[s]
. - Opt to do nothing.
Your task is to determine the earliest second within the range [1, m]
at which all indices in nums
can be marked if operations are chosen optimally, or otherwise, return -1
if it's not possible to do so.
Intuition
The key to solving this problem lies in understanding how to use the changeIndices
efficiently. Since we are trying to find the minimum amount of time needed to mark all indices, a binary search approach can be applied to guess a second, s
, to check if it is possible to mark all indices by that time.
The intuition here involves realizing that to mark an index at changeIndices[s]
, we need to reduce the corresponding nums
value to 0
by the time we use it. If it is already 0
before its last appearance in changeIndices
, we mark it; otherwise, we choose to decrement a nums
value that has yet to appear in changeIndices
.
To implement this, we should be able to:
- Track the last second each index in
changeIndices
is supposed to be used. - Know the total decrement that has been applied until any second
s
.
Using a binary search, we can minimize the guess for the earliest second. Then, we simulate the process to check if all indices can be marked by that second.
- We initialize our lower bound,
l
, to 0, and upper bound,r
, to the length ofchangeIndices
plus 1. - We perform binary search while
l
is less thanr
. - For each guess, we simulate the marking process with
canMark
function. - If all indices are marked, we adjust
r
to the current mid-pointm
, else we setl
tom + 1
. - The search ends when
l
is not less thanr
, and the result isl
if it's within the allowed range, or-1
otherwise.
The canMark
function tries to mark indices up to a given second and returns true
if it's possible, false
otherwise. It uses indexToLastSecond
to track the last second each index needs to be marked and decrement
to keep count of the total decrements applied. If at the end of the given second, the number of marked indices equals the length of nums
, all indices can be marked by that second. Otherwise, it is not possible by that second, and we need to try a later one.
This solution is optimal as it intelligently guesses the earliest second possible and verifies it, minimizing unnecessary operation simulations.
Learn more about Binary Search patterns.
Solution Approach
The solution approach uses a binary search algorithm combined with a greedy strategy to determine the earliest second at which all indices in nums
can be marked.
Following are the steps and concepts used in the implemented solution:
-
Binary Search: The solution leverages the binary search pattern to efficiently narrow down the smallest possible second at which the condition can be satisfied. The binary search looks for the leftmost point (earliest second) where all indices can be marked, with a search space initially spanning from
0
to the length ofchangeIndices
plus 1. -
Simulation Function (
canMark
): This function acts as the condition checker for the binary search. It simulates the marking process and returnstrue
if it is possible to mark all indices within a given second, orfalse
otherwise. -
Decrement Counter: A
decrement
variable is used to record the total number of decrements that occur up until each second. This helps in understanding whether a particular index can be marked when its turn comes in thechangeIndices
array. -
Last Second Index Tracker: An array,
indexToLastSecond
, with the same length asnums
is used to track the last second at which an index is supposed to be marked. This array is populated with-1
values initially and gets updated as the algorithm iterates overchangeIndices
for each simulated second. This tracking helps ensure we only mark an index at its last relevant second. -
Greedy Choice and Operation Simulation: At each simulated second up to the middle value of the binary search, if an index is at its last marking opportunity, we check if the total decrements are enough for the value at
nums[index]
to be0
. If it's0
, we mark it; if it's not, the function returnsfalse
. If it's not the last chance to mark the index, we increment thedecrement
counter to reflect a choice of future possibility rather than immediate marking. -
Return Value: Once the binary search converges on the smallest second where
canMark
returnstrue
, that value is returned. If the search fails to find such a second within the allowed range[1, m]
, the function returns-1
.
By performing the above steps, this solution efficiently finds the earliest possible second to mark all indices by simulating the optimal operations that can be taken at each second. The use of binary search significantly reduces the computation time since we need only to check log(m) possibilities instead of all m seconds.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example.
Suppose we have:
nums = [3, 3, 2]
representing the values at the indices 1 to 3, wheren = 3
.changeIndices = [2, 3, 1]
signifying we can mark indices 2, 3, and 1 in that order, wherem = 3
.
We are looking for the earliest second where all indices can be marked.
Step 1 - Binary Search Initialization:
- Initialize
l
(lower bound) to0
andr
(upper bound) tom + 1
, which is4
in this case.
Step 2 - Start Binary Search:
- The initial midpoint
mid
is calculated as(l + r) / 2
which is2
(assuming integer division). - We use this
mid
as the guessed second to test with ourcanMark
function.
Step 3 - canMark
Simulation:
- At second
1
, we can only work with thechangeIndices
value2
. Since "3" is the last occurrence of2
inchangeIndices
, we don't mark it yet. We increment thedecrement
variable andnums
becomes[3, 2, 2]
. - At second
2
, ourchangeIndices
value is3
. Since "3" is the last time it appears, we check ifnums[3]
reduced by the total decrement (which is now1
) equals0
. Since it doesn't (nums[3]
is2
), we can't mark it.
Hence, by the end of second 2
, we haven't marked all indices, and canMark
returns false.
Adjust Binary Search:
- Since
canMark(mid)
wheremid
is2
returnedfalse
, we setl
tomid + 1
which is3
and leaver
as it is. - The new
mid
is thenl + (r - l) / 2
, which gives us3.5
, which will be3
after integer division.
Repeat canMark
Simulation:
- At second
1
, similar to the previous step, we increment thedecrement
variable,nums
becomes[3, 2, 2]
. - At second
2
, again similar to the previous step, we increment thedecrement
variable,nums
becomes[3, 1, 1]
. - At second
3
, thechangeIndices
value is1
, and since it's the last occurrence of it, we check ifnums[1]
(which is3
) reduced by the total decrement (which is now2
) equals0
. It doesn't, so we can't mark it.
Binary Search Convergence:
- The binary search procedure continues, but there's no need to adjust
r
since we haven't found a validmid
. Hence, asl
crossesr
, the search fails to find a second where all indices could be marked within the given range[1, m]
.
Step 4 - Conclusion:
- Since we cannot find an earliest second by our
mid
within the allowed range, the return value is-1
.
By using this binary search method combined with canMark
, we efficiently deduce that it's not possible to mark all indices in the provided time frame for the example given. If it were possible, our binary search would have converged to the earliest possible second.
Solution Implementation
1class Solution:
2 def earliest_second_to_mark_indices(self, nums, change_indices):
3 """
4 Determine the earliest second when all indices can be marked.
5
6 Args:
7 nums: List[int] - list of numbers.
8 change_indices: List[int] - list of indices to be changed.
9
10 Returns:
11 int: The earliest second to mark all indices, or -1 if not possible.
12 """
13 # Initialize search bounds for binary search.
14 left = 0
15 right = len(change_indices) + 1
16
17 # Continue binary search until it converges.
18 while left < right:
19 mid = (left + right) // 2
20 # Check if we can mark all indices given mid seconds.
21 if self.can_mark(nums, change_indices, mid):
22 right = mid
23 else:
24 left = mid + 1
25
26 # If found, return the earliest second; otherwise, return -1.
27 return left if left <= len(change_indices) else -1
28
29 def can_mark(self, nums, change_indices, second):
30 """
31 Check if all indices can be marked given a number of seconds.
32
33 Args:
34 nums: List[int] - list of numbers.
35 change_indices: List[int] - list of indices to be changed.
36 second: int - number of seconds to attempt to mark all indices.
37
38 Returns:
39 bool: True if can mark all indices within given seconds, else False.
40 """
41 # Array representing the last second each index can be marked.
42 index_to_last_second = [-1] * len(nums)
43
44 # Update index_to_last_second with the last second an index can be marked.
45 for i in range(second):
46 # Convert to 0-based index for current change_index.
47 index_to_last_second[change_indices[i] - 1] = i
48
49 # Attempt to mark each index, respecting the given number of seconds.
50 decrement = 0
51 num_marked = 0
52 for i in range(second):
53 index = change_indices[i] - 1
54 # If this is the last time the index appears in the sequence,
55 # it should be marked in this second, if possible.
56 if i == index_to_last_second[index]:
57 # If decrement is too large, the index cannot be marked.
58 if nums[index] > decrement:
59 return False
60 # Decrement the decrement counter by the number at the index.
61 decrement -= nums[index]
62 # Increment the count of marked indices.
63 num_marked += 1
64 else:
65 # Otherwise, increment the decrement counter.
66 decrement += 1
67
68 # We can mark all indices if the number marked equals the array length.
69 return num_marked == len(nums)
70
1class Solution {
2 public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
3 // Initialize search bounds for binary search.
4 int left = 0;
5 int right = changeIndices.length + 1;
6 // Continue binary search until it converges.
7 while (left < right) {
8 int mid = (left + right) / 2;
9 // Check if we can mark all indices given mid seconds.
10 if (canMark(nums, changeIndices, mid)) {
11 right = mid;
12 } else {
13 left = mid + 1;
14 }
15 }
16 // If found, return the earliest second; otherwise, return -1.
17 return left <= changeIndices.length ? left : -1;
18 }
19
20 private boolean canMark(int[] nums, int[] changeIndices, int second) {
21 int numMarked = 0;
22 int decrement = 0;
23 // Array representing the last second each index can be marked.
24 int[] indexToLastSecond = new int[nums.length];
25 Arrays.fill(indexToLastSecond, -1);
26
27 // Update indexToLastSecond with the last second an index can be marked.
28 for (int i = 0; i < second; ++i) {
29 indexToLastSecond[changeIndices[i] - 1] = i;
30 }
31
32 // Attempt to mark each index, respecting the given number of seconds.
33 for (int i = 0; i < second; ++i) {
34 // Convert to 0-based index for current changeIndex.
35 int index = changeIndices[i] - 1;
36 // If this is the last time the index appears in the sequence,
37 // it should be marked in this second, if possible.
38 if (i == indexToLastSecond[index]) {
39 // If decrement is too large, the index cannot be marked.
40 if (nums[index] > decrement) {
41 return false;
42 }
43 // Decrement the decrement counter by the number at the index.
44 decrement -= nums[index];
45 // Increment the count of marked indices.
46 numMarked++;
47 } else {
48 // Otherwise, increment the decrement counter.
49 decrement++;
50 }
51 }
52 // We can mark all indices if the number marked equals the array length.
53 return numMarked == nums.length;
54 }
55}
56
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 // Method to determine the earliest second to mark all indices.
8 int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
9 // Initialize search bounds for binary search.
10 int left = 0;
11 int right = changeIndices.size() + 1;
12
13 // Continue binary search until it converges.
14 while (left < right) {
15 int mid = (left + right) / 2;
16
17 // Check if we can mark all indices given mid seconds.
18 if (canMark(nums, changeIndices, mid)) {
19 right = mid;
20 } else {
21 left = mid + 1;
22 }
23 }
24
25 // If found, return the earliest second; otherwise, return -1.
26 return left <= changeIndices.size() ? left : -1;
27 }
28
29private:
30 // Helper method to check if it's possible to mark all indices within the specified number of seconds.
31 bool canMark(vector<int>& nums, vector<int>& changeIndices, int seconds) {
32 int numMarked = 0;
33 int decrement = 0;
34
35 // Vector representing the last second each index can be marked.
36 vector<int> indexToLastSecond(nums.size(), -1);
37
38 // Update indexToLastSecond with the last second an index can be marked.
39 for (int i = 0; i < seconds; ++i) {
40 indexToLastSecond[changeIndices[i] - 1] = i;
41 }
42
43 // Attempt to mark each index, respecting the given number of seconds.
44 for (int i = 0; i < seconds; ++i) {
45 // Convert to 0-based index for the current changeIndex.
46 int index = changeIndices[i] - 1;
47
48 // If this is the last time the index appears in the sequence,
49 // it should be marked in this second, if possible.
50 if (i == indexToLastSecond[index]) {
51 // If decrement is too large, the index cannot be marked.
52 if (nums[index] > decrement) {
53 return false;
54 }
55
56 // Decrement the decrement counter by the number at the index.
57 decrement -= nums[index];
58
59 // Increment the count of marked indices.
60 numMarked++;
61 } else {
62 // Otherwise, increment the decrement counter.
63 decrement++;
64 }
65 }
66
67 // We can mark all indices if the number marked equals the array length.
68 return numMarked == nums.size();
69 }
70};
71
1function earliestSecondToMarkIndices(nums: number[], changeIndices: number[]): number {
2 // Initialize search bounds for binary search.
3 let left: number = 0;
4 let right: number = changeIndices.length + 1;
5
6 // Continue binary search until it converges.
7 while (left < right) {
8 let mid: number = Math.floor((left + right) / 2);
9
10 // Check if we can mark all indices given `mid` seconds.
11 if (canMarkIndices(nums, changeIndices, mid)) {
12 right = mid;
13 } else {
14 left = mid + 1;
15 }
16 }
17
18 // If we found a valid second return it; otherwise return -1
19 return left <= changeIndices.length ? left : -1;
20}
21
22function canMarkIndices(nums: number[], changeIndices: number[], seconds: number): boolean {
23 let numMarked: number = 0;
24 let decrement: number = 0;
25
26 // Array representing the last second each index can be marked.
27 const indexToLastSecond: number[] = new Array(nums.length).fill(-1);
28
29 // Update indexToLastSecond with the latest second an index can be marked.
30 for (let i = 0; i < seconds; ++i) {
31 indexToLastSecond[changeIndices[i] - 1] = i;
32 }
33
34 // Attempt to mark each index, within the constraint of the provided seconds.
35 for (let i = 0; i < seconds; ++i) {
36 // Convert to 0-based index for the current changeIndex.
37 const index: number = changeIndices[i] - 1;
38
39 // If this is the last second that the index appears in changeIndices,
40 // it should be marked on this second if possible.
41 if (i === indexToLastSecond[index]) {
42 // If decrement is too large, the index cannot be marked.
43 if (nums[index] > decrement) {
44 return false;
45 }
46
47 // Decrement the decrement counter by the number at the index.
48 decrement -= nums[index];
49
50 // Increment the count of marked indices.
51 numMarked++;
52 } else {
53 // If this is not the last appearance, increase the decrement for future markings.
54 decrement++;
55 }
56 }
57
58 // Check if all numbers have been marked.
59 return numMarked === nums.length;
60}
61
Time and Space Complexity
Time Complexity
The time complexity of the given code can be broken down as follows:
-
The binary search in the
earliestSecondToMarkIndices
method takesO(log(c))
time, wherec
is the length of thechangeIndices
array. This is because each iteration of the loop cuts the problem space in half. -
The
canMark
method is called at each step of the binary search. Inside thecanMark
method, there are twofor
loops that run up tosecond
, which in the worst case isO(c)
. -
The
Arrays.fill(indexToLastSecond, -1)
operation insidecanMark
has a time complexity ofO(n)
, wheren
is the length of thenums
array, as it initializes each element in theindexToLastSecond
array.
Considering these together, in the worst case, the canMark
method is executed log(c)
times and each time it takes O(c) + O(n)
time. Therefore, the overall worst-case time complexity of the entire program is O(n + c * log(c))
as c
operations for the loops inside canMark
can dominate over n
when c
is of considerable size relative to n
.
Space Complexity
The space complexity of the given code can be analyzed as follows:
-
An additional array
indexToLastSecond
of sizen
is created in thecanMark
method, resulting in anO(n)
space complexity. -
Only a few integer variables are used for iteration and calculation, contributing an
O(1)
additional space.
Hence, the overall space complexity of the code is O(n)
due to the indexToLastSecond
array.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!