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:
a.[a, b] inclusive.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:
nums[1] and nums[2]. The array becomes [1, 2, 3, 4, 5, 6].[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:
nums[2] and nums[3]. The array becomes [9, 7, 3, 5].nums[1] and nums[2]. The array becomes [9, 3, 7, 5].nums[0] and nums[1]. The array becomes [3, 9, 7, 5].nums[1] and nums[2]. The array becomes [3, 7, 9, 5].nums[2] and nums[3]. The array becomes [3, 7, 5, 9].[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 <= 1051 <= nums[i] <= 1091 <= a < b <= 109Problem 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| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Swap Simulation | O(n^2) | O(1) | Small arrays or debugging correctness |
| Two Pointers with Swap Counting | O(n) | O(1) | General optimal interview solution |
| Greedy Position Compression | O(n) | O(n) | When tracking target indices explicitly |
LeetCode 3994 | Biweekly Contest 187 Q3 | Minimum Adjacent Swaps to Partition Array | Easy Greedy 😮 • CodeSprint • 270 views views
Watch 5 more video solutions →Practice Minimum Adjacent Swaps to Partition Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor