Cargo Stack Operations ā Problem Statement & Solution Guide
Problem Description
Given a stack of integers representing cargo shipments and a list of operations, where each operation is either 'import' with a specific cargo quantity or 'export' to remove the top shipment from the stack, determine the final state of the cargo stack after applying these operations. If the export quantity is greater than the stack size or not present in the stack, ignore the operation.
Examples
Input
[1, 2, 3], ['import', 1], ['import', 2], ['import', 3], ['export', 3], ['export', 3]
Output
[1, 2]
Explanation: Step-by-step: 1. Import 1, 2, and 3 into the stack: [1, 2, 3]. 2. Export 3 from the stack: [1, 2]. 3. Export 3 from the stack again, but since there is no 3 in the stack, we ignore this operation.
Input
[1, 2, 3], ['export', 4]
Output
[1, 2, 3]
Explanation: Step-by-step: 1. The export operation with quantity 4 is not present in the stack, so we ignore this operation.
Constraints
- {"name":"operationTypes","type":"string","description":"Each operation 'type' can be either 'import' or 'export'."}
- {"name":"quantityRange","type":"integer","description":"The 'quantity' for 'import' operations is a positive integer."}
Optimal Approach & Strategy
An optimized approach utilizes a stack data structure to directly add or remove elements from the top, resulting in a time complexity of O(n) since each operation (import or export) is a constant time operation.
Brute Force Approach
A brute-force approach involves iterating through each operation and manually updating the stack by shifting elements for each import and export, resulting in a time complexity of O(nĀ²) due to the inefficient shifting.
Verified Code Solutions
class Solution {
public int[] cargoStackOperations(int[] cargo, String[][] operations) {
int[] stack = cargo.clone();
for (String[] op : operations) {
if (op[0].equals("import")) {
stack = addElement(stack, op[1]);
} else if (op[0].equals("export")) {
stack = removeElements(stack, op[1]);
}
}
return stack;
}
private int[] addElement(int[] stack, int element) {
int[] newStack = new int[stack.length + 1];
System.arraycopy(stack, 0, newStack, 0, stack.length);
newStack[stack.length] = element;
return newStack;
}
private int[] removeElements(int[] stack, int quantity) {
if (quantity <= stack.length) {
int[] newStack = new int[stack.length - quantity];
System.arraycopy(stack, quantity, newStack, 0, stack.length - quantity);
return newStack;
} else {
return stack;
}
}
}def cargo_stack_operations(cargo, operations):
stack = cargo.copy()
for op in operations:
if op[0] == 'import':
stack.append(op[1])
elif op[0] == 'export':
if op[1] <= len(stack):
for _ in range(op[1]):
stack.pop()
return stack
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.