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 of nums[i] by 1.
If nums[changeIndices[s]] is 0, mark the index changeIndices[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 of changeIndices plus 1.
We perform binary search while l is less than r.
For each guess, we simulate the marking process with canMark function.
If all indices are marked, we adjust r to the current mid-point m, else we set l to m + 1.
The search ends when l is not less than r, and the result is l 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

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 of changeIndices plus 1.
Simulation Function (canMark): This function acts as the condition checker for the binary search. It simulates the marking process and returns true if it is possible to mark all indices within a given second, or false 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 the changeIndices array.
Last Second Index Tracker: An array, indexToLastSecond, with the same length as nums 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 over changeIndices 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 be 0. If it's 0, we mark it; if it's not, the function returns false. If it's not the last chance to mark the index, we increment the decrement 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 returns true, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Example 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, where n = 3.
changeIndices = [2, 3, 1] signifying we can mark indices 2, 3, and 1 in that order, where m = 3.

We are looking for the earliest second where all indices can be marked.

Step 1 - Binary Search Initialization:

Initialize l (lower bound) to 0 and r (upper bound) to m + 1, which is 4 in this case.

Step 2 - Start Binary Search:

The initial midpoint mid is calculated as (l + r) / 2 which is 2 (assuming integer division).
We use this mid as the guessed second to test with our canMark function.

Step 3 - canMark Simulation:

At second 1, we can only work with the changeIndices value 2. Since "3" is the last occurrence of 2 in changeIndices, we don't mark it yet. We increment the decrement variable and nums becomes [3, 2, 2].
At second 2, our changeIndices value is 3. Since "3" is the last time it appears, we check if nums[3] reduced by the total decrement (which is now 1) equals 0. Since it doesn't (nums[3] is 2), 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) where mid is 2 returned false, we set l to mid + 1 which is 3 and leave r as it is.
The new mid is then l + (r - l) / 2, which gives us 3.5, which will be 3 after integer division.

Repeat canMark Simulation:

At second 1, similar to the previous step, we increment the decrement variable, nums becomes [3, 2, 2].
At second 2, again similar to the previous step, we increment the decrement variable, nums becomes [3, 1, 1].
At second 3, the changeIndices value is 1, and since it's the last occurrence of it, we check if nums[1] (which is 3) reduced by the total decrement (which is now 2) equals 0. 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 valid mid. Hence, as l crosses r, 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

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

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 takes O(log(c)) time, where c is the length of the changeIndices 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 the canMark method, there are two for loops that run up to second, which in the worst case is O(c).
The Arrays.fill(indexToLastSecond, -1) operation inside canMark has a time complexity of O(n), where n is the length of the nums array, as it initializes each element in the indexToLastSecond 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 size n is created in the canMark method, resulting in an O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

3048. Earliest Second to Mark Indices I

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings