Valid Crate Stacking — Problem Statement & Solution Guide

StackMediumMixed

TimeO(n + m)

SpaceO(n + m)

Quick Answer & Algorithm Key Takeaway

Iterate with two pointers, always selecting the smallest front element that is ≥ the previously placed weight. This greedy rule yields a single linear pass and constructs a valid stack if one exists.

TopicStack

PatternMixed

TimeO(n + m)

SpaceO(n + m)

Problem Description

You are given two integer arrays crateWeights1 and crateWeights2. Starting with an empty stack, you may repeatedly choose the first (front) element of either array, remove it, and place it on top of the current stack. The stack must always be non‑decreasing when read from bottom to top; that is, each newly placed crate must have a weight greater than or equal to the weight of the crate that was previously on top. Determine whether there exists a sequence of choices that consumes all crates from both arrays while never violating the non‑decreasing condition. Return true if such a sequence exists, otherwise return false.

DSA Pattern Breakdown

"Valid Crate Stacking"

medium

WHY DOES IT MATTER?

The two‑pointer merge pattern is a fundamental technique for combining ordered data streams with minimal overhead; mastering it lets you solve a wide class of problems that require preserving order across multiple sources.

OPTIMIZATION CHALLENGE

The insight that the smallest feasible crate can always be taken without harming future feasibility collapses an exponential decision tree into a deterministic linear scan.

REAL-WORLD CONNECTION

Think of a distributed logging system that receives ordered logs from two micro‑services; to present a single chronological view you merge the streams in real time, exactly like stacking crates while keeping weights non‑decreasing.

During an interview, state the invariant (last placed weight) first, then argue why picking the smallest feasible crate is safe; this shows you understand both the greedy proof and the implementation.

COMPLEXITY AT A GLANCE

⏱ Time:O(n + m)

💾 Space:O(n + m)

Core Theory — Why This Approach?

The "Valid Crate Stacking" problem can be modeled as a merge of two sequences while preserving a monotonic (non‑decreasing) order. Each step we may take the front element of either crateWeights1 or crateWeights2 and push it onto a stack; the stack’s bottom‑to‑top view must never decrease. This is equivalent to constructing a merged sequence that respects the original relative order inside each array and is globally non‑decreasing. The naive view treats the decision at each step as a binary choice, leading to a recursion tree of size O(2^{n+m}) – far too large for typical constraints.

To avoid exponential blow‑up we observe that the only state needed to continue is the last weight placed on the stack and the current indices in the two arrays. Because the stack must be non‑decreasing, at any point we can only pick a crate whose weight is ≥ the last placed weight. This property enables a greedy two‑pointer strategy: always take the smallest feasible front element. When both front elements are feasible, the smaller one cannot hurt future choices, mirroring the classic merge step of the merge‑sort algorithm. The greedy choice is provably optimal because any solution that postpones a smaller feasible crate can be transformed into one that takes it immediately without violating the monotonic constraint.

Thus the optimal paradigm is a linear‑time two‑pointer scan, optionally backed by a simple stack to record the result. The algorithm runs in O(n+m) time and O(n+m) space for the output (or O(1) auxiliary space if we overwrite one of the input arrays).

Interview Questions on This Problem

Q1How would you determine whether a valid stacking order exists for two given crate weight arrays?

Use two pointers starting at the fronts of both arrays and a variable tracking the last placed weight. At each step, pick the smallest front element that is ≥ the last weight; if neither front element satisfies the condition, a valid order does not exist.

Q2What is the time complexity of checking validity versus constructing the actual stack, and why are they the same?

Both checking validity and constructing the stack require a single linear pass over the combined length of the arrays, giving O(n+m) time, because each element is examined exactly once and the decision at each step is constant‑time.

Q3In a fintech platform where transaction batches must be processed in non‑decreasing timestamp order from two streams, which algorithmic pattern from this problem would you apply?

Apply the two‑pointer merge pattern (also known as the "merge step" of merge sort) to interleave the two streams while preserving timestamp monotonicity, guaranteeing O(N) processing time.

Examples

Example 1

Input

{\"crateWeights1\":[1,3,5],\"crateWeights2\":[2,4,6]}

Output

true

Explanation: Pick 1 from the first array (stack: [1]). Next pick 2 from the second array (stack: [1,2]). Then 3 (first), 4 (second), 5 (first), 6 (second). The stack weights 1≤2≤3≤4≤5≤6, so the answer is true.

Example 2

Input

{\"crateWeights1\":[5,4,3],\"crateWeights2\":[1,2,3]}

Output

false

Explanation: The first crate must be 5 or 1. If we start with 1 (second array), the next crate can be 5 (first) which is larger, but then the remaining crates 4 and 3 from the first array are smaller than the top (5), breaking the rule. Any other start leads to a similar violation, therefore no valid ordering exists.

Example 3

Input

{\"crateWeights1\":[2,2,3],\"crateWeights2\":[1,2,2]}

Output

true

Explanation: Choose 1 (second) → stack [1]. Then 2 (first) → [1,2]. Next 2 (first) → [1,2,2]. Then 2 (second) → [1,2,2,2]. Finally 3 (first) → [1,2,2,2,3]. All steps maintain non‑decreasing order, so the answer is true.

Constraints

1 <= crateWeights1.length, crateWeights2.length <= 10^5
-10^9 <= crateWeights1[i], crateWeights2[i] <= 10^9
Both arrays are processed only from the front; you cannot reorder elements within an array.

Optimal Approach & Strategy

Brute Force Approach

Recursively try every possible choice of taking the front element from either array, backtracking when the non‑decreasing condition is violated. This explores an exponential number of states.

Code Solutions

Language:

JavaScript Solution

Time: O(n + m)

function isValidStack(crateWeights1, crateWeights2) {
    let i = 0, j = 0;
    let prev = 0;
    while (i < crateWeights1.length || j < crateWeights2.length) {
        let curr;
        if (i < crateWeights1.length && (j == crateWeights2.length || crateWeights1[i] <= crateWeights2[j])) {
            curr = crateWeights1[i++];
        } else {
            curr = crateWeights2[j++];
        }
        if (curr < prev) {
            return false;
        }
        prev = curr;
    }
    return true;
}

const crateWeights1 = [1, 3, 5];
const crateWeights2 = [2, 4, 6];
console.log(isValidStack(crateWeights1, crateWeights2));


#include <iostream>
#include <vector>

bool isValidStack(std::vector<int>& crateWeights1, std::vector<int>& crateWeights2) {
    int i = 0, j = 0;
    int prev = 0;
    while (i < crateWeights1.size() || j < crateWeights2.size()) {
        int curr;
        if (i < crateWeights1.size() && (j == crateWeights2.size() || crateWeights1[i] <= crateWeights2[j])) {
            curr = crateWeights1[i++];
        } else {
            curr = crateWeights2[j++];
        }
        if (curr < prev) {
            return false;
        }
        prev = curr;
    }
    return true;
}

int main() {
    std::vector<int> crateWeights1 = {1, 3, 5};
    std::vector<int> crateWeights2 = {2, 4, 6};
    std::cout << std::boolalpha << isValidStack(crateWeights1, crateWeights2) << std::endl;
    return 0;
}


public class Main {
    public static boolean isValidStack(int[] crateWeights1, int[] crateWeights2) {
        int i = 0, j = 0;
        int prev = 0;
        while (i < crateWeights1.length || j < crateWeights2.length) {
            int curr;
            if (i < crateWeights1.length && (j == crateWeights2.length || crateWeights1[i] <= crateWeights2[j])) {
                curr = crateWeights1[i++];
            } else {
                curr = crateWeights2[j++];
            }
            if (curr < prev) {
                return false;
            }
            prev = curr;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] crateWeights1 = {1, 3, 5};
        int[] crateWeights2 = {2, 4, 6};
        System.out.println(isValidStack(crateWeights1, crateWeights2));
    }
}


def is_valid_stack(crate_weights1, crate_weights2):
    i, j = 0, 0
    prev = 0
    while i < len(crate_weights1) or j < len(crate_weights2):
        curr = 0
        if i < len(crate_weights1) and (j == len(crate_weights2) or crate_weights1[i] <= crate_weights2[j]):
            curr = crate_weights1[i]
            i += 1
        else:
            curr = crate_weights2[j]
            j += 1
        if curr < prev:
            return False
        prev = curr
    return True

crate_weights1 = [1, 3, 5]
crate_weights2 = [2, 4, 6]
print(is_valid_stack(crate_weights1, crate_weights2))


function isValidStack(crateWeights1, crateWeights2) {
    let i = 0, j = 0;
    let prev = 0;
    while (i < crateWeights1.length || j < crateWeights2.length) {
        let curr;
        if (i < crateWeights1.length && (j == crateWeights2.length || crateWeights1[i] <= crateWeights2[j])) {
            curr = crateWeights1[i++];
        } else {
            curr = crateWeights2[j++];
        }
        if (curr < prev) {
            return false;
        }
        prev = curr;
    }
    return true;
}

const crateWeights1 = [1, 3, 5];
const crateWeights2 = [2, 4, 6];
console.log(isValidStack(crateWeights1, crateWeights2));

Asked in Top Tech Interviews

Adobe

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.