Skip to main content
Talentd

Minimum Adjacent Swaps to Partition Array - Solution & Explanation

MediumArrayGreedy4 min read
Practice this problem

Problem Statement

You are given an integer array nums and two integers a and b such that a < b.

An array is called good if it can be split into three contiguous parts, in this order, such that:

  • Every element in the first part is less than a.
  • Every element in the second part is in the range [a, b] inclusive.
  • Every element in the third part is greater than b.

Any of the three parts may be empty.

In one adjacent swap, you may swap two neighboring elements of nums.

Return the minimum number of adjacent swaps required to make nums good. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,3,2,4,5,6], a = 3, b = 4

Output: 1

Explanation:

  • Swap nums[1] and nums[2]. The array becomes [1, 2, 3, 4, 5, 6].
  • This array is good because it can be split into [1, 2], [3, 4], and [5, 6].

Example 2:

Input: nums = [9,7,5,3], a = 4, b = 8

Output: 5

Explanation:

One sequence of optimal swaps is as follows:

  • Swap nums[2] and nums[3]. The array becomes [9, 7, 3, 5].
  • Swap nums[1] and nums[2]. The array becomes [9, 3, 7, 5].
  • Swap nums[0] and nums[1]. The array becomes [3, 9, 7, 5].
  • Swap nums[1] and nums[2]. The array becomes [3, 7, 9, 5].
  • Swap nums[2] and nums[3]. The array becomes [3, 7, 5, 9].
  • This array is good because it can be split into [3], [7, 5], and [9].

Example 3:

Input: nums = [3,7,5,9], a = 4, b = 8

Output: 0

Explanation:

The array is already good. No swaps are needed.

 

Constraints:

  • 1 <= nums.length <= 105
  • ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹1 <= nums[i] <= 109
  • 1 <= a < b <= 109ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Approach Overview

Problem Overview: You need to partition the array so elements satisfying a condition end up on one side while minimizing adjacent swaps. Since only neighboring elements can be swapped, the total cost depends on how far misplaced values must travel.

Approach 1: Brute Force Swap Simulation (Time: O(n2), Space: O(1))

Scan the array and whenever you find an element on the wrong side, repeatedly swap it with adjacent elements until it reaches its correct partition. This directly simulates the operation described in the problem, which makes it easy to reason about correctness. The downside is that each misplaced value may move across a large section of the array, leading to quadratic runtime. This approach is useful for validating edge cases before optimizing.

Approach 2: Two Pointers with Misplaced Index Tracking (Time: O(n), Space: O(1))

Use two pointers from both ends to locate elements that belong in the opposite partition. Instead of physically simulating every swap, count how many positions each element must cross. The key insight is that adjacent swaps are equivalent to shifting misplaced elements across invalid positions. You iterate once through the array, update the swap count using index differences, and move both pointers inward. This is the standard interview solution because it removes redundant swaps while preserving the exact minimum cost.

Approach 3: Greedy Position Compression (Time: O(n), Space: O(n))

Store the indices of all elements that should belong together and calculate the distance required to move them into contiguous positions. This transforms the problem into minimizing movement between original and target indices. The approach is common in greedy and two pointers problems because it avoids repeated array modifications. If the partition rule depends on parity, sign, or binary values, this technique produces a clean implementation with predictable runtime.

Recommended for interviews: Interviewers usually expect the linear-time greedy or two-pointer solution. Starting with brute force shows that you understand how adjacent swaps behave, but the optimized approach demonstrates stronger algorithmic reasoning and awareness of array movement costs.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Swap SimulationO(n^2)O(1)Small arrays or debugging correctness
Two Pointers with Swap CountingO(n)O(1)General optimal interview solution
Greedy Position CompressionO(n)O(n)When tracking target indices explicitly

Video Solution

LeetCode 3994 | Biweekly Contest 187 Q3 | Minimum Adjacent Swaps to Partition Array | Easy Greedy šŸ˜® ā€¢ CodeSprint ā€¢ 270 views views

Watch 5 more video solutions ā†’

Frequently Asked Questions

Is Minimum Adjacent Swaps to Partition Array easy or hard?
The problem is generally considered medium difficulty because the brute force idea is simple, but deriving the optimal swap-counting strategy requires stronger insight into adjacent movement and greedy optimization.
Minimum Adjacent Swaps to Partition Array Python/Java solution
Python solutions usually use pointer iteration and direct distance accumulation for concise O(n) code. Java implementations follow the same logic with integer counters and array traversal, making both languages efficient for this problem.
How to solve Minimum Adjacent Swaps to Partition Array in O(n)?
Use two pointers to locate elements that belong on opposite sides of the partition. Count the distance each misplaced element must move instead of performing every swap explicitly. Since each index is visited at most once, the algorithm runs in linear time.
What is the best approach for Minimum Adjacent Swaps to Partition Array?
The best approach uses two pointers or greedy index tracking to count how many positions misplaced elements must cross. This avoids simulating every adjacent swap and reduces the runtime to O(n) with constant or linear extra space.
Is Minimum Adjacent Swaps to Partition Array asked at Google/Amazon/Meta?
Adjacent swap and partitioning problems frequently appear in interviews at Google, Amazon, Meta, and other large tech companies. Interviewers use them to evaluate greedy reasoning, pointer manipulation, and array optimization skills.
What data structure is used in Minimum Adjacent Swaps to Partition Array?
Most solutions rely on arrays with two pointers or index lists. Some implementations also use auxiliary vectors or queues to store misplaced positions when computing movement costs efficiently.
What is the time complexity of Minimum Adjacent Swaps to Partition Array?
The brute force simulation runs in O(n^2) time because elements may be shifted repeatedly. The optimized greedy or two-pointer solution processes the array in a single pass, giving O(n) time complexity.

Ready to solve this problem?

Practice Minimum Adjacent Swaps to Partition Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays