(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.
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);
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;
}