Warehouse Inventory Management 2 — Problem Statement & Solution Guide
Problem Description
You are given two integer arrays A and B representing the order in which crates are stacked in two side‑yards. At each step you may take the next untouched crate from the front of either array and load it onto a truck. The truck also stores crates in a stack, therefore the weight of every newly loaded crate must be **greater than or equal to** the weight of the crate that was loaded immediately before it. In other words, the sequence of loaded weights must be non‑decreasing. Determine whether there exists a sequence of choices that loads **all** crates while respecting the original order inside each array and the non‑decreasing rule. Return "true" if it is possible, otherwise return "false".
DSA Pattern Breakdown
DSA Pattern Breakdown
"Warehouse Inventory Management 2"
WHY DOES IT MATTER?
Understanding this pattern teaches candidates how to convert a combinatorial interleaving problem into a deterministic merge, a skill that recurs in scheduling, stream processing, and version‑control merge algorithms.
OPTIMIZATION CHALLENGE
The key insight is the greedy monotonicity: by always picking the minimum feasible weight, you maintain the lowest possible stack threshold, which eliminates the need for backtracking or exponential exploration.
REAL-WORLD CONNECTION
Think of two conveyor belts feeding a single packaging line: each belt supplies items in a fixed order, and the line can only accept items that are not lighter than the previous one to avoid imbalance—choosing the lighter acceptable item first keeps the line stable, just like load‑balancing in distributed queues.
In the interview, write the two‑pointer loop first, then add the conditional checks for feasibility; keep the code short, comment the invariant (lastWeight is the current stack top), and walk through a tiny example to prove correctness.
COMPLEXITY AT A GLANCE
O(N+M)O(1)Core Theory — Why This Approach?
The problem is a classic two‑pointer interleaving challenge that can be modeled as constructing a non‑decreasing sequence by merging two ordered streams. A naive brute‑force would try every possible interleaving, which grows exponentially (2^(n+m)) and quickly becomes infeasible for large inputs. The optimal paradigm leverages the greedy choice property: at any step, if both front crates satisfy the non‑decreasing constraint, picking the lighter one never harms feasibility because it leaves the larger crate for later when the stack height is higher. This reduces the decision space to a deterministic linear scan, turning the problem into a simple O(N+M) merge‑like algorithm that maintains the last loaded weight and advances pointers accordingly.
Interview Questions on This Problem
Q1How would you determine if all crates can be loaded onto the truck while preserving the non‑decreasing weight constraint?
Use two indices i and j for arrays A and B, keep a variable lastWeight initialized to -∞. While i<A.length or j<B.length, look at the next candidates A[i] and B[j]. If both are >= lastWeight, load the smaller one and update lastWeight; if only one qualifies, load that one; if none qualify, return false. If the loop finishes, return true.
Q2Why does the greedy choice of always loading the lighter feasible crate guarantee an optimal solution?
Because the stack must be non‑decreasing, loading a heavier feasible crate early can only restrict future choices by raising the required minimum weight. Selecting the smallest possible crate keeps the threshold as low as possible, preserving all later options and never eliminates a feasible solution that exists.
Q3Can this problem be solved with a DP approach, and would it be advisable in an interview?
A DP could track feasibility for each (i,j) pair, yielding O(N·M) time and space, which is correct but unnecessary. Mentioning DP shows awareness of exhaustive methods, but you should quickly argue that the greedy linear solution is both simpler and optimal, making DP overkill for this medium‑difficulty problem.
Examples
Input
A = [1,3,5] B = [2,4,6]
Output
true
Explanation: Load 1 from A (stack: [1]), then 2 from B (stack: [1,2]), then 3 from A, 4 from B, 5 from A and finally 6 from B. The loaded weights are 1,2,3,4,5,6 which is non‑decreasing, so all crates can be loaded.
Input
A = [4,2,7] B = [1,5,8]
Output
false
Explanation: Array A contains a decreasing pair 4 > 2. Because the relative order inside A cannot be changed, any loading sequence will place 4 before 2, violating the non‑decreasing rule. Hence loading all crates is impossible.
Input
A = [1,2,2] B = [2,3]
Output
true
Explanation: One feasible loading order is 1(A),2(A),2(A),2(B),3(B). The resulting sequence 1,2,2,2,3 never decreases, so all crates can be loaded.
Constraints
- 1 <= A.length, B.length <= 10^5
- -10^9 <= A[i], B[i] <= 10^9
- A.length + B.length <= 2 * 10^5
Optimal Approach & Strategy
Use two pointers and a greedy rule to pick the smallest feasible front element, achieving linear time.
Brute Force Approach
Recursively try every possible choice at each step, leading to exponential time.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = data[idx++]||0;
const A = data.slice(idx, idx+n); idx+=n;
const m = data[idx++]||0;
const B = data.slice(idx, idx+m);
function canLoad(A,B){
let i=0,j=0; let last=-Infinity;
while(i<A.length || j<B.length){
const canA = i<A.length && A[i]>=last;
const canB = j<B.length && B[j]>=last;
if(!canA && !canB) return false;
if(canA && (!canB || A[i]<=B[j])){ last=A[i]; i++; }
else { last=B[j]; j++; }
}
return true;
}
console.log(canLoad(A,B)?'true':'false');#include <bits/stdc++.h>
using namespace std;
bool canLoad(const vector<int>& A, const vector<int>& B){
size_t i=0,j=0; long long last=LLONG_MIN;
while(i<A.size() || j<B.size()){
bool canA = i<A.size() && A[i]>=last;
bool canB = j<B.size() && B[j]>=last;
if(!canA && !canB) return false;
if(canA && (!canB || A[i]<=B[j])){ last=A[i]; ++i; }
else { last=B[j]; ++j; }
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int>A(n); for(int i=0;i<n;++i)cin>>A[i];
int m; cin>>m; vector<int>B(m); for(int i=0;i<m;++i)cin>>B[i];
cout<<(canLoad(A,B)?"true":"false");
return 0;
}import java.util.*;
public class Main {
static boolean canLoad(int[] A, int[] B) {
int i=0,j=0;
long last = Long.MIN_VALUE;
while(i<A.length || j<B.length){
boolean canA = i<A.length && A[i]>=last;
boolean canB = j<B.length && B[j]>=last;
if(!canA && !canB) return false;
if(canA && (!canB || A[i]<=B[j])){ last=A[i]; i++; }
else { last=B[j]; j++; }
}
return true;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.hasNextInt()?sc.nextInt():0;
int[] A = new int[n];
for(int i=0;i<n;i++) A[i]=sc.nextInt();
int m = sc.hasNextInt()?sc.nextInt():0;
int[] B = new int[m];
for(int i=0;i<m;i++) B[i]=sc.nextInt();
System.out.println(canLoad(A,B)?"true":"false");
sc.close();
}
}import sys
def can_load(A, B):
i=j=0
last=-10**18
while i<len(A) or j<len(B):
canA = i<len(A) and A[i]>=last
canB = j<len(B) and B[j]>=last
if not canA and not canB:
return False
if canA and (not canB or A[i]<=B[j]):
last=A[i]; i+=1
else:
last=B[j]; j+=1
return True
def main():
nums = list(map(int, sys.stdin.read().strip().split()))
if not nums:
return
idx=0
n=nums[idx]; idx+=1
A=nums[idx:idx+n]; idx+=n
m=nums[idx]; idx+=1
B=nums[idx:idx+m]
print('true' if can_load(A,B) else 'false')
if __name__=='__main__':
main()
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = data[idx++]||0;
const A = data.slice(idx, idx+n); idx+=n;
const m = data[idx++]||0;
const B = data.slice(idx, idx+m);
function canLoad(A,B){
let i=0,j=0; let last=-Infinity;
while(i<A.length || j<B.length){
const canA = i<A.length && A[i]>=last;
const canB = j<B.length && B[j]>=last;
if(!canA && !canB) return false;
if(canA && (!canB || A[i]<=B[j])){ last=A[i]; i++; }
else { last=B[j]; j++; }
}
return true;
}
console.log(canLoad(A,B)?'true':'false');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.