Make Array Strictly Increasing

Hard

Google

1 view

Topics:

ArraysBinary SearchDynamic Programming

Given two integer arrays arr1 and arr2, your task is to determine the minimum number of operations needed to make arr1 strictly increasing. In a single operation, you can replace an element in arr1 with an element from arr2. If it's impossible to make arr1 strictly increasing, return -1. Assume that 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

Here's a breakdown:

Strictly Increasing: An array is strictly increasing if each element is greater than the element that precedes it.
Operation: You can pick any element from arr2 and use it to replace any element in arr1.
Goal: Minimize the number of replacements to make arr1 strictly increasing.

Example 1:

arr1 = [1, 5, 3, 6, 7]
arr2 = [1, 3, 2, 4]

Output: 1

Explanation: Replace 5 with 2, resulting in arr1 = [1, 2, 3, 6, 7]. Only one operation was needed.

Example 2:

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]. Two operations were needed.

Example 3:

arr1 = [1, 5, 3, 6, 7]
arr2 = [1, 6, 3, 3]

Output: -1

Explanation: It's impossible to make arr1 strictly increasing with the given arrays and operations.

Write a function that takes arr1 and arr2 as input and returns the minimum number of operations needed to make arr1 strictly increasing, or -1 if it is not possible.

Make Array Strictly Increasing

Hard

Google

1 view

Topics:

ArraysBinary SearchDynamic Programming

Here's a breakdown:

Strictly Increasing: An array is strictly increasing if each element is greater than the element that precedes it.
Operation: You can pick any element from arr2 and use it to replace any element in arr1.
Goal: Minimize the number of replacements to make arr1 strictly increasing.

Example 1:

arr1 = [1, 5, 3, 6, 7]
arr2 = [1, 3, 2, 4]

Output: 1

Explanation: Replace 5 with 2, resulting in arr1 = [1, 2, 3, 6, 7]. Only one operation was needed.

Example 2:

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]. Two operations were needed.

Example 3:

arr1 = [1, 5, 3, 6, 7]
arr2 = [1, 6, 3, 3]

Output: -1

Explanation: It's impossible to make arr1 strictly increasing with the given arrays and operations.

Write a function that takes arr1 and arr2 as input and returns the minimum number of operations needed to make arr1 strictly increasing, or -1 if it is not possible.

Solution

Naive Approach (Brute Force)

A brute-force approach would involve trying all possible combinations of replacements from arr2 into arr1 to see if we can make arr1 strictly increasing. This involves recursion and backtracking. For each element in arr1, we can either keep it as is (if it's greater than the previous element) or try replacing it with elements from arr2. We would need to check all possible replacements and keep track of the minimum number of operations.

This approach is highly inefficient due to the exponential number of possible combinations. It would quickly exceed the time limit for larger input sizes.

Big O Analysis (Naive)

Time Complexity: O(mⁿ), where 'n' is the length of arr1 and 'm' is the length of arr2. In the worst case, for each element in arr1, we might try replacing it with every element in arr2.
Space Complexity: O(n) due to the recursive call stack.

Optimal Approach (Dynamic Programming)

A more efficient approach uses dynamic programming and binary search. We can define a DP state dp[i][j] as the minimum number of operations to make arr1[0...i] strictly increasing, with the last element being j. Here, j can be either arr1[i] (if we don't replace it) or an element from arr2 that we use to replace arr1[i].

Initialization: We start by initializing the base cases for the first element of arr1.
Iteration: For each subsequent element in arr1, we have two choices:
- Keep the element if it is greater than the previous element (either the original or a replacement).
- Replace the element with an element from arr2 that is greater than the previous element.
Binary Search: To efficiently find the smallest element in arr2 that is greater than the previous element, we can use binary search after sorting arr2 and removing duplicate elements.

Edge Cases

Empty arrays: Handle cases where arr1 or arr2 are empty.
Unsorted arr2: Sort and deduplicate arr2 before using binary search.
No solution: If at any point we cannot find a valid replacement or keep the element, return -1.

Code Implementation (Python)

import bisect

def makeArrayIncreasing(arr1, arr2):
    arr2 = sorted(list(set(arr2)))
    n = len(arr1)
    
    dp = {}

    def solve(i, prev):
        if i == n:
            return 0
        
        if (i, prev) in dp:
            return dp[(i, prev)]
        
        ans = float('inf')
        
        # Option 1: Keep arr1[i] if possible
        if arr1[i] > prev:
            ans = min(ans, solve(i + 1, arr1[i]))
        
        # Option 2: Replace arr1[i] with an element from arr2
        idx = bisect.bisect_right(arr2, prev)
        if idx < len(arr2):
            ans = min(ans, 1 + solve(i + 1, arr2[idx]))
        
        dp[(i, prev)] = ans
        return ans

    result = solve(0, -1)
    return result if result != float('inf') else -1

Big O Analysis (Optimal)

Time Complexity: O(n * m * log m), where 'n' is the length of arr1 and 'm' is the length of arr2. The n comes from iterating through arr1. The m log m comes from the initial sorting of arr2 and the usage of bisect method (Binary Search on sorted arr2).
Space Complexity: O(n * m) because of the DP table storing the results of the solve function with memoization.

Solution

Naive Approach (Brute Force)

This approach is highly inefficient due to the exponential number of possible combinations. It would quickly exceed the time limit for larger input sizes.

Big O Analysis (Naive)

Time Complexity: O(mⁿ), where 'n' is the length of arr1 and 'm' is the length of arr2. In the worst case, for each element in arr1, we might try replacing it with every element in arr2.
Space Complexity: O(n) due to the recursive call stack.

Optimal Approach (Dynamic Programming)

Initialization: We start by initializing the base cases for the first element of arr1.
Iteration: For each subsequent element in arr1, we have two choices:
- Keep the element if it is greater than the previous element (either the original or a replacement).
- Replace the element with an element from arr2 that is greater than the previous element.
Binary Search: To efficiently find the smallest element in arr2 that is greater than the previous element, we can use binary search after sorting arr2 and removing duplicate elements.

Edge Cases

Empty arrays: Handle cases where arr1 or arr2 are empty.
Unsorted arr2: Sort and deduplicate arr2 before using binary search.
No solution: If at any point we cannot find a valid replacement or keep the element, return -1.

Code Implementation (Python)

import bisect

def makeArrayIncreasing(arr1, arr2):
    arr2 = sorted(list(set(arr2)))
    n = len(arr1)
    
    dp = {}

    def solve(i, prev):
        if i == n:
            return 0
        
        if (i, prev) in dp:
            return dp[(i, prev)]
        
        ans = float('inf')
        
        # Option 1: Keep arr1[i] if possible
        if arr1[i] > prev:
            ans = min(ans, solve(i + 1, arr1[i]))
        
        # Option 2: Replace arr1[i] with an element from arr2
        idx = bisect.bisect_right(arr2, prev)
        if idx < len(arr2):
            ans = min(ans, 1 + solve(i + 1, arr2[idx]))
        
        dp[(i, prev)] = ans
        return ans

    result = solve(0, -1)
    return result if result != float('inf') else -1

Big O Analysis (Optimal)

Time Complexity: O(n * m * log m), where 'n' is the length of arr1 and 'm' is the length of arr2. The n comes from iterating through arr1. The m log m comes from the initial sorting of arr2 and the usage of bisect method (Binary Search on sorted arr2).
Space Complexity: O(n * m) because of the DP table storing the results of the solve function with memoization.