Weight Category Partition ā Problem Statement & Solution Guide
Problem Description
Partition the list of weights into two categories: weights less than 850 and weights greater than or equal to 850, while maintaining the relative order within each category.
Examples
Input
[300, 500, 900, 1200, 1000]
Output
[300, 500, 900]
Explanation: Step-by-step: Given the input [300, 500, 900, 1200, 1000], we first initialize two empty lists, one for weights less than 850 and one for weights greater than or equal to 850. Then, we iterate over the input list. If a weight is less than 850, we append it to the first list. If a weight is greater than or equal to 850, we append it to the second list. Finally, we return the two lists. The output is [300, 500, 900].
Input
[100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200]
Output
[100, 200, 300, 400, 500, 600, 700, 800]
Explanation: Step-by-step: Given the input [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200], we first initialize two empty lists, one for weights less than 850 and one for weights greater than or equal to 850. Then, we iterate over the input list. If a weight is less than 850, we append it to the first list. If a weight is greater than or equal to 850, we append it to the second list. Finally, we return the two lists. The output is [100, 200, 300, 400, 500, 600, 700, 800].
Constraints
- 1 <= cargoWeights.length <= 10^5
- 1 <= cargoWeights[i] <= 10^6
- 1 <= targetWeight <= 10^6
Optimal Approach & Strategy
The optimal approach involves utilizing the Two Pointers technique to iterate through the cargoWeights array and partition it into two subarrays based on the target weight, preserving the original order. This can be achieved with a single pass through the array.
Brute Force Approach
A naive approach would involve using nested loops to compare each container's weight with the target weight, resulting in a time complexity of O(nĀ²). This method is inefficient for large inputs. The brute-force approach would not maintain the original order.
Verified Code Solutions
function weightCategoryPartition(weights) { let lessThan850 = [], greaterThan850 = []; for (let weight of weights) { if (weight < 850) lessThan850.push(weight); else greaterThan850.push(weight); } return lessThan850.concat(greaterThan850); }class Solution {
public Object[] weightCategoryPartition(int[] weights) {
int[] lessThan850 = new int[weights.length];
int[] greaterThanOrEqual850 = new int[weights.length];
int lessThan850Index = 0;
int greaterThanOrEqual850Index = 0;
for (int weight : weights) {
if (weight < 850) {
lessThan850[lessThan850Index++] = weight;
} else {
greaterThanOrEqual850[greaterThanOrEqual850Index++] = weight;
}
}
return new Object[] {lessThan850, greaterThanOrEqual850};
}
}def weight_category_partition(weights):
less_than_850 = [weight for weight in weights if weight < 850]
greater_than_or_equal_to_850 = [weight for weight in weights if weight >= 850]
return less_than_850, greater_than_or_equal_to_850function weightCategoryPartition(weights) { let lessThan850 = [], greaterThan850 = []; for (let weight of weights) { if (weight < 850) lessThan850.push(weight); else greaterThan850.push(weight); } return lessThan850.concat(greaterThan850); }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.