# Sort Products with k-Distance Swaps ## Solution 1: Modulo Grouping with Quadratic Inversion Count ### Intuition - Elements on the shelf can only be swapped if they are exactly a certain distance apart. - This restriction means that an element at a specific starting position can only ever reach positions that differ from it by a multiple of that distance. - We can view the shelf as being divided into several independent groups of products, where products in one group can never move into another. - Within each group, the only allowed operation is swapping items that are effectively "next to each other" in that group's sequence. - The minimum number of such swaps needed to sort any sequence is the number of pairs that are currently in the wrong relative order. - While this logic is correct, checking every single pair in a group becomes extremely time-consuming as the number of products increases. ### Approach - Determine what the final sorted shelf should look like by creating a sorted copy of the input. - Separate the products from both the original and the target sorted shelf into groups based on their index modulo the swap distance. - If the swap distance is zero, we cannot perform any swaps, so we simply check if the shelf is already sorted. - For each group, verify if it contains the same set of products as the corresponding group in the target sorted shelf. - For each group, use a nested loop to count how many pairs of products are out of order (where a larger number appears before a smaller number). - Sum these counts across all groups to find the total operations, returning an error code if the shelf cannot be sorted. ### Pseudocode ```pseudocode minSwaps(n, serial, k) { if k == 0 { for i = 0 to n - 2 { if serial[i] > serial[i + 1] { return -1 } } return 0 } target = copy(serial) sort(target) groups = array of k empty lists targetGroups = array of k empty lists for i = 0 to n - 1 { groups[i % k].append(serial[i]) targetGroups[i % k].append(target[i]) } totalSwaps = 0 for i = 0 to k - 1 { currentGroup = groups[i] invCount = 0 for j = 0 to currentGroup.length - 1 { for m = j + 1 to currentGroup.length - 1 { if currentGroup[j] > currentGroup[m] { invCount = invCount + 1 } } } sort(currentGroup) if currentGroup != targetGroups[i] { return -1 } totalSwaps = totalSwaps + invCount } return totalSwaps } ``` ### Code Implementation #### C++ ```cpp #include #include #include using namespace std; class solution { public: long long minSwaps(int n, vector& serial, int k) { if (k == 0) { for (int i = 0; i < n - 1; i++) { if (serial[i] > serial[i + 1]) return -1; } return 0; } vector target = serial; sort(target.begin(), target.end()); vector> groups(k), targetGroups(k); for (int i = 0; i < n; i++) { groups[i % k].push_back(serial[i]); targetGroups[i % k].push_back(target[i]); } long long totalSwaps = 0; for (int i = 0; i < k; i++) { vector& currentGroup = groups[i]; long long invCount = 0; for (size_t j = 0; j < currentGroup.size(); j++) { for (size_t m = j + 1; m < currentGroup.size(); m++) { if (currentGroup[j] > currentGroup[m]) { invCount++; } } } sort(currentGroup.begin(), currentGroup.end()); if (currentGroup != targetGroups[i]) { return -1; } totalSwaps += invCount; } return totalSwaps; } }; ``` #### Python ```python def minSwaps(self, n, serial, k): if k == 0: for i in range(n - 1): if serial[i] > serial[i + 1]: return -1 return 0 target = sorted(serial) groups = [[] for _ in range(k)] targetGroups = [[] for _ in range(k)] for i in range(n): groups[i % k].append(serial[i]) targetGroups[i % k].append(target[i]) totalSwaps = 0 for i in range(k): currentGroup = groups[i] invCount = 0 size = len(currentGroup) for j in range(size): for m in range(j + 1, size): if currentGroup[j] > currentGroup[m]: invCount += 1 if sorted(currentGroup) != targetGroups[i]: return -1 totalSwaps += invCount return totalSwaps ``` #### Java ```java import java.util.*; class Solution { public long minSwaps(int n, int[] serial, int k) { if (k == 0) { for (int i = 0; i < n - 1; i++) { if (serial[i] > serial[i + 1]) return -1; } return 0; } int[] target = serial.clone(); Arrays.sort(target); List> groups = new ArrayList<>(); List> targetGroups = new ArrayList<>(); for (int i = 0; i < k; i++) { groups.add(new ArrayList<>()); targetGroups.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { groups.get(i % k).add(serial[i]); targetGroups.get(i % k).add(target[i]); } long totalSwaps = 0; for (int i = 0; i < k; i++) { List currentGroup = groups.get(i); long invCount = 0; for (int j = 0; j < currentGroup.size(); j++) { for (int m = j + 1; m < currentGroup.size(); m++) { if (currentGroup.get(j) > currentGroup.get(m)) { invCount++; } } } Collections.sort(currentGroup); List targetGroup = targetGroups.get(i); if (!currentGroup.equals(targetGroup)) { return -1; } totalSwaps += invCount; } return totalSwaps; } } ``` #### JavaScript ```javascript class Solution { static minSwaps(n, serial, k) { if (k === 0) { for (let i = 0; i < n - 1; i++) { if (serial[i] > serial[i + 1]) return -1; } return 0; } const target = [...serial].sort((a, b) => a - b); const groups = Array.from({ length: k }, () => []); const targetGroups = Array.from({ length: k }, () => []); for (let i = 0; i < n; i++) { groups[i % k].push(serial[i]); targetGroups[i % k].push(target[i]); } let totalSwaps = 0; for (let i = 0; i < k; i++) { const currentGroup = groups[i]; let invCount = 0; for (let j = 0; j < currentGroup.length; j++) { for (let m = j + 1; m < currentGroup.length; m++) { if (currentGroup[j] > currentGroup[m]) { invCount++; } } } currentGroup.sort((a, b) => a - b); if (JSON.stringify(currentGroup) !== JSON.stringify(targetGroups[i])) { return -1; } totalSwaps += invCount; } return totalSwaps; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n²/k + n log n)` - **Space Complexity:** `O(n)` --- ## Solution 2: Modulo Grouping with Divide and Conquer Inversion Count ### Intuition - The problem of finding the minimum number of swaps between adjacent items to sort a list is a classic problem solvable by counting inversions. - In our case, items at indices `i` and `i+k` are "adjacent" within their respective modulo-`k` groups. - Instead of using a slow nested loop, we can count inversions much faster by using a modified merge sort. - During the merging process of two sorted halves, every time we pick an element from the right half before the left half, it means that element has "jumped" over all remaining elements in the left half, creating multiple inversions at once. - This divide and conquer approach allows us to process even very large shelves efficiently. ### Approach - Just like the previous method, divide the shelf into `k` independent groups based on index modulo `k`. - Also determine the target contents of each group by looking at a globally sorted version of the shelf. - For each group, use a recursive merge sort function that returns the number of inversions found while sorting. - Inside the merge step, whenever a right-side element is smaller than a left-side element, add the number of remaining left-side elements to the total inversion count. - If the sorted version of a group does not match the target group, it means the products in that group's positions cannot be sorted to reach the global target, so return -1. - Accumulate the results from all groups and return the total. ### Pseudocode ```pseudocode mergeAndCount(arr, left, right) { if left >= right { return 0 } mid = left + (right - left) / 2 count = 0 count = count + mergeAndCount(arr, left, mid) count = count + mergeAndCount(arr, mid + 1, right) temp = [] i = left j = mid + 1 while i <= mid AND j <= right { if arr[i] <= arr[j] { temp.append(arr[i]) i = i + 1 } else { temp.append(arr[j]) count = count + (mid - i + 1) j = j + 1 } } while i <= mid { temp.append(arr[i]) i = i + 1 } while j <= right { temp.append(arr[j]) j = j + 1 } for k = 0 to temp.length - 1 { arr[left + k] = temp[k] } return count } minSwaps(n, serial, k) { if k == 0 { for i = 0 to n - 2 { if serial[i] > serial[i + 1] { return -1 } } return 0 } sortedSerial = copy(serial) sort(sortedSerial) groups = array of k lists targets = array of k lists for i = 0 to n - 1 { groups[i % k].append(serial[i]) targets[i % k].append(sortedSerial[i]) } totalOps = 0 for i = 0 to k - 1 { invs = mergeAndCount(groups[i], 0, groups[i].length - 1) if groups[i] != targets[i] { return -1 } totalOps = totalOps + invs } return totalOps } ``` ### Code Implementation #### C++ ```cpp #include #include #include using namespace std; class solution { public: long long mergeAndCount(vector& arr, int l, int r) { if (l >= r) return 0; int m = l + (r - l) / 2; long long count = mergeAndCount(arr, l, m); count += mergeAndCount(arr, m + 1, r); vector temp; int i = l, j = m + 1; while (i <= m && j <= r) { if (arr[i] <= arr[j]) { temp.push_back(arr[i++]); } else { temp.push_back(arr[j++]); count += (m - i + 1); } } while (i <= m) temp.push_back(arr[i++]); while (j <= r) temp.push_back(arr[j++]); for (int k = 0; k < temp.size(); k++) { arr[l + k] = temp[k]; } return count; } long long minSwaps(int n, vector& serial, int k) { if (k == 0) { for (int i = 0; i < n - 1; i++) { if (serial[i] > serial[i + 1]) return -1; } return 0; } vector sortedSerial = serial; sort(sortedSerial.begin(), sortedSerial.end()); vector> groups(k), targets(k); for (int i = 0; i < n; i++) { groups[i % k].push_back(serial[i]); targets[i % k].push_back(sortedSerial[i]); } long long totalOps = 0; for (int i = 0; i < k; i++) { totalOps += mergeAndCount(groups[i], 0, (int)groups[i].size() - 1); if (groups[i] != targets[i]) return -1; } return totalOps; } }; ``` #### Python ```python class solution: def mergeAndCount(self, arr, l, r): if l >= r: return 0 m = (l + r) // 2 count = self.mergeAndCount(arr, l, m) count += self.mergeAndCount(arr, m + 1, r) temp = [] i, j = l, m + 1 while i <= m and j <= r: if arr[i] <= arr[j]: temp.append(arr[i]) i += 1 else: temp.append(arr[j]) count += (m - i + 1) j += 1 temp.extend(arr[i:m+1]) temp.extend(arr[j:r+1]) for k in range(len(temp)): arr[l + k] = temp[k] return count def minSwaps(self, n, serial, k): if k == 0: for i in range(n - 1): if serial[i] > serial[i + 1]: return -1 return 0 sorted_serial = sorted(serial) groups = [[] for _ in range(k)] targets = [[] for _ in range(k)] for i in range(n): groups[i % k].append(serial[i]) targets[i % k].append(sorted_serial[i]) total_ops = 0 for i in range(k): total_ops += self.mergeAndCount(groups[i], 0, len(groups[i]) - 1) if groups[i] != targets[i]: return -1 return total_ops ``` #### Java ```java import java.util.*; class Solution { private long mergeAndCount(int[] arr, int l, int r) { if (l >= r) return 0; int m = l + (r - l) / 2; long count = mergeAndCount(arr, l, m); count += mergeAndCount(arr, m + 1, r); int[] temp = new int[r - l + 1]; int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; count += (m - i + 1); } } while (i <= m) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; for (int p = 0; p < temp.length; p++) { arr[l + p] = temp[p]; } return count; } public long minSwaps(int n, int[] serial, int k) { if (k == 0) { for (int i = 0; i < n - 1; i++) { if (serial[i] > serial[i + 1]) return -1; } return 0; } int[] sortedSerial = serial.clone(); Arrays.sort(sortedSerial); List> groupsList = new ArrayList<>(); List> targetsList = new ArrayList<>(); for (int i = 0; i < k; i++) { groupsList.add(new ArrayList<>()); targetsList.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { groupsList.get(i % k).add(serial[i]); targetsList.get(i % k).add(sortedSerial[i]); } long totalOps = 0; for (int i = 0; i < k; i++) { List g = groupsList.get(i); int[] currentArr = new int[g.size()]; for (int j = 0; j < g.size(); j++) currentArr[j] = g.get(j); totalOps += mergeAndCount(currentArr, 0, currentArr.length - 1); List t = targetsList.get(i); for (int j = 0; j < currentArr.length; j++) { if (currentArr[j] != t.get(j)) return -1; } } return totalOps; } } ``` #### JavaScript ```javascript class Solution { static mergeAndCount(arr, l, r) { if (l >= r) return 0; const m = Math.floor((l + r) / 2); let count = this.mergeAndCount(arr, l, m); count += this.mergeAndCount(arr, m + 1, r); const temp = []; let i = l, j = m + 1; while (i <= m && j <= r) { if (arr[i] <= arr[j]) { temp.push(arr[i++]); } else { temp.push(arr[j++]); count += (m - i + 1); } } while (i <= m) temp.push(arr[i++]); while (j <= r) temp.push(arr[j++]); for (let k = 0; k < temp.length; k++) { arr[l + k] = temp[k]; } return count; } static minSwaps(n, serial, k) { if (k === 0) { for (let i = 0; i < n - 1; i++) { if (serial[i] > serial[i + 1]) return -1; } return 0; } const sortedSerial = [...serial].sort((a, b) => a - b); const groups = Array.from({ length: k }, () => []); const targets = Array.from({ length: k }, () => []); for (let i = 0; i < n; i++) { groups[i % k].push(serial[i]); targets[i % k].push(sortedSerial[i]); } let totalOps = 0; for (let i = 0; i < k; i++) { const currentGroup = groups[i]; totalOps += this.mergeAndCount(currentGroup, 0, currentGroup.length - 1); for (let j = 0; j < currentGroup.length; j++) { if (currentGroup[j] !== targets[i][j]) return -1; } } return totalOps; } } ``` ### Complexity Analysis - **Time Complexity:** `O(n log n)` - **Space Complexity:** `O(n)`