Weight Category Partition — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Weight Category Partition problem optimally.
O(n)O(1) auxiliary (output array O(n) is required)Problem Description
Given an integer array nums, reorder its elements so that every value strictly less than 850 appears before any value greater than or equal to 850. The relative order of the numbers within each partition must be identical to their order in the original array. Return the reordered array. The algorithm should run in linear time and use only constant extra space beyond the output array (or modify the input in‑place).
DSA Pattern Breakdown
DSA Pattern Breakdown
"Weight Category Partition"
WHY DOES IT MATTER?
Stable partitioning appears in many real‑world pipelines where ordering conveys meaning—e.g., logs before errors, low‑risk trades before high‑risk ones. Maintaining order avoids extra sorting steps downstream and guarantees deterministic behavior across runs.
OPTIMIZATION CHALLENGE
The insight is that we don’t need to shuffle elements around the pivot; we can simply collect them into two streams in a single pass, which eliminates the quadratic cost of repeated swaps and yields O(n) time with only constant auxiliary variables.
REAL-WORLD CONNECTION
Think of a mail‑sorting center: letters destined for local delivery (low weight) are placed on one conveyor belt while long‑distance parcels (high weight) go to another, but within each belt the original arrival sequence is kept, ensuring fair processing.
When coding, allocate a result array of the same size, keep a write pointer for the ‘less‑than’ region, and a second pointer that starts after the first pass; this two‑pointer technique is easy to reason about and avoids off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(n)O(1) auxiliary (output array O(n) is required)Core Theory — Why This Approach?
The problem is a classic example of a stable partition: we must reorder an array around a pivot (850) while preserving the relative order of elements on each side. A naive in‑place swap‑based partition (like the one used in quicksort) breaks stability because it moves elements across the pivot without regard to their original sequence. For large inputs, such instability leads to incorrect answers and, if one tries to fix it by repeatedly swapping adjacent elements, the runtime degrades to O(n²). The optimal paradigm leverages the fact that we are allowed to produce a new array (the output) and that we only need constant auxiliary storage beyond that. By scanning the original array once, we can copy all elements <850 into the result, then a second pass (or a continuation of the same pass) copies the remaining elements, guaranteeing both linear time and stability. This approach embodies the “two‑bucket stable partition” pattern, which is a special case of counting‑sort‑like bucketization where the bucket count is constant (two buckets).
Interview Questions on This Problem
Q1How would you modify the stable partition algorithm if the pivot value is not known in advance but must be the median of the array?
First find the median in O(n) time using the QuickSelect algorithm, then perform the same two‑bucket stable partition using that median as the pivot; the overall complexity remains O(n) time and O(1) extra space beyond the output array.
Q2At a fintech firm you need to stream transaction amounts and keep a real‑time view of amounts below and above a regulatory threshold without reordering the stream. Which data structure helps you achieve O(1) amortized insertion while preserving order?
A pair of linked‑list queues (or dequeues) works: one queue stores values < threshold, the other stores ≥ threshold; each incoming value is enqueued to the appropriate list, preserving arrival order and enabling constant‑time insertion.
Q3A high‑growth startup wants to run this partition on a massive distributed dataset stored across shards. How can you parallelize the stable partition while still producing a globally ordered result?
Run the stable partition locally on each shard to produce two ordered sub‑lists, then perform a distributed merge where all <‑threshold sub‑lists are concatenated in shard order followed by all ≥‑threshold sub‑lists, preserving global stability with only O(number of shards) coordination overhead.
Examples
Input
[900,800,850,700,860]
Output
[800,700,900,850,860]
Explanation: Elements <850 are 800 and 700; they keep their original order. Elements ≥850 are 900,850,860; they also keep their original order. Concatenating the two groups yields [800,700,900,850,860].
Input
[500,850,849,851]
Output
[500,849,850,851]
Explanation: Values <850: 500,849 (order preserved). Values ≥850: 850,851 (order preserved). Combined result is [500,849,850,851].
Input
[1000,200,300,850,400]
Output
[200,300,400,1000,850]
Explanation: Values <850: 200,300,400. Values ≥850: 1000,850. Maintaining original ordering inside each group gives the final array [200,300,400,1000,850].
Constraints
- 1 <= nums.length <= 200000
- -10^9 <= nums[i] <= 10^9
- Time complexity must be O(n)
- Auxiliary space must be O(1) besides the output array
Optimal Approach & Strategy
Perform a single linear pass, copying elements <850 into the front of a new array, then copy the remaining elements, achieving O(n) time and O(1) auxiliary space.
Brute Force Approach
Iterate over the array, and for each element less than 850, shift it leftwards by swapping with preceding elements until it reaches the correct region—this leads to O(n²) time.
Code Solutions
function partitionWeight(nums) {
const less = [];
const greaterOrEqual = [];
for (const v of nums) {
if (v < 850) less.push(v);
else greaterOrEqual.push(v);
}
return less.concat(greaterOrEqual);
}
const readline = require('readline');
const rl = readline.createInterface({input: process.stdin, output: process.stdout});
rl.on('line', (line) => {
const nums = line.split(/[,\s]+/).filter(s=>s.length).map(Number);
const res = partitionWeight(nums);
console.log(res.join(','));
rl.close();
});#include <bits/stdc++.h>
using namespace std;
// Stable partition using an auxiliary vector (O(n) time, O(n) extra for output only)
vector<int> partitionWeight(const vector<int>& nums) {
vector<int> less; less.reserve(nums.size());
vector<int> greaterOrEqual; greaterOrEqual.reserve(nums.size());
for(int v: nums){
if(v < 850) less.push_back(v);
else greaterOrEqual.push_back(v);
}
less.insert(less.end(), greaterOrEqual.begin(), greaterOrEqual.end());
return less;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line; if(!getline(cin,line)) return 0;
stringstream ss(line);
vector<int> nums; int x; char delim;
while(ss>>x){ nums.push_back(x); ss>>delim; }
vector<int> res = partitionWeight(nums);
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 int[] partitionWeight(int[] nums) {
List<Integer> less = new ArrayList<>();
List<Integer> greaterOrEqual = new ArrayList<>();
for (int v : nums) {
if (v < 850) less.add(v);
else greaterOrEqual.add(v);
}
int[] result = new int[nums.length];
int idx = 0;
for (int v : less) result[idx++] = v;
for (int v : greaterOrEqual) result[idx++] = v;
return result;
}
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;
String[] parts = line.split("[ ,]+");
int[] nums = new int[parts.length];
for (int i = 0; i < parts.length; i++) nums[i] = Integer.parseInt(parts[i]);
int[] res = partitionWeight(nums);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.length; i++) {
if (i > 0) sb.append(',');
sb.append(res[i]);
}
System.out.println(sb.toString());
}
}
def partition_weight(nums):
less = [v for v in nums if v < 850]
greater_or_equal = [v for v in nums if v >= 850]
return less + greater_or_equal
if __name__ == "__main__":
import sys
line = sys.stdin.readline().strip()
if line:
nums = [int(x) for x in line.replace(',', ' ').split()]
result = partition_weight(nums)
print(','.join(map(str, result)))
function partitionWeight(nums) {
const less = [];
const greaterOrEqual = [];
for (const v of nums) {
if (v < 850) less.push(v);
else greaterOrEqual.push(v);
}
return less.concat(greaterOrEqual);
}
const readline = require('readline');
const rl = readline.createInterface({input: process.stdin, output: process.stdout});
rl.on('line', (line) => {
const nums = line.split(/[,\s]+/).filter(s=>s.length).map(Number);
const res = partitionWeight(nums);
console.log(res.join(','));
rl.close();
});
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.