801. Minimum Swaps To Make Sequences Increasing Solution

The 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].

Example 1:

Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
Output: 1
Explanation: 
Swap nums1[3] and nums2[3]. Then the sequences are:
nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4]
which are both strictly increasing.

Example 2:

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

Constraints:

2 <= nums1.length <= 10⁵
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 10⁵

Approach overview

Problem Overview: You are given two equal-length integer arrays. At any index you may swap the elements between the arrays. The goal is to perform the minimum number of swaps so both arrays become strictly increasing.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

At every index you have two choices: keep the pair as is or swap the elements between the arrays. Recursively explore both options while checking whether the sequences remain strictly increasing relative to the previous index. If the current values violate the increasing condition, prune that branch. The recursion tracks the last chosen values and counts swaps. This approach demonstrates the core decision structure but quickly becomes impractical because it explores up to 2^n states.

Approach 2: Dynamic Programming with State Arrays (O(n) time, O(n) space)

The key observation: at each index you only care about two states — whether you swapped at this index or not. Maintain two arrays: keep[i] (minimum swaps if index i is not swapped) and swap[i] (minimum swaps if index i is swapped). Transition based on whether the current elements maintain the strictly increasing order relative to the previous index. If A[i] > A[i-1] and B[i] > B[i-1], the previous state can carry forward. If A[i] > B[i-1] and B[i] > A[i-1], a cross transition (swap vs keep) is also valid. This dynamic programming formulation reduces the exponential search to a linear scan.

Approach 3: Space Optimized Dynamic Programming (O(n) time, O(1) space)

You only need results from the previous index, so the keep and swap arrays can be compressed into two variables. Iterate from left to right and update the next state using temporary variables. For each position, evaluate the two ordering conditions and update the minimum swaps accordingly. This keeps the logic identical to the DP formulation but reduces memory usage to constant space. The algorithm performs a single pass through the arrays, making it the optimal solution.

Recommended for interviews: The space‑optimized dynamic programming approach. It shows you recognized the two-state dependency and reduced the DP table to constant memory. Interviewers often expect candidates to first reason about the decision (swap vs keep), derive the DP transition, and then optimize space. The problem strongly tests reasoning with ordered sequences in arrays and state transitions in dynamic programming.

Approach 1: Dynamic Programming Approach

In this approach, we use dynamic programming (DP) to solve the problem efficiently. We maintain two arrays, keep and swap, where keep[i] denotes the minimum number of swaps needed to make the sequences increasing up to index i without swapping at i, and swap[i] denotes the minimum swaps with a swap at position i.

Initialize keep[0] = 0 and swap[0] = 1 as the first position doesn't require any operation unless swapped. Then for each index i, we calculate keep[i] and swap[i] based on previous values while ensuring the increasing order condition is maintained.

Python

class Solution:
    def minSwap(self, nums1, nums2):
        n = len(nums1)
        keep = [float('inf')] * n
        swap = [float('inf')] * n
        keep[0] = 0
        swap[0] = 1

        for i in range(1, n):
            if nums1[i-1] < nums1[i] and nums2[i-1] < nums2[i]:
                keep[i] = keep[i - 1]
                swap[i] = swap[i - 1] + 1
            if nums1[i-1] < nums2[i] and nums2[i-1] < nums1[i]:
                keep[i] = min(keep[i], swap[i - 1])
                swap[i] = min(swap[i], keep[i - 1] + 1)

        return min(keep[-1], swap[-1])

# Example usage:
solution = Solution()
print(solution.minSwap([1, 3, 5, 4], [1, 2, 3, 7]))

Java

public class MinSwap {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] keep = new int[n];
        int[] swap = new int[n];
        keep[0] = 0;
        swap[0] = 1;

        for (int i = 1; i < n; i++) {
            keep[i] = swap[i] = Integer.MAX_VALUE;
            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
                keep[i] = keep[i - 1];
                swap[i] = swap[i - 1] + 1;
            }
            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                keep[i] = Math.min(keep[i], swap[i - 1]);
                swap[i] = Math.min(swap[i], keep[i - 1] + 1);
            }
        }
        return Math.min(keep[n - 1], swap[n - 1]);
    }

    public static void main(String[] args) {
        MinSwap solution = new MinSwap();
        int[] nums1 = {1, 3, 5, 4};
        int[] nums2 = {1, 2, 3, 7};
        System.out.println("Minimum swaps needed: " + solution.minSwap(nums1, nums2));
    }
}

C++

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minSwap(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    vector<int> keep(n, INT_MAX), swap(n, INT_MAX);
    keep[0] = 0; swap[0] = 1;

    for (int i = 1; i < n; ++i) {
        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
            keep[i] = keep[i - 1];
            swap[i] = swap[i - 1] + 1;
        }
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
            keep[i] = min(keep[i], swap[i - 1]);
            swap[i] = min(swap[i], keep[i - 1] + 1);
        }
    }
    return min(keep[n - 1], swap[n - 1]);
}

int main() {
    vector<int> nums1 = {1, 3, 5, 4};
    vector<int> nums2 = {1, 2, 3, 7};
    int result = minSwap(nums1, nums2);
    cout << "Minimum swaps needed: " << result << endl;
    return 0;
}

JavaScript

var minSwap = function(nums1, nums2) {
    const n = nums1.length;
    const keep = Array(n).fill(Infinity);
    const swap = Array(n).fill(Infinity);
    keep[0] = 0;
    swap[0] = 1;

    for (let i = 1; i < n; i++) {
        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
            keep[i] = keep[i - 1];
            swap[i] = swap[i - 1] + 1;
        }
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
            keep[i] = Math.min(keep[i], swap[i - 1]);
            swap[i] = Math.min(swap[i], keep[i - 1] + 1);
        }
    }
    return Math.min(keep[n - 1], swap[n - 1]);
};

// Example usage:
console.log(minSwap([1, 3, 5, 4], [1, 2, 3, 7]));

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

int minSwap(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int keep[nums1Size];
    int swap[nums1Size];
    keep[0] = 0; swap[0] = 1;

    for (int i = 1; i < nums1Size; ++i) {
        keep[i] = swap[i] = INT_MAX;
        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
            keep[i] = keep[i - 1];
            swap[i] = swap[i - 1] + 1;
        }
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
            keep[i] = (keep[i] < swap[i - 1] ? keep[i] : swap[i - 1]);
            swap[i] = (swap[i] < keep[i - 1] + 1 ? swap[i] : keep[i - 1] + 1);
        }
    }
    return keep[nums1Size - 1] < swap[nums1Size - 1] ? keep[nums1Size - 1] : swap[nums1Size - 1];
}

int main() {
    int nums1[] = {1, 3, 5, 4};
    int nums2[] = {1, 2, 3, 7};
    int result = minSwap(nums1, 4, nums2, 4);
    printf("Minimum swaps needed: %d\n", result);
    return 0;
}

public class Solution {
    public int MinSwap(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int[] keep = new int[n];
        int[] swap = new int[n];
        keep[0] = 0; swap[0] = 1;

        for (int i = 1; i < n; i++) {
            keep[i] = swap[i] = int.MaxValue;
            if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {
                keep[i] = keep[i-1];
                swap[i] = swap[i-1] + 1;
            }
            if (nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]) {
                keep[i] = Math.Min(keep[i], swap[i-1]);
                swap[i] = Math.Min(swap[i], keep[i-1] + 1);
            }
        }
        return Math.Min(keep[n-1], swap[n-1]);
    }

    public static void Main() {
        var solution = new Solution();
        Console.WriteLine("Minimum swaps needed: " + solution.MinSwap(new int[] {1, 3, 5, 4}, new int[] {1, 2, 3, 7}));
    }
}

This Python solution implements the dynamic programming approach, using arrays keep and swap to store minimum swap counts. Similar to other languages, it iterates through elements to determine state updates, ensuring strict sequences.

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the lists used for storing DP states.

Try this approach in the editor

Approach 2: Dynamic Programming

Define a and b to represent the minimum number of swaps needed to make the element sequences strictly increasing up to index [0..i], with the i-th element not swapped and swapped, respectively. The index starts from 0.

When i=0, we have a = 0 and b = 1.

When i \gt 0, we first save the previous values of a and b in x and y, and then discuss the following cases:

If nums1[i - 1] \ge nums1[i] or nums2[i - 1] \ge nums2[i], to make both sequences strictly increasing, the relative positions of the elements at indices i-1 and i must change. That is, if the previous position was swapped, then the current position should not be swapped, so a = y; if the previous position was not swapped, then the current position must be swapped, so b = x + 1.

Otherwise, the relative positions of the elements at indices i-1 and i do not need to change, so b = y + 1. Additionally, if nums1[i - 1] \lt nums2[i] and nums2[i - 1] \lt nums1[i], the relative positions of the elements at indices i-1 and i can change, so a and b can take the smaller values, thus a = min(a, y) and b = min(b, x + 1).

Finally, return the smaller value between a and b.

The time complexity is O(n), and the space complexity is O(1).

TypeScript

function minSwap(nums1: number[], nums2: number[]): number {
    let [a, b] = [0, 1];
    for (let i = 1; i < nums1.length; ++i) {
        let x = a,
            y = b;
        if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
            a = y;
            b = x + 1;
        } else {
            b = y + 1;
            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                a = Math.min(a, y);
                b = Math.min(b, x + 1);
            }
        }
    }
    return Math.min(a, b);
}

func minSwap(nums1 []int, nums2 []int) int {
	a, b, n := 0, 1, len(nums1)
	for i := 1; i < n; i++ {
		x, y := a, b
		if nums1[i-1] >= nums1[i] || nums2[i-1] >= nums2[i] {
			a, b = y, x+1
		} else {
			b = y + 1
			if nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i] {
				a = min(a, y)
				b = min(b, x+1)
			}
		}
	}
	return min(a, b)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n), where `n` is the length of the array. Space Complexity: O(n), due to the lists used for storing DP states.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Recursion	O(2^n)	O(n)	Conceptual understanding of swap vs keep decisions
Dynamic Programming (DP Arrays)	O(n)	O(n)	Clear DP formulation when teaching or debugging transitions
Space Optimized Dynamic Programming	O(n)	O(1)	Production or interview solution with minimal memory usage

Frequently asked questions

Is Minimum Swaps To Make Sequences Increasing easy or hard?

Minimum Swaps To Make Sequences Increasing is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the two-state dynamic programming pattern and correctly handling both normal and cross ordering conditions between adjacent indices.

Minimum Swaps To Make Sequences Increasing Python/Java solution

Implement the dynamic programming approach with two variables: keep and swap. Initialize keep = 0 and swap = 1, then iterate through the arrays updating the states based on ordering conditions. The same logic works across Python, Java, C++, C#, and JavaScript with O(n) time and constant space.

How to solve Minimum Swaps To Make Sequences Increasing in O(n)?

Track two values while scanning the arrays: the minimum swaps if the current index is swapped and if it is not swapped. At each step check two conditions: normal increasing order (A[i] > A[i-1] and B[i] > B[i-1]) and cross increasing order (A[i] > B[i-1] and B[i] > A[i-1]). Update the swap and keep states accordingly. This dynamic programming transition produces the answer in linear time.

What is the best approach for Minimum Swaps To Make Sequences Increasing?

The best approach uses dynamic programming with two states per index: keep and swap. keep[i] represents the minimum swaps if you do not swap at index i, while swap[i] represents the minimum swaps if you swap at that index. By evaluating ordering conditions between current and previous elements, the algorithm updates these states in a single pass. The optimized version runs in O(n) time and O(1) space.

Is Minimum Swaps To Make Sequences Increasing asked at Google/Amazon/Meta?

This problem appears in interview preparation sets for major tech companies including Google, Amazon, and Meta because it tests dynamic programming with state transitions. Candidates must reason about multiple valid transitions and maintain minimal cost across states.

What data structure is used in Minimum Swaps To Make Sequences Increasing?

The solution primarily relies on arrays and dynamic programming states. Two variables or DP arrays track the minimum swaps when keeping or swapping the current index. No advanced data structures are required beyond basic arrays and integer state tracking.

What is the time complexity of Minimum Swaps To Make Sequences Increasing?

The optimal dynamic programming solution runs in O(n) time because it processes each index once and performs constant-time state updates. Space complexity can be reduced from O(n) to O(1) by storing only the previous keep and swap values instead of full arrays.

Minimum Swaps To Make Sequences Increasing solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Swaps To Make Sequences Increasing solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems