Valid Crate Stacking — Problem Statement & Solution Guide
Problem Description
Given two arrays of integers crateWeights1 and crateWeights2, determine if it is possible to stack crates from both arrays into a single stack following the last-in-first-out principle, such that the total weight of crates in the stack never decreases.
Examples
Input
[3, 5, 4, 2, 1, 5, 4, 2, 1], [1, 2, 3, 4, 5]
Output
true
Explanation: Step-by-step: We can stack crates from both arrays in the order [3, 5, 4, 2, 1, 5, 4, 2, 1] following the last-in-first-out principle. First, we take the first crate from the first array (3), then the first crate from the second array (1), then the second crate from the first array (5), and so on. The total weight of crates in the stack never decreases.
Input
[1, 2, 3, 4, 5, 3, 5, 4, 2, 1], [1, 2, 3, 4, 5]
Output
true
Explanation: Step-by-step: We can stack crates from both arrays in the order [1, 2, 3, 4, 5, 3, 5, 4, 2, 1] following the last-in-first-out principle. First, we take the first crate from the first array (1), then the first crate from the second array (1), then the second crate from the first array (2), and so on. The total weight of crates in the stack never decreases.
Constraints
- 1 <= array lengths <= 100
- 1 <= crate weights <= 1000
Optimal Approach & Strategy
An optimal approach involves using two pointers, one for each array, to track the current element being considered for loading. By comparing the weights of the current elements and determining whether loading one would increase or maintain the total weight, we can efficiently decide the order of loading.
Brute Force Approach
One naive approach would involve generating all possible sequences of loading and unloading crates and checking each one to see if it meets the condition. This would have a high time complexity due to the large number of sequences. Another approach could involve using nested loops to compare each element from one array with every element from the other array.
Verified Code Solutions
function validCrateStacking(crateWeights1, crateWeights2) {
if (crateWeights1.length === 0 && crateWeights2.length === 0) return true;
if (crateWeights1.length === 0 || crateWeights2.length === 0) return false;
let sum1 = 0, sum2 = 0;
let i = crateWeights1.length - 1, j = crateWeights2.length - 1;
while (i >= 0 && j >= 0) {
if (crateWeights1[i] > crateWeights2[j]) {
sum1 += crateWeights1[i--];
} else {
sum2 += crateWeights2[j--];
}
}
return sum1 >= sum2;
}class Solution {
public boolean validCrateStacking(int[] crateWeights1, int[] crateWeights2) {
int i = 0, j = 0, totalWeight = 0;
while (i < crateWeights1.length && j < crateWeights2.length) {
if (crateWeights1[i] > crateWeights2[j]) {
return false;
}
totalWeight += crateWeights1[i];
i++;
j++;
}
return true;
}
}def valid_crate_stacking(crateWeights1, crateWeights2):
i, j = 0, 0
total_weight = 0
while i < len(crateWeights1) and j < len(crateWeights2):
if crateWeights1[i] > crateWeights2[j]:
return False
total_weight += crateWeights1[i]
i += 1
j += 1
return Truefunction validCrateStacking(crateWeights1, crateWeights2) {
if (crateWeights1.length === 0 && crateWeights2.length === 0) return true;
if (crateWeights1.length === 0 || crateWeights2.length === 0) return false;
let sum1 = 0, sum2 = 0;
let i = crateWeights1.length - 1, j = crateWeights2.length - 1;
while (i >= 0 && j >= 0) {
if (crateWeights1[i] > crateWeights2[j]) {
sum1 += crateWeights1[i--];
} else {
sum2 += crateWeights2[j--];
}
}
return sum1 >= sum2;
}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.