Skip to main content
Talentd

Minimum Swaps To Make Sequences Increasing - Solution & Explanation

HardArrayDynamic Programming18 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 <= 105
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 2 * 105

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.

The above C code uses two arrays to track the minimum swaps required at each index with and without swapping. By initializing keep[0] as 0 and swap[0] as 1, it allows the first position either unswapped or swapped. The logic then calculates for each subsequent index the minimum swaps based on previous indices, ensuring the strictly increasing sequence.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of two arrays for tracking the minimum swaps.

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of two arrays for tracking the minimum swaps.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(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 ProgrammingO(n)O(1)Production or interview solution with minimal memory usage

Video Solution

Leetcode Contest 76 Problem 2 - Minimum Swaps To Make Sequences Increasing • code_report • 26,980 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Swaps To Make Sequences Increasing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Make the Array K-Increasing

Next

Minimum Operations to Maximize Last Elements in Arrays