Daily Challenge 09/30/2024: Design a Stack With Increment Operation.

Design a stack that supports increment operations on its elements.

Find the problem statement on leetcode. There will be no analysis on todays post as this problem was trivial and likely should have had a difficulty of easy instead of medium.

Solutions

Initial Solution

My initial solution was a bit slow, ranking in the \(40\%\) quantile for runtime - however it did well in memory in the \(87\%\) quantile.

class CustomStackInitial:

    top_max: int
    top: int
    data: list[int]

    def __init__(self, maxSize: int):

        self.top_max = maxSize - 1
        self.top = -1
        self.data = [-1 for _ in range(maxSize)]

    def push(self, x: int) -> None:
        if self.top == self.top_max:
            return

        self.top += 1
        self.data[self.top] = x

    def pop(self) -> int:
        if self.top < 0:
            return -1

        x = self.data[self.top]
        self.data[self.top] = -1
        self.top -= 1
        return x

    def increment(self, k: int, val: int) -> None:

        # NOTE: Use the minimum since if ``k`` exceeds ``top_max`` all elements
        #       should be incremented. Should do nothing when ``k=0``.
        for j in range(min(k, self.top_max + 1)):
            self.data[j] += val

        return

Improved Solution

Obviously the above solution has linear runtime with respect to the number of elements incremented. I decided to read the editorial to see if there was a clever solution. This solution was so clever that in fact it reduced the time complexity of incrementing to be linear. This is done by maintaining only one entry for the increment and lazily computing the incremented value.

The drawing bellow attempts to demonstrate this:

stack = Stack(5)


After stack.push(1), stack.push(2), stack.push(3), stack.push(4)

Stack      | 1  | 2  | 3  | 4  | -1 |
Increments | 0  | 0  | 0  | 0  | 0  |
Pop        | 1  | 2  | 3  | 4  |


After stack.increment(5, 5). Put 5 in the highest available index.

Stack      | 1  | 2  | 3  | 4  | -1 |
Increments | 0  | 0  | 0  | 5  | 0  |
Pop        | 6  | 7  | 8  | 9  |


After stack.increment(3, 5). Put 5 in the index for the third item.

Stack      | 1  | 2  | 3  | 4  | -1 |
Increments | 0  | 0  | 5  | 5  | 0  |
Pop        | 11 | 12 | 13 | 9  |


After stack.pop() should get 9 by adding the top to the increment. The 
increment should be added to its left neighbor.

Stack      | 1  | 2  | 3  | -1 | -1 |
Increments | 0  | 0  | 10 | 0  | 0  |
Pop        | 11 | 12 | 13 |


stack.pop()
Stack      | 1  | 2  | -1 | -1 | -1 |
Increments | 0  | 10 | 0  | 0  | 0  |
Pop        | 11 | 12 |

This solution performed much better in runtime, and placed in the \(98\%\) for runtime and a sad \(18\%\) for memory. However, the memory used only increased by 1 MB, so the decrease in memory performance is less sad than is apparent.

class CustomStack:

    top_max: int
    top: int
    data: list[int]

    def __init__(self, maxSize: int):

        self.top_max = maxSize - 1
        self.top = -1
        self.data = [-1 for _ in range(maxSize)]
        self.increments = [0 for _ in range(maxSize)]

    def push(self, x: int) -> None:
        if self.top == self.top_max:
            return

        self.top += 1
        self.data[self.top] = x

    def pop(self) -> int:
        if self.top < 0:
            return -1

        x = self.data[self.top]
        y = self.increments[self.top]

        self.data[self.top] = -1
        self.increments[self.top] = 0
        self.top -= 1

        if self.top > -1:
            self.increments[self.top] += y

        return x + y

    def increment(self, k: int, val: int) -> None:

        if self.top < 0:
            return

        index = min(k - 1, self.top)
        self.increments[index] += val

        return