Galactic Cargo Sorting — Problem Statement & Solution Guide
Problem Description
Given an array of integers representing the weights (in kilograms) of cargo containers loaded into a spaceship, rearrange the array so that every container weighing less than 850 kg appears before any container weighing 850 kg or more. The relative order of containers inside each weight group must stay exactly as in the original sequence. Return the resulting array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Cargo Sorting"
WHY DOES IT MATTER?
The stable partition pattern is essential because it ensures that the relative order of elements within each partition is preserved, which is critical in many real-world applications such as sorting algorithms, database indexing, and data processing pipelines. Understanding this pattern helps in designing efficient algorithms that maintain data integrity and order.
OPTIMIZATION CHALLENGE
The key insight that reduces time/space complexity is the use of two auxiliary arrays to separate the elements into two groups in a single pass. This avoids the O(n^2) complexity of naive swapping methods and ensures O(n) time complexity with O(n) space.
REAL-WORLD CONNECTION
In distributed systems, stable partitioning is analogous to sharding data across multiple servers while maintaining the order of transactions within each shard. This ensures that when data is reassembled, the original order is preserved, which is crucial for consistency and correctness.
In an interview, clearly state that you are using a stable partition approach and explain why it is necessary. Mention the trade-offs between time and space complexity and be prepared to discuss in-place solutions if asked.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem of partitioning an array into two groups while preserving the relative order within each group is a classic application of the Stable Partition problem. Unlike the standard Dutch National Flag problem or Lomuto partition scheme, which do not guarantee stability (i.e., the relative order of elements within the same partition may change), this problem requires a stable partition. Naive approaches, such as repeatedly scanning the array to find the first element of the second group and swapping it with the first element of the first group, result in O(n^2) time complexity. This is inefficient for large datasets because each swap may require multiple comparisons and movements, leading to poor performance on large inputs.
The optimal paradigm for solving this problem in O(n) time and O(n) space involves using two auxiliary arrays or a single auxiliary array with two pointers. By iterating through the original array once, we can place elements less than the threshold (850 kg) into the first auxiliary array and elements greater than or equal to the threshold into the second. Finally, we concatenate these two arrays. This approach ensures that the relative order within each group is preserved because we process the elements in their original sequence. The time complexity is O(n) because we traverse the array once, and the space complexity is O(n) due to the auxiliary storage required.
For in-place solutions, which are more complex and typically require O(1) extra space, algorithms like the recursive stable partition or using a divide-and-conquer approach can be employed. However, these are often overkill for interview settings unless specifically requested. The two-pointer auxiliary array method is the most practical and efficient solution for this problem, balancing time and space complexity while maintaining stability.
Interview Questions on This Problem
Q1How would you modify your solution to handle a dynamic threshold that changes during the partitioning process?
If the threshold changes dynamically, you would need to re-evaluate the partitioning condition for each element. This could be achieved by using a priority queue or a balanced binary search tree to keep track of elements and their weights, allowing for efficient re-partitioning as the threshold changes. However, for a static threshold, the two-pointer auxiliary array method remains optimal.
Q2Can you solve this problem in O(1) extra space? If so, how?
Solving this in O(1) extra space requires an in-place stable partition algorithm. One approach is to use a recursive divide-and-conquer method where you partition the array into smaller subarrays and recursively apply the stable partition. Another approach is to use a loop that swaps elements to maintain the partition while preserving order, though this is more complex and less commonly used in interviews.
Q3How would you handle the case where the array is already partitioned correctly?
If the array is already partitioned correctly, the two-pointer auxiliary array method will still work, but it will unnecessarily create two auxiliary arrays. To optimize for this case, you could first check if the array is already partitioned by scanning it once. If it is, you can return the array as is, saving the overhead of creating auxiliary arrays.
Examples
Input
[920, 430, 870, 300, 850, 120]
Output
[430, 300, 120, 920, 870, 850]
Explanation: Original order: 920(≥850), 430(<850), 870(≥850), 300(<850), 850(≥850), 120(<850). First collect all <850 in original order → 430, 300, 120. Then collect all ≥850 in original order → 920, 870, 850. Concatenating gives the output.
Input
[800, 799, 801, 850, 849]
Output
[800, 799, 801, 849, 850]
Explanation: Elements <850 are 800, 799, 801, 849 (preserving order). Elements ≥850 are only 850. Combined result yields the output.
Input
[950, 940, 930]
Output
[950, 940, 930]
Explanation: All containers weigh ≥850, so the order remains unchanged.
Constraints
- 1 <= weights.length <= 200000
- 0 <= weights[i] <= 1000000
- All weights are integers
Optimal Approach & Strategy
The optimal approach uses two auxiliary arrays to separate the elements into two groups in a single pass. By iterating through the original array once, we place elements less than 850 kg into the first array and elements greater than or equal to 850 kg into the second, then concatenate them.
Brute Force Approach
The naive approach involves repeatedly scanning the array to find the first element of the second group and swapping it with the first element of the first group. This results in O(n^2) time complexity due to the repeated scans and swaps.
Verified Code Solutions
function sortCargo(weights) {
const less = [];
const greater = [];
for (const w of weights) {
if (w < 850) less.push(w);
else greater.push(w);
}
return less.concat(greater);
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
const n = data[0];
const arr = data.slice(1, 1 + n);
const res = sortCargo(arr);
console.log(res.join(' '));
}
main();#include <bits/stdc++.h>
using namespace std;
vector<int> sortCargo(const vector<int>& weights) {
vector<int> less, greater;
less.reserve(weights.size());
greater.reserve(weights.size());
for (int w : weights) {
if (w < 850) less.push_back(w);
else greater.push_back(w);
}
less.insert(less.end(), greater.begin(), greater.end());
return less;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;if(!(cin>>n))return 0;vector<int>a(n);for(int&i:a)cin>>i;auto res=sortCargo(a);for(size_t i=0;i<res.size();++i){if(i)cout<<' ';cout<<res[i];}cout<<'\n';return 0;}import java.io.*;
import java.util.*;
public class Main {
public static List<Integer> sortCargo(List<Integer> weights) {
List<Integer> less = new ArrayList<>();
List<Integer> greater = new ArrayList<>();
for (int w : weights) {
if (w < 850) less.add(w);
else greater.add(w);
}
less.addAll(greater);
return less;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
StringTokenizer st = new StringTokenizer(br.readLine());
List<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(Integer.parseInt(st.nextToken()));
}
List<Integer> res = sortCargo(arr);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(res.get(i));
}
System.out.println(sb.toString());
}
}def sort_cargo(weights):
less = [w for w in weights if w < 850]
greater = [w for w in weights if w >= 850]
return less + greater
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit()
n = int(data[0])
arr = list(map(int, data[1:1+n]))
res = sort_cargo(arr)
print(' '.join(map(str, res)))function sortCargo(weights) {
const less = [];
const greater = [];
for (const w of weights) {
if (w < 850) less.push(w);
else greater.push(w);
}
return less.concat(greater);
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
const n = data[0];
const arr = data.slice(1, 1 + n);
const res = sortCargo(arr);
console.log(res.join(' '));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.