Earliest Second to Mark Indices I

Medium

MathWorks

2 views

Topics:

ArraysBinary Search

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 i in the range [1, n] and decrement nums[i] by 1.
If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[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 <= 2000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 2000
1 <= changeIndices[i] <= n

Try coding it in LeetCode

Earliest Second to Mark Indices I

Medium

MathWorks

2 views

Topics:

ArraysBinary Search

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 i in the range [1, n] and decrement nums[i] by 1.
If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[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 <= 2000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 2000
1 <= changeIndices[i] <= n

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of `nums` (n) and `changeIndices` (m)?
Can the values in `nums` be negative, zero, or have a specific maximum value?
If it's impossible to mark all indices in `nums`, should I return -1 or throw an exception?
Are the indices in `changeIndices` 1-based or 0-based relative to `nums`?
Are there any duplicate values in `nums`? If so, how should the marking be handled for duplicate indices?

Brute Force Solution

Approach

The brute force method for this problem involves trying every possible combination of assignments to see if we can mark all the indices. It's like trying every single lock combination until you find the right one. We’ll go through each possible timeframe to find the earliest one that works.

Here's how the algorithm would work step-by-step:

Start by considering the smallest possible time frame - the first one second.
Check if, using only the assignment available at that first second, you can mark all the required spots.
If it doesn't work, increase the time frame to two seconds.
Now, consider all assignments possible within the first two seconds.
See if, using this extended set of assignments, you can mark all the spots.
Keep increasing the timeframe by one second at a time.
For each time frame, carefully check if it is possible to mark all required spots using the assignments available up to that second.
Once you find a time frame where you can successfully mark all spots, that's your answer.

Code Implementation

def earliest_second_to_mark_indices_brute_force(numbers_array, change_indices):
    for current_time in range(1, len(change_indices) + 1):
        
        available_indices = change_indices[:current_time]
        
        #Try all possible combinations to mark
        import itertools
        for combination in itertools.permutations(available_indices):
            
            marked = [False] * len(numbers_array)
            
            all_marked = True
            
            for index_to_change in combination:
                if index_to_change <= len(numbers_array) :
                    marked[index_to_change -1] = True

            for number_index in range(len(numbers_array)):
                if not marked[number_index]:
                    all_marked = False
                    break

            #If we marked all indices, then we found an answer
            if all_marked:
                return current_time

    # We didn't find an answer, so we return -1
    return -1

Big(O) Analysis

Time Complexity

O(m * n^n) – The outer loop iterates up to m times, where m is the length of the given array assignments. In each iteration, a check is performed to see if it's possible to mark all n indices. The core of this check involves trying all possible combinations of the available assignments (up to the current second) to cover the n indices. The number of combinations grows exponentially with n, specifically, it could potentially be n^n in the worst case where each assignment can mark any index. This combination checking dominates the time complexity, resulting in a total time complexity of approximately m * n^n, which simplifies to O(m * n^n).

Space Complexity

O(N) – The brute force solution requires a temporary array or set to keep track of which indices have been marked for each timeframe being tested. In the worst case, within each timeframe, the algorithm needs to remember the marked status of all N indices to determine if all spots have been covered. Thus, this necessitates extra space that grows linearly with the input size N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

This problem asks us to find the earliest possible time we can mark all elements in a list. The key is to work backward, focusing on when we *must* use a certain time slot, and then greedily filling in the rest.

Here's how the algorithm would work step-by-step:

Start by thinking about the last possible moment each element in the initial list can be marked. This is determined by the corresponding number in a separate list that tells us when each initial element can be marked.
Work backwards through the separate list of possible marking times. For each time slot, check if it *must* be used to mark a specific element from the initial list because that element can't be marked at any later time.
If a time slot *must* be used, then use it to mark the corresponding element. If multiple elements *must* be marked at that time, prioritize one of them.
If a time slot isn't required for any specific element, we can skip it and move to an earlier time. This is the greedy part: we are prioritizing marking elements at the latest possible time.
Continue working backward until all elements from the initial list are marked, or you run out of time slots. If all elements are marked, then the earliest time is the last time slot you used.
If you run out of time slots before marking all elements, it's impossible to mark them all, so the answer would be -1.

Code Implementation

def find_earliest_second_to_mark_indices(numbers, change):
    number_count = len(numbers)
    change_count = len(change)
    marked = [False] * number_count
    must_use = [-1] * change_count

    # Mark the must_use array from the back
    for i in range(change_count - 1, -1, -1):
        number_to_mark = change[i]
        index_to_mark = numbers.index(number_to_mark) if number_to_mark in numbers else -1
        if index_to_mark != -1 and must_use[i] == -1 and not marked[index_to_mark]:
            last_occurrence = -1
            for j in range(change_count - 1, -1, -1):
                if numbers[index_to_mark] == change[j]:
                    last_occurrence = j
                    break
            
            can_mark_later = False
            for k in range(i + 1, change_count):
                if change[k] == numbers[index_to_mark] and k <= last_occurrence and not marked[index_to_mark]:
                  can_mark_later = True
                  break

            if not can_mark_later:

                must_use[i] = index_to_mark
                marked[index_to_mark] = True

    marked = [False] * number_count
    for i in range(change_count):
        if must_use[i] != -1:

            marked[must_use[i]] = True

    #Greedily fill in the rest
    for i in range(change_count):
        if must_use[i] == -1:
            number_to_mark = change[i]
            index_to_mark = numbers.index(number_to_mark) if number_to_mark in numbers else -1
            if index_to_mark != -1 and not marked[index_to_mark]:
                must_use[i] = index_to_mark
                marked[index_to_mark] = True
    if all(marked):
        return change_count

    return -1

Big(O) Analysis

Time Complexity

O(m*n) – Let n be the length of the input array 'nums' and m be the length of the input array 'changeIndices'. The algorithm iterates backward through the 'changeIndices' array (length m). In each iteration, it checks if a particular index in 'nums' *must* be marked at that specific time. To determine this, it potentially iterates through 'nums' (length n) to check if any element can only be marked at the current index of 'changeIndices'. This leads to a nested loop structure, resulting in a time complexity of O(m*n), as each of the m time slots in `changeIndices` potentially requires scanning all n elements in `nums`.

Space Complexity

O(N) – The algorithm implicitly keeps track of which indices from the initial list have been marked. The plain English description refers to determining the last possible moment each element can be marked and then working backwards, implying the storage of which elements are still unmarked. In the worst-case scenario, we might need to store information about all N elements in the initial list. Therefore, the auxiliary space used is proportional to the size of the input list. This can be achieved, for example, via a boolean array or set of size N.

Edge Cases

Case	How to Handle
nums is null or empty	Return -1 if nums is null or empty since there are no indices to mark.
changeIndices is null or empty	Return -1 if changeIndices is null or empty because no indices can be marked, unless nums is also empty.
nums.length is greater than changeIndices.length	Return -1, as it is impossible to mark all indices in nums.
nums contains duplicate indices	The binary search and simulated marking process handles this correctly as the earliest marking index will be chosen first.
changeIndices contains out-of-bounds indices for nums	Handle out-of-bounds indices in changeIndices by skipping or ignoring them during the simulation.
Large input sizes for nums and changeIndices	Ensure the binary search and simulated marking process scales efficiently (O(m log m) or better) to avoid timeouts.
The last index in changeIndices is the only index needed to complete marking of nums	The binary search will find the smallest possible right bound which will contain that index.
changeIndices contains indices that never appear	The binary search will still find a solution or determine no solution is possible given valid upper and lower bounds.