mediumStackPattern: Mixed
Validate Crate Sequences Solution
Problem Statement
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
Example 1:
Input:[["add",1],["add",2],["remove",1],["remove",2]]
Output:true
Example 2:
Input:[["add",1],["add",1],["remove",1],["remove",1]]
Output:false
Example 3:
Input:[["add",1],["remove",1],["add",2],["remove",2]]
Output:true
Example 4:
Input:[["add",1],["remove",2]]
Output:false
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.)
Time: O(n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.