Minimum Swaps To Make Sequences Increasing

Minimum Swaps To Make Sequences Increasing - Problem

You are given two integer arrays of the same length nums1 and nums2. In one operation, you are allowed to swap nums1[i] with nums2[i].

For example, if nums1 = [1,2,3,8] and nums2 = [5,6,7,4], you can swap the element at i = 3 to obtain nums1 = [1,2,3,4] and nums2 = [5,6,7,8].

Return the minimum number of needed operations to make nums1 and nums2 strictly increasing. The test cases are generated so that the given input always makes it possible.

An array arr is strictly increasing if and only if arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1].

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7]

› Output: 1

💡 Note: Swap nums1[3] and nums2[3] to get nums1 = [1,3,5,7] and nums2 = [1,2,3,4]. Both arrays become strictly increasing with 1 swap.

Example 2 — No Swaps Needed

$ Input: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]

› Output: 1

💡 Note: Need to swap at position 1 to make both sequences strictly increasing: nums1 = [0,1,5,8,9], nums2 = [2,3,4,6,9].

Example 3 — Multiple Valid Solutions

$ Input: nums1 = [1,2], nums2 = [3,4]

› Output: 0

💡 Note: Both arrays are already strictly increasing, so no swaps needed.

Constraints

2 ≤ nums1.length == nums2.length ≤ 1000
0 ≤ nums1[i], nums2[i] ≤ 2000

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays nums1=[1,3,5,4] and nums2=[1,2,3,7] that need to be strictly increasing

Process

Identify positions where swapping helps maintain increasing order

Output

Minimum number of swaps needed: 1

Key Takeaway

🎯 Key Insight: Use dynamic programming to track minimum swaps for keep/swap states at each position

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use dynamic programming to track two states at each position: minimum swaps needed if we keep the current pair, and minimum swaps if we swap the current pair. The optimal approach uses O(n) time and O(1) space by maintaining these states as we iterate through the arrays.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible swap combinations and find the minimum that creates strictly increasing sequences
Dynamic Programming - State Tracking	O(n)	O(1)	Track minimum swaps needed at each position considering whether we swap or not

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all 2^n possible swap combinations
Step 2: For each combination, check if both arrays are strictly increasing
Step 3: Among valid combinations, return the one with minimum swaps

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible swap patterns using bitmasks

Validate

Check if each combination creates strictly increasing arrays

Minimize

Return the valid combination with minimum swaps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums1, int* nums2, int n) {
    int minSwaps = INT_MAX;
    
    // Try all 2^n combinations
    for (int mask = 0; mask < (1 << n); mask++) {
        int temp1[1000], temp2[1000];
        memcpy(temp1, nums1, n * sizeof(int));
        memcpy(temp2, nums2, n * sizeof(int));
        int swaps = 0;
        
        // Apply swaps based on mask
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                int tmp = temp1[i];
                temp1[i] = temp2[i];
                temp2[i] = tmp;
                swaps++;
            }
        }
        
        // Check if both arrays are strictly increasing
        int valid = 1;
        for (int i = 1; i < n; i++) {
            if (temp1[i] <= temp1[i-1] || temp2[i] <= temp2[i-1]) {
                valid = 0;
                break;
            }
        }
        
        if (valid && swaps < minSwaps) {
            minSwaps = swaps;
        }
    }
    
    return minSwaps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int nums1[1000], nums2[1000], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums1[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    // Parse second array
    int n2 = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums2[n2++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, nums2, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

2^n combinations to try, each taking O(n) to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing current combination and arrays

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler