FastPrep
Problem · Array

Adding Stack 2.0

Learn this problem
● MediumIMC logoIMCINTERNNEW GRADOA

Problem statement

Process a sequence of operations on a stack that starts empty. The stack supports these commands:

  • push v: push integer v.
  • pop: remove the top element.
  • inc i v: add v to each of the bottom i elements.

Return an array whose kth value is the sum of all values in the stack after the kth command. The sum of an empty stack is 0.

Every operation and every reported sum must be processed in O(1) time.

Function

processAddingStack(operations: String[]) → long[]

Examples

Example 1

operations = ["push 4","push 5","inc 2 1","pop","pop"]return = [4,9,11,5,0]

The first two sums are 4 and 9. The increment changes the stack to [5, 6] with sum 11; the two pops then leave sums 5 and 0.

Example 2

operations = ["push 1","push 2","inc 1 10","pop"]return = [1,3,13,11]

Incrementing only the bottom value changes [1, 2] to [11, 2], whose sum is 13. Popping 2 leaves a sum of 11.

Constraints

  • 1 <= operations.length <= 2 * 10^5
  • -10^9 <= v <= 10^9
  • For every inc i v, 1 <= i <= current stack size.
  • A pop command is issued only when the stack is nonempty.
  • Every command has exactly one of the three forms described above.
  • Every stack value and reported sum fits in a signed 64-bit integer.

More IMC problems

drafts saved locally
class Solution {
    public long[] processAddingStack(String[] operations) {
        // Write your code here.
        return new long[0];
    }
}
operations["push 4","push 5","inc 2 1","pop","pop"]
expected[4,9,11,5,0]
checking account