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

Minimum Swaps To Make Sequences Increasing

Number: 819

Difficulty: Hard

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Given two integer arrays nums1 and nums2 of equal length, you can perform swaps at the same index between the two arrays. The goal is to return the minimum number of swaps required such that both arrays become strictly increasing. A sequence is strictly increasing if every element is greater than its previous one.

Key Insights

  • Use dynamic programming to decide at each index whether to swap or not.
  • Define two states: one where no swap is performed at the current index, and one where a swap is performed.
  • Transition between states requires consistency with the previous values ensuring both arrays remain strictly increasing.
  • Two valid conditions can exist at each index:
    1. Both arrays naturally increasing without a swap at the current index.
    2. A swap can help maintain order when considering the swapped value from the previous index.
  • Optimize space by maintaining only the latest state.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

The solution uses dynamic programming with two variables to track the minimum number of swaps needed up to the current index when either not swapping or swapping at that index. We initialize prevNoSwap to 0 and prevSwap to 1, representing the first index (no swap and a swap, respectively).
For every subsequent index, we update the current state (curNoSwap and curSwap) based on two conditions:

  1. If both arrays continue to be increasing without a swap.
  2. If swapping at the current index (considering the swapped previous state) ensures both arrays are strictly increasing.
    Finally, the answer is the minimum of the two states at the last index.

Code Solutions

def minSwap(nums1, nums2):
    n = len(nums1)
    # Initialize dp states: no swap and swap for index 0
    prev_no_swap = 0  # No swap at index 0
    prev_swap = 1     # Swap at index 0

    for i in range(1, n):
        # Initialize current states with a high value
        curr_no_swap = float('inf')
        curr_swap = float('inf')

        # Condition 1: both sequences are increasing without swap at the current index
        if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
            # if no swap at i, carry forward cost from previous no swap state
            curr_no_swap = min(curr_no_swap, prev_no_swap)
            # if swap at i, add one swap to the previous swap state
            curr_swap = min(curr_swap, prev_swap + 1)

        # Condition 2: swapping at current i allows crossing scenario
        if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
            # if no swap at i, but previous index was swapped
            curr_no_swap = min(curr_no_swap, prev_swap)
            # if swap at i, plus one swap to previous no swap state
            curr_swap = min(curr_swap, prev_no_swap + 1)

        # Update the previous states
        prev_no_swap = curr_no_swap
        prev_swap = curr_swap

    return min(prev_no_swap, prev_swap)

# Example usage:
nums1 = [1,3,5,4]
nums2 = [1,2,3,7]
print(minSwap(nums1, nums2))  # Expected output: 1
← Back to All Questions