Validate Crate Sequences — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Stack and solve the Validate Crate Sequences problem optimally.
O(n)O(n)Problem Description
You are given an integer n and a list of n operations describing how crates are handled in a storage stack. Each operation is either "add X" meaning a crate of type X is placed on top of the stack, or "remove X" meaning the crate on the top of the stack must be of type X and is taken away. A sequence is considered valid if all three conditions hold: 1) No "remove" is executed when the stack is empty. 2) When adding a crate, its type must differ from the current top crate (if any). 3) Every "remove X" must match the type of the crate that is currently on top. Output "YES" if the whole sequence satisfies these rules, otherwise output "NO".
DSA Pattern Breakdown
DSA Pattern Breakdown
"Validate Crate Sequences"
WHY DOES IT MATTER?
Stack validation appears in compilers (parentheses matching), transaction logs, and undo mechanisms; mastering it demonstrates understanding of LIFO semantics and constant‑time state updates.
OPTIMIZATION CHALLENGE
The key insight is that you never need to look deeper than the top element; by maintaining only the current stack you avoid re‑scanning the entire history, collapsing the problem to O(n) time and O(n) space.
REAL-WORLD CONNECTION
Think of a warehouse pallet jack: crates are stacked, and only the topmost crate can be lifted. Any mistake in the removal order can cause a collapse, mirroring how an invalid operation invalidates the whole sequence.
During an interview, write the push/pop logic first, then immediately add the two guard checks (empty stack and type mismatch). This early validation often catches edge cases before you even finish the loop.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic validation of a sequence of stack operations. Each "add X" pushes an element onto the stack, while each "remove X" must pop and verify that the top element matches X. A naive simulation that records every operation in an array works for tiny inputs but becomes costly when n reaches 10^5 or more because each operation still requires O(1) time, yet the overall memory usage can blow up if we store unnecessary auxiliary data or repeatedly scan the stack. The optimal paradigm leverages the LIFO property of a stack: we push on "add" and pop on "remove", checking the popped value against the expected type. This yields a linear‑time solution with only the current stack contents stored, which is the minimal state needed to enforce the three validity conditions.
Why naive approaches fail: If one tries to validate by scanning the entire history for each "remove" or by using a list and performing costly index operations, the time can degrade to O(n^2). Moreover, forgetting to enforce the empty‑stack check leads to runtime errors on large test cases. The optimal solution uses a true stack (e.g., vector/deque) with O(1) push and pop, guaranteeing O(n) total time and O(n) worst‑case space (the size of the deepest stack).
The optimal algorithm therefore follows the standard stack‑validation pattern: iterate once over the operations, maintain a stack, and immediately reject the sequence if a removal is attempted on an empty stack or if the popped element differs from the required type. If the loop finishes and the stack is empty, the sequence is valid.
Interview Questions on This Problem
Q1How would you modify the algorithm if the "remove" operation could specify any crate type that must appear somewhere in the stack, not necessarily on top?
You would need a data structure that supports fast removal of arbitrary elements while preserving order, such as a doubly‑linked list combined with a hash map from crate type to its node. Each "remove X" would locate the node via the map, verify that all crates above it have already been removed (or maintain a counter of pending removals), and then delete the node, updating the map. This changes the complexity to O(log n) or O(1) amortized depending on the auxiliary structures.
Q2Why is a stack the appropriate data structure for this problem, and could a queue ever be used instead?
A stack enforces Last‑In‑First‑Out order, which matches the physical constraint that only the top crate can be accessed. A queue follows First‑In‑First‑Out, so it cannot model the "remove" operation that must target the most recently added crate, making it unsuitable for this validation.
Q3In a distributed system where multiple producers add crates and multiple consumers remove crates, what consistency guarantees must you enforce to keep the sequence valid?
You must enforce linearizability of stack operations: each "add" and "remove" must appear atomically in a total order that respects real‑time ordering. This typically requires a single‑writer lock or a consensus protocol (e.g., Raft) to serialize access, ensuring that no consumer can remove a crate that hasn't been added or that the top‑of‑stack invariant is never violated.
Examples
Input
6 add 1 add 2 remove 2 add 3 remove 3 remove 1
Output
YES
Explanation: Start with an empty stack. - add 1 → stack [1] - add 2 (different from top 1) → stack [1,2] - remove 2 matches top → stack [1] - add 3 (different from top 1) → stack [1,3] - remove 3 matches top → stack [1] - remove 1 matches top → stack [] All operations obey the rules, so the answer is YES.
Input
5 add 5 add 5 remove 5 remove 5 remove 5
Output
NO
Explanation: After the first "add 5" the stack is [5]. The second operation tries to "add 5" while 5 is already on top, violating rule 2. The sequence is therefore invalid, and the answer is NO.
Input
4 add 10 remove 5 add 5 remove 10
Output
NO
Explanation: Step 1: add 10 → stack [10]. Step 2: remove 5 expects top 5 but top is 10, breaking rule 3. Since a rule is broken, the whole sequence is invalid, yielding NO.
Constraints
- 1 <= n <= 200000
- -10^9 <= X <= 10^9
- All operation strings are either "add X" or "remove X"
Optimal Approach & Strategy
Use a true stack: push on "add" and pop with a type check on "remove", achieving O(1) work per operation and O(n) total time.
Brute Force Approach
Simulate each operation using an array and, for every "remove", scan the entire array to find the matching crate, leading to O(n^2) time in the worst case.
Code Solutions
function isValidSequence(n, ops){
const stack = [];
for(const [cmd, val] of ops){
if(cmd === 'add'){
stack.push(val);
}else{ // remove
if(stack.length===0 || stack[stack.length-1]!==val) return false;
stack.pop();
}
}
return stack.length===0;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
if(data.length===0) process.exit(0);
const n = parseInt(data[idx++]);
let ops=[];
for(let i=0;i<n;i++){
const cmd = data[idx++];
const x = parseInt(data[idx++]);
ops.push([cmd,x]);
}
console.log(isValidSequence(n,ops) ? "YES" : "NO");#include <bits/stdc++.h>
using namespace std;
bool isValidSequence(int n, const vector<pair<string,int>>& ops){
vector<int> st;
st.reserve(n);
for(const auto &op: ops){
if(op.first=="add"){
st.push_back(op.second);
}else{ // remove
if(st.empty() || st.back()!=op.second) return false;
st.pop_back();
}
}
return st.empty();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<pair<string,int>> ops; ops.reserve(n);
for(int i=0;i<n;++i){
string cmd; int x; cin>>cmd>>x; ops.emplace_back(cmd,x);
}
cout << (isValidSequence(n,ops)?"YES":"NO") << "\n";
return 0;
}import java.io.*;
import java.util.*;
public class Main {
static boolean isValidSequence(int n, List<String[]> ops){
Deque<Integer> stack = new ArrayDeque<>();
for(String[] op : ops){
String cmd = op[0];
int val = Integer.parseInt(op[1]);
if("add".equals(cmd)){
stack.push(val);
}else{ // remove
if(stack.isEmpty() || stack.peek()!=val) return false;
stack.pop();
}
}
return stack.isEmpty();
}
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;
int n = Integer.parseInt(line.trim());
List<String[]> ops = new ArrayList<>();
for(int i=0;i<n;i++){
String[] parts = br.readLine().trim().split("\\s+");
ops.add(parts);
}
System.out.println(isValidSequence(n, ops) ? "YES" : "NO");
}
}import sys
def is_valid_sequence(n, ops):
stack = []
for cmd, val in ops:
if cmd == 'add':
stack.append(val)
else: # remove
if not stack or stack[-1] != val:
return False
stack.pop()
return not stack
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
n = int(next(it))
ops = [(next(it), int(next(it))) for _ in range(n)]
print('YES' if is_valid_sequence(n, ops) else 'NO')
if __name__ == '__main__':
main()function isValidSequence(n, ops){
const stack = [];
for(const [cmd, val] of ops){
if(cmd === 'add'){
stack.push(val);
}else{ // remove
if(stack.length===0 || stack[stack.length-1]!==val) return false;
stack.pop();
}
}
return stack.length===0;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
if(data.length===0) process.exit(0);
const n = parseInt(data[idx++]);
let ops=[];
for(let i=0;i<n;i++){
const cmd = data[idx++];
const x = parseInt(data[idx++]);
ops.push([cmd,x]);
}
console.log(isValidSequence(n,ops) ? "YES" : "NO");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.