Jobs

Interviews

Discussions

Make Array Strictly Increasing

Hard

Asked by:

6 views

Topics:

ArraysBinary SearchDynamic Programming

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Try coding it in LeetCode

Make Array Strictly Increasing

Hard

Asked by:

6 views

Topics:

ArraysBinary SearchDynamic Programming

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

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 is the range of values in the input array? Are negative numbers, zeros, or floating-point numbers possible?
Can the input array be empty or null?
If it is not possible to make the array strictly increasing, what should I return?
Are there any constraints on the operations that I am allowed to do?
Could you define the term 'strictly increasing' for this problem? Should each element be greater than the element before it or greater than or equal to?

Brute Force Solution

Approach

The brute force approach to making an array strictly increasing involves trying every possible combination of changes to the array elements. We explore each element and its potential replacements, checking if the resulting array is strictly increasing. This method guarantees finding the solution if it exists but can be very slow.

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

Start with the first number in the list.
Consider all possible numbers that could replace it. These numbers must be larger than the number before it (if there is one) to maintain the strictly increasing order.
For each possible replacement, move to the next number in the list.
Again, consider all possible numbers that could replace this number, ensuring they are larger than the number before it after the possible replacement made previously.
Continue this process until you reach the end of the list. At this point, you've created one possible strictly increasing list.
Repeat steps 2-5 for all possible combinations of replacements in the list.
Keep track of the fewest changes it took to make the array strictly increasing.
Return the smallest number of changes you found.

Code Implementation

def make_array_strictly_increasing_brute_force(array_one, array_two):
    minimum_changes = float('inf')

    def find_minimum_changes(current_index, previous_number, current_changes, current_array):
        nonlocal minimum_changes

        # If we reach the end, update the minimum changes.
        if current_index == len(array_one):
            minimum_changes = min(minimum_changes, current_changes)
            return

        # Option 1: Don't change the current number.
        if array_one[current_index] > previous_number:
            find_minimum_changes(
                current_index + 1,
                array_one[current_index],
                current_changes,
                current_array
            )

        # Option 2: Change the current number with numbers from array_two.
        for replacement_number in array_two:

            # Check if the replacement number is greater than the previous number.
            if replacement_number > previous_number:
                find_minimum_changes(
                    current_index + 1,
                    replacement_number,
                    current_changes + 1,
                    current_array
                )

    # Begin recursive calls with appropriate initial values.
    find_minimum_changes(
        0,
        float('-inf'),
        0,
        array_one
    )
    
    # Check if any solution exists
    if minimum_changes == float('inf'):
        return -1

    return minimum_changes

Big(O) Analysis

Time Complexity

O(m^n) – The described brute force approach explores all possible replacements for each element in the input array. Let n be the length of the input array and m be the range of possible replacement values for each element. For each of the n positions, we might need to try up to m different values. This leads to a decision tree where each node has up to m children. Traversing this tree requires exploring up to m^n possible combinations, making the time complexity O(m^n).

Space Complexity

O(N) – The brute force approach described explores every possible combination of replacements using recursion. In the worst-case scenario, where many replacements are needed, the recursion depth could reach N (the number of elements in the input array), leading to N stack frames on the call stack to track the possible changes being made. The space used by the recursion stack is proportional to the depth of the recursion. Thus, the auxiliary space complexity is O(N).

Optimal Solution

Approach

To make the array strictly increasing with the fewest changes, we'll use a technique that focuses on building the longest possible increasing sequence. We'll replace elements that disrupt this sequence with suitable values from another available set.

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

Imagine you're walking through the first array, building a path of increasing numbers.
If you find a number that's smaller than or equal to the one before it, you've hit a roadblock.
Look in the second array for a number that's bigger than the previous number on your path, and smaller than the next number after the roadblock on your path. This number can be used to fix the 'roadblock'.
Replace the problem number with the smallest suitable number from the second array. This is important.
If you can't find a suitable number, the array cannot be made strictly increasing, so we can stop.
Keep track of how many numbers you replace. This is the answer you're looking for.
Repeat this process until you've gone through the entire first array.

Code Implementation

def make_array_strictly_increasing(first_array, second_array):
    second_array.sort()
    number_of_changes = 0
    previous_value = float('-inf')

    for i in range(len(first_array)):
        if first_array[i] > previous_value:
            previous_value = first_array[i]
        else:
            # Need to find a replacement from second array
            replacement_found = False
            suitable_replacement = float('inf')
            
            for potential_replacement in second_array:
                if potential_replacement > previous_value and potential_replacement < suitable_replacement:
                    suitable_replacement = potential_replacement
                    replacement_found = True

            if replacement_found:
                # Choose the smallest valid replacement
                first_array[i] = suitable_replacement
                previous_value = suitable_replacement
                number_of_changes += 1
            else:
                # No suitable replacement found
                return -1

    return number_of_changes

Big(O) Analysis

Time Complexity

O(n*m*log(m)) – We iterate through the first array of size 'n'. In the worst case, for each element, we might need to find a suitable replacement from the second array of size 'm'. Finding the smallest suitable number in the second array involves searching, which can be efficiently done using binary search (lower_bound or similar) in O(log m) time, after sorting the second array which takes O(m log m) time. Thus, inside the loop that runs 'n' times, we have binary search taking O(log m) time. The initial sorting of the second array is O(m log m), but as it is done only once, it does not affect the per element cost. The most time-consuming part per element is the search of O(log m), so the complexity is dominated by the nested loops behavior of n * log(m). Factoring in the initial sort results in O(n*log(m) + m*log(m)). However, if we perform binary search for each of the n elements of the first array, it becomes O(n*log(m)). So the total time complexity would be O(n*log(m)). After re-reading the approach, for each element we consider, we need to search the sorted second array, giving a time complexity of O(n log m). The overall time complexity including sorting the second array once is O(n*log(m) + m*log(m)). In the worst case, we iterate the first array 'n' times and potentially perform a search in the second array of size 'm' (after sorting), and that is why we multiply these values with each other. Therefore, the overall time complexity is O(n*m*log(m)).

Space Complexity

O(N) – The algorithm, as described, implicitly relies on recursion or a stack-like data structure to keep track of potential replacements while iterating through the first array. In the worst-case scenario, where many elements need replacement, the recursion depth or the stack size could grow linearly with the size of the first array, denoted as N. Additionally, sorting the second array (not explicitly mentioned, but likely required to find the 'smallest suitable number') might use O(N) space depending on the sorting algorithm used. Therefore the auxiliary space is O(N) stemming from the implicit data structures and potential sorting.

Edge Cases

Case	How to Handle
Empty arr1 or empty arr2	If arr1 is empty, no increasing sequence can be made, so return -1; arr2 may be empty but still relevant to replace with.
arr1 with one element	If arr1 has one element, we only need to check if it needs replacement and find the smallest element in arr2 that is greater than arr1[0] or no replacement is needed, return 0 or 1 accordingly.
arr1 is already strictly increasing	If arr1 is already strictly increasing, no operations are needed, return 0.
No element in arr2 can make arr1 strictly increasing.	Return -1 when it is impossible to make arr1 strictly increasing regardless of arr2.
arr1 and arr2 contain duplicate elements.	Duplicates in arr1 don't affect the general DP approach; Duplicates in arr2 only matter if they're the smallest possible replacement (need min or sorted structure).
Large input arrays leading to potential memory issues in recursion.	Use dynamic programming with memoization instead of pure recursion to reduce space complexity.
Integer overflow when calculating dp values	Since the constraint doesn't define the value range of the elements, integer overflow isn't relevant in this case; if required, use a larger data type such as long.
All elements in arr1 are the same and arr2 contains a single element greater than them.	Requires all but the last element of arr1 to be replaced with elements in arr2 that are all larger, return the number of required replacements.

Empty arr1 or empty arr2

How to Handle:

If arr1 is empty, no increasing sequence can be made, so return -1; arr2 may be empty but still relevant to replace with.

arr1 with one element

How to Handle:

If arr1 has one element, we only need to check if it needs replacement and find the smallest element in arr2 that is greater than arr1[0] or no replacement is needed, return 0 or 1 accordingly.

arr1 is already strictly increasing

How to Handle:

If arr1 is already strictly increasing, no operations are needed, return 0.

No element in arr2 can make arr1 strictly increasing.

How to Handle:

Return -1 when it is impossible to make arr1 strictly increasing regardless of arr2.

arr1 and arr2 contain duplicate elements.

How to Handle:

Duplicates in arr1 don't affect the general DP approach; Duplicates in arr2 only matter if they're the smallest possible replacement (need min or sorted structure).

Large input arrays leading to potential memory issues in recursion.

How to Handle:

Use dynamic programming with memoization instead of pure recursion to reduce space complexity.

Integer overflow when calculating dp values

How to Handle:

Since the constraint doesn't define the value range of the elements, integer overflow isn't relevant in this case; if required, use a larger data type such as long.

All elements in arr1 are the same and arr2 contains a single element greater than them.

How to Handle:

Requires all but the last element of arr1 to be replaced with elements in arr2 that are all larger, return the number of required replacements.

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 is the range of values in the input array? Are negative numbers, zeros, or floating-point numbers possible?
Can the input array be empty or null?
If it is not possible to make the array strictly increasing, what should I return?
Are there any constraints on the operations that I am allowed to do?
Could you define the term 'strictly increasing' for this problem? Should each element be greater than the element before it or greater than or equal to?

Brute Force Solution

Approach

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

Start with the first number in the list.
Consider all possible numbers that could replace it. These numbers must be larger than the number before it (if there is one) to maintain the strictly increasing order.
For each possible replacement, move to the next number in the list.
Again, consider all possible numbers that could replace this number, ensuring they are larger than the number before it after the possible replacement made previously.
Continue this process until you reach the end of the list. At this point, you've created one possible strictly increasing list.
Repeat steps 2-5 for all possible combinations of replacements in the list.
Keep track of the fewest changes it took to make the array strictly increasing.
Return the smallest number of changes you found.

Code Implementation

def make_array_strictly_increasing_brute_force(array_one, array_two):
    minimum_changes = float('inf')

    def find_minimum_changes(current_index, previous_number, current_changes, current_array):
        nonlocal minimum_changes

        # If we reach the end, update the minimum changes.
        if current_index == len(array_one):
            minimum_changes = min(minimum_changes, current_changes)
            return

        # Option 1: Don't change the current number.
        if array_one[current_index] > previous_number:
            find_minimum_changes(
                current_index + 1,
                array_one[current_index],
                current_changes,
                current_array
            )

        # Option 2: Change the current number with numbers from array_two.
        for replacement_number in array_two:

            # Check if the replacement number is greater than the previous number.
            if replacement_number > previous_number:
                find_minimum_changes(
                    current_index + 1,
                    replacement_number,
                    current_changes + 1,
                    current_array
                )

    # Begin recursive calls with appropriate initial values.
    find_minimum_changes(
        0,
        float('-inf'),
        0,
        array_one
    )
    
    # Check if any solution exists
    if minimum_changes == float('inf'):
        return -1

    return minimum_changes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're walking through the first array, building a path of increasing numbers.
If you find a number that's smaller than or equal to the one before it, you've hit a roadblock.
Look in the second array for a number that's bigger than the previous number on your path, and smaller than the next number after the roadblock on your path. This number can be used to fix the 'roadblock'.
Replace the problem number with the smallest suitable number from the second array. This is important.
If you can't find a suitable number, the array cannot be made strictly increasing, so we can stop.
Keep track of how many numbers you replace. This is the answer you're looking for.
Repeat this process until you've gone through the entire first array.

Code Implementation

def make_array_strictly_increasing(first_array, second_array):
    second_array.sort()
    number_of_changes = 0
    previous_value = float('-inf')

    for i in range(len(first_array)):
        if first_array[i] > previous_value:
            previous_value = first_array[i]
        else:
            # Need to find a replacement from second array
            replacement_found = False
            suitable_replacement = float('inf')
            
            for potential_replacement in second_array:
                if potential_replacement > previous_value and potential_replacement < suitable_replacement:
                    suitable_replacement = potential_replacement
                    replacement_found = True

            if replacement_found:
                # Choose the smallest valid replacement
                first_array[i] = suitable_replacement
                previous_value = suitable_replacement
                number_of_changes += 1
            else:
                # No suitable replacement found
                return -1

    return number_of_changes

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty arr1 or empty arr2	If arr1 is empty, no increasing sequence can be made, so return -1; arr2 may be empty but still relevant to replace with.
arr1 with one element	If arr1 has one element, we only need to check if it needs replacement and find the smallest element in arr2 that is greater than arr1[0] or no replacement is needed, return 0 or 1 accordingly.
arr1 is already strictly increasing	If arr1 is already strictly increasing, no operations are needed, return 0.
No element in arr2 can make arr1 strictly increasing.	Return -1 when it is impossible to make arr1 strictly increasing regardless of arr2.
arr1 and arr2 contain duplicate elements.	Duplicates in arr1 don't affect the general DP approach; Duplicates in arr2 only matter if they're the smallest possible replacement (need min or sorted structure).
Large input arrays leading to potential memory issues in recursion.	Use dynamic programming with memoization instead of pure recursion to reduce space complexity.
Integer overflow when calculating dp values	Since the constraint doesn't define the value range of the elements, integer overflow isn't relevant in this case; if required, use a larger data type such as long.
All elements in arr1 are the same and arr2 contains a single element greater than them.	Requires all but the last element of arr1 to be replaced with elements in arr2 that are all larger, return the number of required replacements.

Empty arr1 or empty arr2

How to Handle:

If arr1 is empty, no increasing sequence can be made, so return -1; arr2 may be empty but still relevant to replace with.

arr1 with one element

How to Handle:

If arr1 has one element, we only need to check if it needs replacement and find the smallest element in arr2 that is greater than arr1[0] or no replacement is needed, return 0 or 1 accordingly.

arr1 is already strictly increasing

How to Handle:

If arr1 is already strictly increasing, no operations are needed, return 0.

No element in arr2 can make arr1 strictly increasing.

How to Handle:

Return -1 when it is impossible to make arr1 strictly increasing regardless of arr2.

arr1 and arr2 contain duplicate elements.

How to Handle:

Duplicates in arr1 don't affect the general DP approach; Duplicates in arr2 only matter if they're the smallest possible replacement (need min or sorted structure).

Large input arrays leading to potential memory issues in recursion.

How to Handle:

Use dynamic programming with memoization instead of pure recursion to reduce space complexity.

Integer overflow when calculating dp values

How to Handle:

Since the constraint doesn't define the value range of the elements, integer overflow isn't relevant in this case; if required, use a larger data type such as long.

All elements in arr1 are the same and arr2 contains a single element greater than them.

How to Handle:

Requires all but the last element of arr1 to be replaced with elements in arr2 that are all larger, return the number of required replacements.