Event counter with rollback (savepoint idea)
Hard
Java
Variables
23 views
Problem Statement
Task: apply updates (+x) but also handle rollback to previous savepoint index. Return final value.
Input Format
• First line: Integer q (number of operations)
• Next q lines:
• add x → add value x
• save → create a savepoint
• rollback k → rollback to savepoint index k (0-based)
• Next q lines:
• add x → add value x
• save → create a savepoint
• rollback k → rollback to savepoint index k (0-based)
Output Format
• Print one integer: the final value after all operations
Example
6 add 5 save add 3 save add 2 rollback 0
123
Constraints
• 1 ≤ q ≤ 10^5
• -10^9 ≤ x ≤ 10^9
• Rollback index is always valid
• -10^9 ≤ x ≤ 10^9
• Rollback index is always valid
Concept Explanation
Operations step-by-step:
1.add 5 → value = 5
2.save → savepoint 0 stores value 5
3.add 3 → value = 8
4.save → savepoint 1 stores value 8
5.add 2 → value = 10
6.rollback 0 → revert to savepoint 0 → value = 5
Final value = 5
1.add 5 → value = 5
2.save → savepoint 0 stores value 5
3.add 3 → value = 8
4.save → savepoint 1 stores value 8
5.add 2 → value = 10
6.rollback 0 → revert to savepoint 0 → value = 5
Final value = 5
Step-by-Step Explanation
1.Initialize currentValue = 0.
2.Create a List to store savepoints.
3.For each operation:
• If operation is add x:
• currentValue += x
• If operation is save:
• Store currentValue in savepoints list
• If operation is rollback k:
• Set currentValue = savepoints.get(k)
4.After processing all operations, print currentValue.
2.Create a List to store savepoints.
3.For each operation:
• If operation is add x:
• currentValue += x
• If operation is save:
• Store currentValue in savepoints list
• If operation is rollback k:
• Set currentValue = savepoints.get(k)
4.After processing all operations, print currentValue.
Concept Explanation
Operations step-by-step:
1.add 5 → value = 5
2.save → savepoint 0 stores value 5
3.add 3 → value = 8
4.save → savepoint 1 stores value 8
5.add 2 → value = 10
6.rollback 0 → revert to savepoint 0 → value = 5
Final value = 5
1.add 5 → value = 5
2.save → savepoint 0 stores value 5
3.add 3 → value = 8
4.save → savepoint 1 stores value 8
5.add 2 → value = 10
6.rollback 0 → revert to savepoint 0 → value = 5
Final value = 5
Step-by-Step Explanation
1.Initialize currentValue = 0.
2.Create a List to store savepoints.
3.For each operation:
• If operation is add x:
• currentValue += x
• If operation is save:
• Store currentValue in savepoints list
• If operation is rollback k:
• Set currentValue = savepoints.get(k)
4.After processing all operations, print currentValue.
2.Create a List to store savepoints.
3.For each operation:
• If operation is add x:
• currentValue += x
• If operation is save:
• Store currentValue in savepoints list
• If operation is rollback k:
• Set currentValue = savepoints.get(k)
4.After processing all operations, print currentValue.
Input / Output Format
Input Format
• First line: Integer q (number of operations)
• Next q lines:
• add x → add value x
• save → create a savepoint
• rollback k → rollback to savepoint index k (0-based)
• Next q lines:
• add x → add value x
• save → create a savepoint
• rollback k → rollback to savepoint index k (0-based)
Output Format
• Print one integer: the final value after all operations
Constraints
• 1 ≤ q ≤ 10^5
• -10^9 ≤ x ≤ 10^9
• Rollback index is always valid
• -10^9 ≤ x ≤ 10^9
• Rollback index is always valid
Examples
Input:
6
add 5
save
add 3
save
add 2
rollback 0
Output:
123
Example Solution (Public)
static int applyWithRollback(int[] ops){java.util.ArrayDeque<Integer> st=new java.util.ArrayDeque<>();int val=0;for(int op:ops){if(op==0){if(!st.isEmpty()) val=st.pop();}else{st.push(val);val+=op;}}return val;}
Official Solution Code
static int applyWithRollback(int[] ops){java.util.ArrayDeque<Integer> st=new java.util.ArrayDeque<>();int val=0;for(int op:ops){if(op==0){if(!st.isEmpty()) val=st.pop();}else{st.push(val);val+=op;}}return val;}
Please login to submit solutions.