Validate Crate Sequences ā Problem Statement & Solution Guide
Problem Description
You are given a sequence of crate operations, where each operation is either 'add' or 'remove' with a corresponding crate type. Determine if the sequence is valid. A sequence is valid if every crate addition can be matched with a corresponding crate removal, and at no point is a crate removed from an empty stack or a crate added on top of another crate of the same type.
Examples
Input
['add crate1', 'add crate2', 'remove crate1', 'remove crate2', 'add crate1', 'remove crate1']
Output
false
Explanation: Step-by-step: 1. We start with an empty stack. 2. We add crate1 and crate2 to the stack. 3. We remove crate1 and crate2 from the stack. 4. We try to add crate1 on top of crate2 of the same type, which is invalid. 5. We try to remove crate1 from an empty stack, which is also invalid.
Input
['remove crate1', 'add crate1', 'remove crate1', 'add crate1', 'remove crate1']
Output
false
Explanation: Step-by-step: 1. We start with an empty stack. 2. We try to remove crate1 from an empty stack, which is invalid. 3. We add crate1 to the stack. 4. We remove crate1 from the stack. 5. We add crate1 to the stack again. 6. We remove crate1 from the stack again.
Constraints
- 1 <= sequence length <= 100
- Each operation in the sequence is either 'add_X' or 'remove_X', where X is a crate type (A, B, C, etc.)
Optimal Approach & Strategy
The optimal approach involves utilizing a stack to track the added crates and checking for corresponding removals, ensuring that no two crates of the same type are added consecutively. This can be achieved with a single pass through the sequence, resulting in a linear time complexity.
Brute Force Approach
The brute-force approach would involve iterating through the sequence for each operation to validate it against all previous operations, resulting in a time complexity of O(nĀ²). This naive approach would be highly inefficient for large sequences. It can be implemented using nested loops to compare each operation with all previous ones.
Verified Code Solutions
function validateCrateSequence(sequence) {
let stack = [];
for (let i = 0; i < sequence.length; i++) {
if (sequence[i][0] === 'add') {
if (stack.length > 0 && stack[stack.length - 1] === sequence[i][1]) {
return false;
}
stack.push(sequence[i][1]);
} else if (sequence[i][0] === 'remove') {
if (stack.length === 0) {
return false;
}
if (stack[stack.length - 1] === sequence[i][1]) {
stack.pop();
} else {
return false;
}
}
}
return stack.length === 0;
}public boolean validateCrateSequence(String[] sequence) {
Stack<String> stack = new Stack<>();
for (String operation : sequence) {
if (operation.startsWith("add")) {
String crate = operation.split(" ")[1];
if (!stack.isEmpty() && stack.peek().equals(crate)) {
return false;
}
stack.push(crate);
} else if (operation.startsWith("remove")) {
String crate = operation.split(" ")[1];
if (stack.isEmpty() || stack.pop() != crate) {
return false;
}
}
}
return stack.isEmpty();
}def validate_crate_sequence(sequence):
stack = []
for operation in sequence:
if operation.startswith('add'):
crate = operation.split(' ')[1]
if stack and stack[-1] == crate:
return False
stack.append(crate)
elif operation.startswith('remove'):
crate = operation.split(' ')[1]
if not stack or stack.pop() != crate:
return False
return not stackfunction validateCrateSequence(sequence) {
let stack = [];
for (let i = 0; i < sequence.length; i++) {
if (sequence[i][0] === 'add') {
if (stack.length > 0 && stack[stack.length - 1] === sequence[i][1]) {
return false;
}
stack.push(sequence[i][1]);
} else if (sequence[i][0] === 'remove') {
if (stack.length === 0) {
return false;
}
if (stack[stack.length - 1] === sequence[i][1]) {
stack.pop();
} else {
return false;
}
}
}
return stack.length === 0;
}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.