Minimum Adjacent Swaps to Partition Array - Video Solutions
LeetCode 3994 | Biweekly Contest 187 Q3 | Minimum Adjacent Swaps to Partition Array | Easy Greedy š®
Minimum Adjacent Swaps to Partition Array - Video Solution
Watch 6 video solutions for Minimum Adjacent Swaps to Partition Array, a medium level problem involving Array, Greedy. This walkthrough by CodeSprint has 270 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]andnums[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]andnums[3]. The array becomes[9, 7, 3, 5]. - Swap
nums[1]andnums[2]. The array becomes[9, 3, 7, 5]. - Swap
nums[0]andnums[1]. The array becomes[3, 9, 7, 5]. - Swap
nums[1]andnums[2]. The array becomes[3, 7, 9, 5]. - Swap
nums[2]andnums[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] <= 1091 <= 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.
Complexity Analysis
| 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 |