We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make Array Strictly Increasing

Difficulty: Hard

Problem Description

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.

Key Insights

  • The elements of arr1 must be strictly increasing, meaning each subsequent element must be greater than the previous one.
  • We can replace elements in arr1 with those from arr2 to achieve a strictly increasing order.
  • A binary search can help efficiently find suitable replacements in arr2 that maintain the strictly increasing property.
  • Dynamic programming can be used to keep track of the minimum operations needed to achieve the desired order.

Space and Time Complexity

Time Complexity: O(n * log(m)), where n is the length of arr1 and m is the length of arr2.
Space Complexity: O(n), for storing the dynamic programming states.

Solution

To solve this problem, we can utilize dynamic programming combined with binary search. We maintain a list that represents the minimum last value of a strictly increasing sequence we can achieve with each length using elements from arr2. For each element in arr1, we try to either keep it or replace it with a suitable element from arr2. The binary search helps in finding the smallest valid replacement to maintain the strictly increasing property. If we cannot replace an element in a way that keeps the sequence valid, we return -1.

Code Solutions

def makeArrayIncreasing(arr1, arr2):
    arr2 = sorted(set(arr2))  # Remove duplicates and sort arr2
    n = len(arr1)
    dp = {0: -1}  # dp[i] = minimum number of operations to make arr1[0:i] strictly increasing
    
    for num in arr1:
        new_dp = {}
        for k, last in dp.items():
            # Case 1: Keep arr1[i]
            if num > last:
                new_dp[k] = min(new_dp.get(k, float('inf')), last)
            # Case 2: Replace arr1[i] with an element from arr2
            idx = bisect.bisect_right(arr2, last)  # Find a valid replacement
            if idx < len(arr2):
                new_dp[k + 1] = min(new_dp.get(k + 1, float('inf')), arr2[idx])
        
        dp = new_dp  # Move to the next element in arr1

    # Find the minimum operations
    min_ops = min(dp.keys(), default=float('inf'))
    return min_ops if min_ops != float('inf') else -1
← Back to All Questions