Swaps to Sort
A puzzle inspired by my experience working on high-performance systems at Citadel
At Citadel, you’re building a real-time system to process market signals. These signals arrive out of order and need to be sorted in ascending order for risk calculations. Each swap of two signals incurs a computational cost, so your goal is to achieve the correct order with the minimum number of swaps.
Problem Statement
Given an array of unique integers representing market signals, determine the minimum number of swaps required to sort the array in ascending order. A swap involves exchanging two elements of the array.
Example
Input: [4, 3, 1, 2, 5]
Output: 3
Explanation:
1. Swap 4 and 1 → [1, 3, 4, 2, 5]
2. Swap 3 and 2 → [1, 2, 4, 3, 5]
3. Swap 4 and 3 → [1, 2, 3, 4, 5]
Challenge
Provide two O(nlogn) solutions to this problem.
Bonus Challenge
If the input array contains duplicates, prove that the problem is NP-complete.
Counting sort (can handle negative numbers by padding the left, good for small range of numbers in signals):
// solution 2 counting sort
// can be adjusted to accommodate negative numbers by padding the left
int minimumSwaps2(vector<int> signals) {
vector<int> index(*max_element(signals.begin(), signals.end()) + 1, -1);
for (int i = 0; i < signals.size(); ++i)
index[signals[i]] = i;
int ans = 0, cur = 0, i = 0;
while (i < signals.size()){
if (index[cur] == -1) ++cur;
else{
if (i != index[cur]){
++ans;
int prev = index[signals[i]];
index[signals[i]] = index[cur];
swap(signals[index[cur]], signals[prev]);
}
++cur, ++i;
}
}
return ans;
}
Proof: Duplicates Complicate Optimality
(created with the help of GPT after thinking about a specific example and instructing it to focus on index 1 with multiple choices)
Consider the array [1, 3, 2, 2, 4, 2]. The goal is to sort the array with the minimum number of swaps. At index 1, the value is 3, and we need to place a 2 to sort the array correctly. However, there are three options for swapping: 2 at indices 2, 3, and 5. Only one specific choice leads to the optimal solution.
Illustrative Cases
Case 1: Swap 3 (index 1) with the 2 at index 2
Array after the first swap: [1, 2, 3, 2, 4, 2].
The 3 at index 2 now needs to be swapped to its correct position.
Swap 3 (index 2) with 4 (index 4).
Array after the second swap: [1, 2, 4, 2, 3, 2].
Swap 4 (index 2) with 2 (index 5).
Final array: [1, 2, 2, 2, 3, 4].
Total swaps: 3.
Case 2: Swap 3 (index 1) with the 2 at index 3
Array after the first swap: [1, 2, 2, 3, 4, 2].
The 3 at index 3 now needs to be swapped to its correct position.
Swap 3 (index 3) with 4 (index 4).
Array after the second swap: [1, 2, 2, 4, 3, 2].
Swap 4 (index 3) with 2 (index 5).
Final array: [1, 2, 2, 2, 3, 4].
Total swaps: 3.
Case 3: Swap 3 (index 1) with the 2 at index 5
Array after the first swap: [1, 2, 2, 2, 4, 3].
The 3 at index 5 now needs to be swapped to its correct position.
Swap 3 (index 5) with 4 (index 4).
Final array: [1, 2, 2, 2, 3, 4].
Total swaps: 2.
I'll work on creating solution 2, and seeing if a O(n) approach is possible if the range of numbers is small, then work on creating a proof for np-complete when input array has duplicates.
// solution 1
int minimumSwaps(vector<int> signals) {
vector<pair<int,int>> sorted;
for (int i = 0; i < signals.size(); ++i){
sorted.push_back({signals[i], i});
}
sort(sorted.begin(), sorted.end());
int ans = 0;
for (int i = 0; i < signals.size(); ++i){
if (signals[i] != sorted[i].first){
++ans;
pair<int,int> bsearch = {signals[i], INT_MIN};
auto it = lower_bound(sorted.begin(), sorted.end(), bsearch);
auto [f,s] = *it;
swap(signals[s], signals[sorted[i].second]);
it->second = sorted[i].second;
}
}
return ans;
}