Problem of The Day: Shortest Path in Binary Matrix

Problem Statement

Brute Force - [Accepted]

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.size = maxSize

    def push(self, x: int) -> None:
        if len(self.stack) < self.size:
            self.stack.append(x)

    def pop(self) -> int:
        if not self.stack:
            return -1
        return self.stack.pop()

    def increment(self, k: int, val: int) -> None:
        topElems = len(self.stack) - k
        other_stack = []
        if topElems >= 0:
            while topElems > 0:
                other_stack.append(self.pop())
                topElems -= 1
            while self.stack:
                other_stack.append(self.pop() + val)
            while other_stack:
                self.stack.append(other_stack.pop())
        else:
            while self.stack:
                other_stack.append(self.pop() + val)
            while other_stack:
                self.stack.append(other_stack.pop())


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

Intuition

The problem asks for the implementation of a stack that has a fixed size and two additional functionalities: a push method that only adds elements if the stack is not full, and an increment method that increments the first k elements by a given value. The pop method should work as in a standard stack by removing and returning the top element. My initial thought is to manage this with an array of fixed size and manually control the index for tracking the top of the stack.

Approach

1. Push Operation: For the push method, I’ll check if the stack is not full by comparing the current index with the maximum size. If it’s not full, I’ll increment the index and assign the element to that position in the array.
2. Pop Operation: For pop, I’ll check if the stack is not empty (index greater than or equal to zero). If it’s empty, return -1. Otherwise, return the top element and decrement the index.
3. Increment Operation: For the increment method, I’ll iterate over the first k elements (or up to the current top of the stack if k is greater than the number of elements) and add the given value to each.

Complexity

• Time complexity:

  • Push: \(O(1)\) since we are just incrementing the index and inserting the value.
  • Pop: \(O(1)\) since we are just decrementing the index and returning the value.
  • Increment: \(O(k)\) where k is the number of elements we are incrementing. In the worst case, this could be \(O(n)\) where n is the size of the stack.

• Space complexity:

  • The space complexity is \(O(n)\) since we are using an array to store the elements, where n is the maximum size of the stack.

Code

class CustomStack:

    def __init__(self, maxSize: int):
        self.arr = [0] * maxSize
        self.index = -1
        self.size = maxSize

    def push(self, x: int) -> None:
        if self.index < self.size - 1:
            self.index += 1
            self.arr[self.index] = x

    def pop(self) -> int:
        if self.index < 0:
            return -1
        self.index -= 1
        return self.arr[self.index + 1]

    def increment(self, k: int, val: int) -> None:
        if k <= self.index + 1:
            for i in range(k):
                self.arr[i] += val
        else:
            for i in range(self.index + 1):
                self.arr[i] += val

# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)