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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Array Strictly Increasing

Number: 1290

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two integer arrays, arr1 and arr2, the goal is to make arr1 strictly increasing with the minimum number of replacement operations. In one operation you may replace any element in arr1 with any element from arr2. If it is impossible to make arr1 strictly increasing, return -1.

Key Insights

  • The problem requires a careful decision at each index whether to keep the existing element or replace it.
  • Using dynamic programming helps to model choices with state (current index, last value used) while ensuring the strictly increasing order.
  • Sorting and deduplicating arr2 enables efficient binary search for the least candidate in arr2 that is greater than a given value.
  • The decision involves two options: (1) No replacement if the next element is larger than the current "previous" value; (2) Replacement with the smallest valid candidate from arr2.
  • Memoization is vital to avoid recomputation and reduce the exponential search space.

Space and Time Complexity

Time Complexity: O(n * m * log(m)) where n is the length of arr1 and m is the length of arr2.
Space Complexity: O(n * m) due to the memoization cache used during the dynamic programming recursion.

Solution

We solve the problem using recursion with memoization by defining a state dp(index, prev) which returns the minimum operations needed from index onward given that the previous value in the “increasing” sequence is prev.
Steps:

  1. Sort and deduplicate arr2.
  2. At each index, if arr1[index] is greater than prev, we have the option to keep arr1[index] (i.e., no operation).
  3. Regardless, we can also try to replace arr1[index] with the smallest element in arr2 that is greater than prev (found using binary search), and count one replacement.
  4. The minimum number of operations over these two choices (if valid) forms the solution.
  5. If no valid sequence can be built, return -1.

Key data structures and techniques include:

  • Dynamic Programming with memoization to cache computed states.
  • Binary Search (using the sorted arr2) to efficiently locate the smallest valid replacement element.

Code Solutions

# Python solution with detailed comments
from functools import lru_cache
import bisect

def makeArrayIncreasing(arr1, arr2):
    # Sort and remove duplicates from arr2
    arr2 = sorted(set(arr2))
    
    # Recursive function with memoization to determine the minimum operations.
    @lru_cache(maxsize=None)
    def dp(index, prev):
        # If we have processed all elements in arr1, no further operations needed.
        if index == len(arr1):
            return 0
        
        minOperations = float('inf')
        
        # Option 1: Do not replace arr1[index] if it is greater than the last value 'prev'
        if arr1[index] > prev:
            minOperations = dp(index + 1, arr1[index])
        
        # Option 2: Replace arr1[index] with an element in arr2 
        # We need the smallest element in arr2 that is greater than 'prev'
        pos = bisect.bisect_right(arr2, prev)
        if pos < len(arr2):
            # Count one replacement operation and continue recursion with the chosen value.
            minOperations = min(minOperations, 1 + dp(index + 1, arr2[pos]))
        
        return minOperations
    
    result = dp(0, -1)  # Use -1 as the initial previous value (since arr1[i]>=0)
    return result if result != float('inf') else -1

# Example usage:
print(makeArrayIncreasing([1,5,3,6,7], [1,3,2,4]))  # Expected output: 1
← Back to All Questions