ArrayProblem 33 of 36
Minimum swaps required bring elements less equal K together
Problem Statement
Given an array of n positive integers and a number k, find the minimum number of swaps required to bring all elements less than or equal to k together (in a contiguous subarray).
Example:
- Input:
arr = [2, 1, 5, 6, 3],k = 3 - Output:
1 - Explanation: Elements ≤ 3 are 3. We need to bring them together. One swap of 5 and 3 gives [2, 1, 3, 6, 5].
Approach 1: Brute Force
Intuition
Count elements ≤ k (let it be 'count'). For every window of size 'count', count elements > k. The minimum such count is the answer.
Algorithm
- Count total elements ≤ k (this will be our window size)
- For each possible window of this size
- Count elements > k in the window (these need to be swapped out)
- Track minimum swaps needed
java
public class Solution {
public int minSwaps(int[] arr, int k) {
int n = arr.length;
// Count elements <= k
int count = 0;
for (int num : arr) {
if (num <= k) count++;
}
// Edge cases
if (count == 0 || count == n) return 0;
int minSwaps = Integer.MAX_VALUE;
// Check all windows of size 'count'
for (int i = 0; i <= n - count; i++) {
int badElements = 0;
for (int j = i; j < i + count; j++) {
if (arr[j] > k) {
badElements++;
}
}
minSwaps = Math.min(minSwaps, badElements);
}
return minSwaps;
}
}Complexity Analysis
- Time Complexity: O(n²) - For each window position, we traverse the entire window
- Space Complexity: O(1) - Only constant extra space
Approach 2: Optimal - Sliding Window
Intuition
Use sliding window technique. Maintain count of "bad" elements (elements > k) in current window. Slide the window and update count efficiently.
Algorithm
- Count elements ≤ k (this is window size)
- Count bad elements in first window
- Slide window: remove contribution of outgoing element, add incoming element
- Track minimum bad elements count
java
public class Solution {
public int minSwaps(int[] arr, int k) {
int n = arr.length;
// Count elements <= k (window size)
int windowSize = 0;
for (int num : arr) {
if (num <= k) windowSize++;
}
// Edge cases
if (windowSize == 0 || windowSize == n) return 0;
// Count bad elements in first window
int badCount = 0;
for (int i = 0; i < windowSize; i++) {
if (arr[i] > k) badCount++;
}
int minSwaps = badCount;
// Slide the window
for (int i = windowSize; i < n; i++) {
// Add incoming element
if (arr[i] > k) badCount++;
// Remove outgoing element
if (arr[i - windowSize] > k) badCount--;
minSwaps = Math.min(minSwaps, badCount);
}
return minSwaps;
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass to count, single pass to slide window
- Space Complexity: O(1) - Only constant extra space
Variation: Return the Window Position
Intuition
Track not just minimum swaps but also the starting index of the optimal window.
java
public class Solution {
public int[] minSwapsWithPosition(int[] arr, int k) {
int n = arr.length;
// Count elements <= k
int windowSize = 0;
for (int num : arr) {
if (num <= k) windowSize++;
}
if (windowSize == 0 || windowSize == n) return new int[]{0, 0};
// Count bad elements in first window
int badCount = 0;
for (int i = 0; i < windowSize; i++) {
if (arr[i] > k) badCount++;
}
int minSwaps = badCount;
int optimalStart = 0;
// Slide the window
for (int i = windowSize; i < n; i++) {
if (arr[i] > k) badCount++;
if (arr[i - windowSize] > k) badCount--;
if (badCount < minSwaps) {
minSwaps = badCount;
optimalStart = i - windowSize + 1;
}
}
return new int[]{minSwaps, optimalStart};
}
}Complexity Analysis
- Time Complexity: O(n) - Same as optimal approach
- Space Complexity: O(1) - Only constant extra space
Key Takeaways
- Window size is fixed - Number of elements ≤ k determines window size
- Count "bad" elements - Minimize elements > k in window (these need swapping)
- Sliding window optimization - Update count incrementally instead of recounting
- Swap interpretation - Each bad element in optimal window needs one swap
- Similar problems - Minimum swaps for sorting, grouping elements by property