cpps2: Queue and Stack

[hon9g]

Click ✔️ to go to each solution. The Link to each problem🌐 is at the top of each solution.

#	title	my solution
1	Largest Rectangle in Histogram	✔️
2	Binary Search Tree Iterator	✔️
3	Asteroid Collision	✔️
4	Daily Temperatures	✔️
5	Design Circular Queue	✔️

+

Problems selected by LeetCode for the topic Queue and Stack 🌐

🔗 Queue : First-in First-out Data Structure

#	title	my solution
1	Design Circular Queue	✔️

🔗 Queue and BFS

#	title	my solution
1	Number of Islands	✔️
2	Open the Lock	✔️
3	Perfect Squares	✔️

🔗 Stack : Last-in First-out Data Structure

#	title	my solution
1	Min Stack	✔️
2	Valid Parentheses	✔️
3	Daily Temperatures	✔️
4	Evaluate Reverse Polish Notation	✔️

🔗 Stack and DFS

#	title	my solution
1	Number of Islands	✔️
2	Clone Graph	✔️
3	Target Sum	✔️
4	Binary Tree Inorder Traversal	✔️

🔗 Stack and Queue

#	title	my solution
1

[hon9g]

Q5. Design Circular Queue

• 🌐problem
• 🔗 Queue : First-in First-out Data Structure

Circular Queue by Array

• Time complexity: O(1) for all methods

• Space complexity: O(k)

  class MyCircularQueue:
  
  def __init__(self, k: int):
      """
      Initialize your data structure here. Set the size of the queue to be k.
      """
      self.queue = [None] * k
      self.head, self.tail, self.k = -1, -1, k
  
  def enQueue(self, value: int) -> bool:
      """
      Insert an element into the circular queue. Return true if the operation is successful.
      """
      if self.isFull():
          return False
      elif self.isEmpty():
          self.head = self.tail = 0
      else:
          self.tail = (self.tail + 1) % self.k
      self.queue[self.tail] = value
      return True
  
  def deQueue(self) -> bool:
      """
      Delete an element from the circular queue. Return true if the operation is successful.
      """
      if self.isEmpty():
          return False
      elif self.head == self.tail:
          self.head = self.tail = -1
      else:
          self.head = (self.head + 1) % self.k
      return True
  
  def Front(self) -> int:
      """
      Get the front item from the queue.
      """
      return self.queue[self.head] if not self.isEmpty() else -1
  
  def Rear(self) -> int:
      """
      Get the last item from the queue.
      """
      return self.queue[self.tail] if not self.isEmpty() else -1
  
  def isEmpty(self) -> bool:
      """
      Checks whether the circular queue is empty or not.
      """
      return self.head == -1
  
  def isFull(self) -> bool:
      """
      Checks whether the circular queue is full or not.
      """
      return (self.head - 1) % self.k == self.tail % self.k

Circular Queue by Linked List

• Time complexity: O(1) for all methods
• Space complexity: O(k) when the queue is full

class Node:
    def __init__(self, x: int):
        self.val = x
        self.next = None

class MyCircularQueue:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self.capacity, self.count = k, 0
        self.head = self.tail  = None

    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.isFull():
            return False
        elif self.isEmpty():
            self.head = self.tail = Node(value)
        else:
            self.tail.next = Node(value)
            self.tail = self.tail.next
        self.count += 1
        return True

    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
        elif self.head == self.tail:
            self.head = self.tail = None
        else:
            self.head = self.head.next
        self.count -= 1
        return True

    def Front(self) -> int:
        """
        Get the front item from the queue.
        """
        return self.head.val if not self.isEmpty() else -1

    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """
        return self.tail.val if not self.isEmpty() else -1

    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        return self.count == 0

    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        return self.capacity <= self.count

[hon9g]

Number of Islands

• 🌐problem

  🔗 Stack and DFS

• Time complexity: O(NM)

• Space complexity: O(NM) in worst case because of the call stack for recursion

  class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
      if grid == []: return 0
  
      N, M, cnt = len(grid), len(grid[0]), 0
  
      def dfs(n,m):
          for x in [-1, +1]:
              if n + x >= 0 and n + x < N and grid[n + x][m] == '1':
                  grid[n + x][m] = '0'
                  dfs(n + x,m)
              if m + x >= 0 and m + x < M and grid[n][m + x] == '1':
                  grid[n][m + x] = '0'
                  dfs(n, m + x)
  
      for n in range(N):
          for m in range(M):
              if grid[n][m] == '1':
                  grid[n][m] = '0'
                  cnt += 1
                  dfs(n,m)
      return cnt

  🔗 Queue and Breadth First Search

• Time complexity: O(NM)

• Space complexity: O(NM)

  class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
      if grid == []: return 0
  
      N, M, cnt = len(grid), len(grid[0]), 0
  
      def checkVisited(queue, idx):
          while idx < len(queue):
              n, m = queue[idx]
              for x in (-1, 1):
                  if n+x>=0 and n+x<N and grid[n+x][m] == '1':
                      grid[n+x][m] = '0'
                      queue.append((n+x, m))
                  if m+x>=0 and m+x<M and grid[n][m+x] == '1':
                      grid[n][m+x] = '0'
                      queue.append((n,m+x))
              idx += 1
  
      for n in range(N):
          for m in range(M):
              if grid[n][m] == '1':
                  grid[n][m] = '0'
                  checkVisited([(n,m)],0)
                  cnt += 1
      return cnt     

[hon9g]

Open the Lock

• 🌐problem

🔗 Queue and BFS

• Time complexity: O()
• Space complexity: O()

  class Solution:
  def openLock(self, deadends: List[str], target: str) -> int:
      if target == '0000': return 0
      queue, next_queue, depth, deadends = {target}, set(), 1, set(deadends)
      deadends.add(target)
      if '0000' in deadends: return -1
      while queue:
          for node in queue:
              for x in [-1, +1]:
                  for i in range(4):
                      lock = node[:i] + str((int(node[i]) + x)%10) + node[i+1:]
                      if lock == '0000':
                          return depth
                      if lock not in deadends:
                          next_queue.add(lock)
                      deadends.add(lock)
          queue, next_queue = next_queue, set()
          depth += 1
      return -1

[hon9g]

Perfect Squares

• 🌐problem

  🔗 Queue and BFS

• Time complexity: O(n √n)
• Space complexity: O(n)

  class Solution:
  def numSquares(self, n: int) -> int:
      squares = [x**2 for x in range(1, int(n**0.5) + 1)]
      queue, next_queue, depth = {n}, set(), 1
      while queue:
          for node in queue:
              for square in squares:
                  if node == square:
                      return depth
                  elif node < square:
                      break
                  next_queue.add(node - square)
          queue, next_queue = next_queue, set()
          depth += 1
      return n

[hon9g]

Min Stack

• 🌐problem
• 🔗 Stack : Last-in First-out Data Structure

Stack min values

• Time complexity: O(1) for all methods
• Space complexity: O(N)

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self._stack = []

    def push(self, x: int) -> None:
        if not self._stack:
            self._stack.append((x, x))
        else:
            self._stack.append((x, min(self._stack[-1][1], x)))

    def pop(self) -> None:
        return self._stack.pop()

    def top(self) -> int:
        return self._stack[-1][0] if self._stack else None

    def getMin(self) -> int:
        return self._stack[-1][1] if self._stack else None

Sort the stack to get a min value

• Time complexity: O(1) for push() pop() top() / O(n log n) for getMin()

• Space complexity: O(N log N)

  class MinStack:
  
  def __init__(self):
      """
      initialize your data structure here.
      """
      self._stack = []
  
  def push(self, x: int) -> None:
      self._stack.append(x)
  
  def pop(self) -> None:
      if self._stack: self._stack.pop()
  
  def top(self) -> int:
      return self._stack[-1] if self._stack else False
  
  def getMin(self) -> int:
      return sorted(self._stack)[0] if self._stack else False

[hon9g]

Valid Parentheses

• 🌐problem

🔗 Stack : Last-in First-out Data Structure

• Time complexity: O(N)
• Space complexity: O(N)

  class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      right = {')': '(', ']': '[', '}': '{'}
      for e in s:
          if e in right.keys():
              if not stack: return False
              elif stack.pop() != right[e]:
                  return False
          else:
              stack.append(e)
      return True if not stack else False

[hon9g]

Q4. Daily Temperatures

• 🌐problem

🔗 Stack : iterate over every day of future (TLE)

• Time complexity: O(N^N)
• Space complexity: O(N)

  class Solution:
  def dailyTemperatures(self, T: List[int]) -> List[int]:
      passed, res = [], [0]
      while T:
          passed.append(T.pop())
          if T:
              days = 0
              for p in reversed(passed):
                  days += 1
                  if T[-1] < p:
                      res.append(days)
                      break
              else:
                  res.append(0)
      return reversed(res)

🔗 Stack : iterate over warmer days of future

• Time complexity: O(N^W)
• Space complexity: O(N)

  class Solution:
  def dailyTemperatures(self, T: List[int]) -> List[int]:
      warmers, res = [], [0] * len(T)
      for i in range(len(T) - 1, -1, -1):
          while warmers and T[warmers[-1]] <= T[i]:
              warmers.pop()
          if warmers:
              res[i] = warmers[-1] - i
          warmers.append((i))
      return res

[hon9g]

Evaluate Reverse Polish Notation

• 🌐problem

🔗 Stack the numbers

• Time complexity: O(N)
• Space complexity: O(N)

  class Solution:
  def evalRPN(self, tokens: List[str]) -> int:
      operator, nums = {'+', '-', '*', '/'}, []
      for token in tokens:
          if token in operator:
              b, a = nums.pop(), nums.pop()
              if token == '+':   nums.append(a + b)
              elif token == '-': nums.append(a - b)
              elif token == '*': nums.append(a * b)
              elif token == '/': nums.append(int(a / b))
          else:
              nums.append(int(token))
      return nums[0]

[hon9g]

Clone Graph

• 🌐problem

🔗 Stack and DFS

• Time complexity: O(N)
• Space complexity: O(N) because of the call stack

  
  """
  # Definition for a Node.
  class Node:
  def __init__(self, val, neighbors):
      self.val = val
      self.neighbors = neighbors
  """

class Solution(object): def init(self): self.visited = {}

def cloneGraph(self, node):
    if not node: return node
    if node in self.visited: return self.visited[node]

    self.visited[node] = Node(node.val, [])

    if node.neighbors:
        self.visited[node].neighbors = [self.cloneGraph(n) for n in node.neighbors]

    return self.visited[node]

[hon9g]

Target Sum

• 🌐problem

🔗 DFS

• Time complexity: O(2^N) N = len(nums)

• Space complexity: O(N) depth of recursion tree

  class Solution:
  def __init__(self):
      self.cnt = 0
  
  def findTargetSumWays(self, nums: List[int], S: int) -> int:
  
      def targetSumWay(idx: int, s: int):
          if idx < len(nums):
              for x in [-1, +1]:
                  targetSumWay(idx + 1, nums[idx] * x + s)
          else:
              if S == s: self.cnt += 1
  
      targetSumWay(0, 0)    
      return self.cnt

🔗 DFS with memorization

• Time complexity: O(NK) N = len(nums) K = len(memo)
• Space complexity: O(N) depth of recursion tree

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.memo = {}

        def targetSumWay(idx: int, s: int):
            if idx < len(nums):
                if (idx, s) in self.memo.keys():
                    return self.memo[(idx, s)]
                a = targetSumWay(idx + 1, nums[idx] * -1 + s)
                b = targetSumWay(idx + 1, nums[idx] + s)
                self.memo[(idx, s)] = a + b
                return self.memo[(idx, s)]
            else:
                return 1 if S == s else 0
        return targetSumWay(0, 0)

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.memo = {}

        def targetSumWay(idx: int, s: int):
            if idx < len(nums):
                v1, v2 = nums[idx] * -1 + s, nums[idx] + s
                a = self.memo[(idx + 1, v1)] if (idx + 1, v1) in self.memo.keys() else targetSumWay(idx + 1, v1)
                b = self.memo[(idx + 1, v2)] if (idx + 1, v2) in self.memo.keys() else targetSumWay(idx + 1, v2)
                self.memo[(idx, s)] = a + b
                return self.memo[(idx, s)]
            else:
                return 1 if S == s else 0

        return targetSumWay(0, 0)

[hon9g]

Binary Tree Inorder Traversal

• 🌐problem

Recursive DFS

• Time complexity: O(N) recursion takes N

• Space complexity: O(N) depth of recursion tree

  class Solution:
  def inorderTraversal(self, root: TreeNode) -> List[int]:
      self.result = []
      self.traverse(root)
      return self.result
  
  def traverse(self, node):
      if not node: return
      self.traverse(node.left)
      self.result.append(node.val)
      self.traverse(node.right)

• Time complexity: O(N^2) recursion takes N x expend takes N in worst case

• Space complexity: O(N) depth of recursion tree

  class Solution:
  def inorderTraversal(self, root: TreeNode) -> List[int]:
      return self.traverse(root) if root else []
  
  def traverse(self, node):
      left = self.traverse(node.left) if node.left else []
      right = self.traverse(node.right) if node.right else []
      return left + [node.val] + right

  Iterative DFS

• Time complexity: O(N) N = number of nodes

• Space complexity: O(N) Stack takes N space in worst case

  class Solution:
  def inorderTraversal(self, root: TreeNode) -> List[int]:
      self.stack, res = [], []
      self.stackLeft(root)
      while self.stack:
          node = self.stack.pop()
          res.append(node.val)
          if node.right:
              self.stackLeft(node.right)
      return res
  
  def stackLeft(self, node):
      while node:
          self.stack.append(node)
          node = node.left

[hon9g]

Q1. Largest Rectangle in Histogram

• 🌐problem
• Time complexity: O(N^2)
• Space complexity: O(1)

  class Solution:
  def largestRectangleArea(self, heights: List[int]) -> int:
      heights.append(0)
      idx, area = [-1], max(heights)
      for i in range(len(heights)):
          while idx and heights[i] < heights[idx[-1]]:
              h = heights[idx.pop()]
              w = i - idx[-1] - 1
              area = max(area, h * w)
          idx.append(i)
      return area

[hon9g]

Q2. Binary Search Tree Iterator

• 🌐problem
• Time complexity:
  • next(): O(n) n = number of left node of current node.right
  • hasNext(): O(1)

• Space complexity: O(N) N = number of tree nodes

  class BSTIterator:
  
  def __init__(self, root: TreeNode):
      self.stack = []
      self.stackLeft(root)
  
  def stackLeft(self, node):
      while node:
          self.stack.append(node)
          node = node.left
  
  def next(self) -> int:
      """
      @return the next smallest number
      """
      if not self.hasNext(): return
      node = self.stack.pop()
      if node.right:
          self.stackLeft(node.right)
      return node.val
  
  def hasNext(self) -> bool:
      """
      @return whether we have a next smallest number
      """
      return 0 < len(self.stack)

[hon9g]

Q3. Asteroid Collision

• 🌐problem
• Time complexity: O(N)
• Space complexity: O(N)

  class Solution:
  def asteroidCollision(self, asteroids: List[int]) -> List[int]:
      res = []
      for a in asteroids:
          if a < 0:
              while res and res[-1] > 0:
                  b = res.pop()
                  if a*-1 < b:
                      res.append(b)
                      break
                  elif a*-1 == b:
                      break
              else: res.append(a)
          else: res.append(a)
      return res

[hon9g]

• 🌐problem
• Time complexity: O()
• Space complexity: O()

[hon9g]

• 🌐problem
• Time complexity: O()
• Space complexity: O()

[hon9g]

• 🌐problem
• Time complexity: O()
• Space complexity: O()