Earliest Second to Mark Indices II

Hard

MathWorks

2 views

Topics:

ArraysBinary SearchGreedy Algorithms

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.
Set nums[changeIndices[s]] to any non-negative value.
Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i.
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 = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
Second 4: Mark index 1, since nums[1] is equal to 0.
Second 5: Mark index 2, since nums[2] is equal to 0.
Second 6: Mark index 3, since nums[3] 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 2:

Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
Output: 7
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Mark index 1, since nums[1] is equal to 0.
Second 2: Mark index 2, since nums[2] is equal to 0.
Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
Second 6: Mark index 3, since nums[3] is equal to 0.
Second 7: Mark index 4, since nums[4] 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 7th second.
Hence, the answer is 7.

Example 3:

Input: nums = [1,2,3], changeIndices = [1,2,3]
Output: -1
Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. 
Hence, the answer is -1.

Constraints:

1 <= n == nums.length <= 5000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 5000
1 <= changeIndices[i] <= n

Try coding it in LeetCode

Earliest Second to Mark Indices II

Hard

MathWorks

2 views

Topics:

ArraysBinary SearchGreedy Algorithms

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.
Set nums[changeIndices[s]] to any non-negative value.
Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i.
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 = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
Second 4: Mark index 1, since nums[1] is equal to 0.
Second 5: Mark index 2, since nums[2] is equal to 0.
Second 6: Mark index 3, since nums[3] 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 2:

Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
Output: 7
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Mark index 1, since nums[1] is equal to 0.
Second 2: Mark index 2, since nums[2] is equal to 0.
Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
Second 6: Mark index 3, since nums[3] is equal to 0.
Second 7: Mark index 4, since nums[4] 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 7th second.
Hence, the answer is 7.

Example 3:

Input: nums = [1,2,3], changeIndices = [1,2,3]
Output: -1
Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. 
Hence, the answer is -1.

Constraints:

1 <= n == nums.length <= 5000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 5000
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 the `nums` and `changeIndices` arrays? What are the bounds on the values within these arrays?
If it's impossible to mark all indices, should I return -1, or is there any other specific error value I should return?
Can the `changeIndices` array contain duplicate index values? How should I handle a scenario where an index is pointed to multiple times?
Is `nums` guaranteed to contain only positive integers?
If there are multiple possible 'earliest seconds' to mark all indices, should I return the absolute earliest, or is any valid 'earliest second' acceptable?

Brute Force Solution

Approach

The brute force method for this problem means we will check every possible combination of turning on the available options. We'll try turning on the first, then the second, then the first and second, then the first and third, etc., and see if each combination works.

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

Start with the very first available option.
See if using ONLY that option lets you mark everything you need to.
If not, try the first TWO options, and see if using just those two allows you to mark everything.
Keep going, adding one option at a time, and checking if that combination is enough.
After trying each individual option, try every pair of options. Then try every group of three options, and so on.
Each time you try a combination, carefully simulate what happens when you use those options. Check if, with the selected options, you can mark all required items.
If you find a combination that works, remember it.
Keep trying every possible combination of options, even after finding a working one. You want to find the earliest second that works.
After you've tried absolutely every possible combination, pick the earliest time out of all the combinations that work. That's your answer.

Code Implementation

def earliest_second_to_mark_indices_brute_force(available_seconds, required_indices):
    number_available_seconds = len(available_seconds)
    number_required_indices = len(required_indices)
    earliest_time = float('inf')

    for i in range(1, 1 << number_available_seconds):
        selected_seconds_indices = []
        for j in range(number_available_seconds):
            if (i >> j) & 1:
                selected_seconds_indices.append(j)

        # Simulate marking indices with selected seconds
        marked_indices = [False] * number_required_indices
        
        for second_index in selected_seconds_indices:
            current_second = available_seconds[second_index]
            
            for index_to_mark in range(number_required_indices):
                if required_indices[index_to_mark] == current_second:
                    marked_indices[index_to_mark] = True

        # Check if all indices are marked
        all_marked = all(marked_indices)
        
        if all_marked:

            #Find earliest second if the all_marked condition is met
            earliest_possible_time = available_seconds[selected_seconds_indices[-1]]
            earliest_time = min(earliest_time, earliest_possible_time)

    if earliest_time == float('inf'):
        return -1
    else:
        return earliest_time

Big(O) Analysis

Time Complexity

O(n * 2^n) – The algorithm iterates through all possible combinations of the 'n' available seconds. There are 2^n such combinations (each second is either included or excluded). For each combination, the algorithm simulates marking indices, which takes O(n) time in the worst case (where we iterate through all indices to see if they can be marked with the chosen seconds). Therefore, the total time complexity is O(n * 2^n).

Space Complexity

O(N) – The brute force approach involves simulating the marking process for each combination of available options. During this simulation, we potentially need an auxiliary array, `marked`, of size N (where N represents the number of indices that need to be marked) to track which indices have been marked in the current combination. While other variables may be used for iteration and temporary calculations, the `marked` array dominates the auxiliary space used. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The core idea is to use a binary search to find the earliest time when we can mark all the indices. For each time we guess, we'll check if it's possible to mark all indices by selecting the best possible assignment of times to indices greedily.

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

Imagine we are trying to find the earliest possible moment to finish a task.
We can guess a time, and then check if it's possible to finish by then.
To check if it's possible, we go through each task in order.
For each task, we try to assign it to the best possible time slot, meaning a time slot that allows us to complete as many other tasks as possible.
If we can assign all tasks by our guessed time, then we know our guess was too late, so we try an earlier time.
If we cannot assign all tasks, then we know our guess was too early, and we try a later time.
We keep guessing and adjusting until we find the earliest time that allows us to complete all tasks.

Code Implementation

def earliest_second_to_mark_indices(numbers, change_indices):
    number_of_indices = len(numbers)
    number_of_changes = len(change_indices)

    def can_mark_all(time_limit):
        marked = [False] * number_of_indices
        available_times = [0] * number_of_indices

        # Assign available times for each index.
        for time_index in range(time_limit):
            index_to_change = change_indices[time_index] - 1
            available_times[index_to_change] = time_index + 1

        indices_to_mark = list(range(number_of_indices))
        indices_to_mark.sort(key=lambda index: numbers[index])

        # Greedily try to mark each index.
        for index in indices_to_mark:
            mark_time = available_times[index]
            if mark_time == 0:
                return False
            
            required_time = numbers[index]
            
            # Check if we have enough time.
            if mark_time >= required_time:
                
                # Mark the current index as true.
                mark_time_index = mark_time - 1
                index_to_change = change_indices[mark_time_index] - 1
                marked[index_to_change] = True
            else:
                return False

        return all(marked)

    left_bound = 1
    right_bound = number_of_changes
    earliest_time = -1

    # Binary search to find the earliest time.
    while left_bound <= right_bound:
        midpoint = (left_bound + right_bound) // 2

        # Check if it's possible to mark all indices within the time limit.
        if can_mark_all(midpoint):

            #If possible, move the high bound to midpoint -1.
            earliest_time = midpoint
            right_bound = midpoint - 1
        else:

            # If not possible, move the low bound to midpoint + 1.
            left_bound = midpoint + 1

    return earliest_time

Big(O) Analysis

Time Complexity

O(n*m*log(m)) – The algorithm employs binary search over the possible time range (1 to m), where m is the length of the 'time' array. Inside the binary search, we iterate through the 'time' array (of size m) in the `possible` function. For each time in 'time', we iterate through indices (up to n, which is the length of 'marks') to find the optimal assignment. This leads to O(n) operations within the inner loop. The binary search contributes a factor of O(log(m)). Therefore, the overall time complexity is O(n*m*log(m)).

Space Complexity

O(N) – The algorithm uses binary search to find the earliest possible time. The 'check if it's possible' step likely involves marking assigned indices or tracking available time slots, which could require an auxiliary array of size N, where N is the number of indices or tasks. This auxiliary data structure, used to simulate and check assignments within the binary search, leads to O(N) space complexity. Although the problem description is high-level, a practical implementation would likely need to store the state of the marking process for each guessed time.

Edge Cases

Case	How to Handle
Empty nums or changeIndices array	Return -1 immediately since it's impossible to mark any index.
nums and changeIndices have different lengths	Return -1 since the marking process is ill-defined.
n = 1 (single element in nums and changeIndices)	Check if the first changeIndices value allows marking the single index at or before the time given by nums[0].
All nums values are 0	Check for the first occurrence of each index in changeIndices, and if all exist before n, return the maximum such time.
changeIndices never contains a specific index i	Return -1 since index i can never be marked.
Large n, potential for time limit exceed	Employ binary search to efficiently find the earliest second.
changeIndices contains out-of-bounds indices (less than 1 or greater than n)	Filter out invalid changeIndices elements during pre-processing, treating them as no-ops.
Impossible to mark all indices even when iterating through entire changeIndices	Return -1 after binary search if all indices are still not marked.