Several possible approaches to this problem are provided below, along with their complexity information.

At first glance, this seems like a simple problem, and there is a simple solution. Using an array as an underlying data structure, the #push and #pop methods are easy to implement, and the #increment method just involves iterating over n elements in the array and incrementing each of their values by one:

class StackPlus
  attr_reader :data

  def initialize
    # Use an array as the underlying data structure
    @data = []
  end

  def push(value)
    # Push a value onto the array
    data.push(value)
  end

  def pop
    # Edge case: return -1 if the array is empty
    return -1 unless data.size > 0

    # Otherwise, just pop the top element from the array
    data.pop
  end

  def increment(n)
    # We need to iterate over n elements from the array,
    # but if there are fewer than n elements in the array,
    # we can just iterate over the length of the array
    [n, data.size].min.times do |i|
      # increment the value of each element by 1
      data[i] += 1
    end
  end
end

We have a O(n) space complexity, since we need to create an array to store each element pushed on the stack.

We also have the following time complexity for each method:

• #push: O(1)
• #pop: O(1)
• #increment: O(n)

For the #increment method, the worst-case scenario is that we need to iterate over every element in the array to increment its value, so we end up with a linear runtime. Can we do better?

Our goal with this second solution is to improve the time complexity of the #increment method. That means that we need to find a way to increment each value in the stack without iterating over every element in the array when the #increment method is called.

One very useful piece of information is that we only need to check the values of the array when the #pop method is called. So we don't need to increment each value in the data array when the #increment method is called, we just need a way to keep track of all the #increment operations. We can then apply the correct incremented value when the #pop method is called.

To do this, we'll make a second array inc that will have the same number of elements as the data array. The inc array will keep track of the number of elements that need to be incremented by storing a value at the index position that corresponds to that number; the value stored will indicate the number of times those elements should be incremented. When the #pop method is called, the element will be incremented as indicated by the corresponding element in the inc array; in addition, if there are any remaining elements in the stack, the increment information will be passed down to the next element in the inc array so that those remaining elements also get incremented when they are popped off the stack.

The process is probably easier to visualize with some diagrams:

Before we start popping elements from the stack, our two arrays look like this:

• data: [2, 3, 5]
• inc: [0, 1, 0]

The inc array above tells us that the first two elements of the data array each need to be incremented by 1 when they are popped from the stack.

When #pop is called, we pop the top elements from both the data and inc arrays, add them together to get 5, and return that value. Then the arrays look like this:

• data: [2, 3]
• inc: [0, 1]

Calling #pop again, we pop data and inc, add them together to get 4, and return that value. But we also need to update the top of the inc array to keep track of the fact that the final value, 2, also needs to be incremented:

• data: [2]
• inc: [1]

Here's what this looks like in code:

class StackPlus
  attr_reader :inc, :data

  def initialize
    # initialize two arrays, one to encode the incrementing data
    @inc = []
    @data = []
  end

  def push(value)
    # we need to ensure that the `inc` array always has the same number of elements
    # as the `data` array, so any time a new element is pushed to the stack,
    # add 0 at the top of the `inc` array
    data.push(value)
    inc.push(0)
  end

  def pop
    return -1 unless data.size > 0

    # pop the top value from the `inc` array
    inc_val = inc.pop

    # we need to keep the top value of the `inc` array updated with the
    # information needed to increment the remaining values of the `data`
    # array, so whatever the top element of the `inc` array is should be updated
    inc[inc.size - 1] += inc_val if inc.size > 0

    # finally, pop the top element of the data array, and return the incremented value
    data.pop + inc_val
  end

  def increment(n)
    # since `n` may be greater than the size of our stack, we can get the correct index by
    # finding the minimum of `n` and the size of the stack
    i = [n, inc.size].min - 1

    # here, we encode the value we need to increment at the correct position in the `inc` array
    inc[i] += 1 if inc[i]
  end
end

This solution is not an easy one to figure out, so don't stress if you didn't come up with it! Try to make sure you understand the steps to implement this solution, then see if you can reproduce it on your own for practice. It's useful to see solutions like this to help in case you encounter similar problems in the future.

Since we have two arrays — one for the data, and one for the incrementing information — the space complexity is worse than our first solution, but it still simplifies to O(n).

We also have the following time complexity for each method:

• #push: O(1)
• #pop: O(1)
• #increment: O(1)

As you can see, we were able to improve #increment to a constant time operation, since we don't need to iterate over each element in the array. Instead, we just look up one element in the inc array and update its value.

Here's a slight variation on Solution 2 that involves storing the value and the increment data together in the same array. If you understood the approach to Solution 2, this should feel similar. The key change here is that there is only one array, data, and each element in that array is an array of two elements: the value, and the increment data.

Using our example from Solution 2:

stack = StackPlus.new
stack.push(2) # data is: [[2, 0]]
stack.push(3) # data is: [[2, 0], [3, 0]]
stack.increment(2) # data is: [[2, 0], [3, 1]]
stack.increment(5) # data is: [[2, 0], [3, 1], [5, 0]]
stack.pop # return 5 + 0, data is: [[2, 0], [3, 1]]
stack.pop # return 3 + 1, data is: [[2, 1]]
stack.pop # return 2 + 1, data is: []

Here's how this solution works:

class StackPlus
  attr_reader :data

  def initialize
    @data = []
  end

  def push(value)
    # store two values in the data array: the value itself, and the information
    # about how that value should be incremented
    data.push([value, 0])
  end

  def pop
    return -1 unless data.size > 0

    # each element in the `data` array is now an array of two elements [value, increment]
    value, inc = data.pop

    # we need to update the top element of the data array to have the correct information on incrementing
    data[data.size - 1][1] += inc if data.size > 0

    # return the incremented value
    value + inc
  end

  def increment(n)
    # find the element that needs to store the information about
    # how to increment the elements below
    i = [n, data.size].min - 1

    # since each element in the `data` array is now an array of two elements [value, increment]
    # we need to update the increment element at the correct position in the data array
    data[i][1] += 1 if data[i]
  end
end

We end up with the same space complexity as Solution 2, since we still need the same amount of space to encode our two-dimensional data array as we did for two separate inc and data arrays.

Our time complexity remains the same as well, since we're performing basically the same operations in push, pop, and increment.