Practice DSA

min_stack.md

MinStack

Design a Stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Solution

To solve this problem, we'll use two stacks. The first stack, which is the main stack, will store all elements. The other stack will keep track of the minimum elements.

When pushing an element, we'll add it to the main stack. If it's smaller than or equal to the current minimum, we'll also add it to the minimum stack.

For pop operations, we'll remove from both stacks if the popped element is the current minimum.

The top operation will return the top of the main stack, while getMin will return the top of the minimum stack.

This approach ensures all operations have O(1) time complexity because each operation only involves adding or removing elements from the top of the stacks, which are constant-time operations.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def getMin(self):
        if self.min_stack:
            return self.min_stack[-1]

    def push(self, val):
        if not self.min_stack or self.min_stack[-1] >= val:
            self.min_stack.append(val)
        self.stack.append(val)

    def pop(self):
        if self.stack:
            if self.min_stack and self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.stack.pop()

    def top(self):
        if self.stack:
            return self.stack[-1]


minStack = MinStack()

print(minStack.getMin())
minStack.push(3)
minStack.push(5)
minStack.push(2)
minStack.push(6)
minStack.push(1)

print(minStack.getMin())

minStack.pop()
print(minStack.getMin())
minStack.pop()
print(minStack.getMin())
minStack.pop()
print(minStack.getMin())
minStack.pop()
print(minStack.getMin())

n_queens.py

class Solution:
  def __init__(self):
    self.solve_count = 0

  def solveNQueens(self, n: int) -> list[list[str]]:
    # Check if queen at row and columns is safe from other queens
    def issafe(r,c):
      n = len(board)
      for i in range(n):
        # Check Queen present at upper direction (same column)
        if board[i][c] == 'Q':
          return False
        # Check Queen is present at left upper diagonal direction
        if r - i >= 0 and c - i >= 0 and board[r-i][c-i] == 'Q':
          return False
        # Check Queen is present at right upper diagonal direction
        if r - i >= 0 and c + i < n and board[r-i][c+i] == 'Q':
          return False
      return True

    # Recursive method
    # Starts from row 0 and iterates all the columns
    #
    def solve(r):
      n = len(board)
      self.solve_count += 1
      # If row is at max, then add the solution to ANS and print current board
      if r == n:
        print(board)
        ans.append(["".join(i) for i in board])
        return

      # Iterate column by colum
      for c in range(0,n):
        # print(r,c)
        # If queen is not safe, then move back to previous row and change queen's column. Then check for safety
        if issafe(r,c):
          # If Queen is safe, then place the queen. Now, move to next row
          board[r][c] = 'Q'
          solve(r+1)
          # Remove the queen
          board[r][c] = '.'

    # Create Empty board
    board = [['.']*n for i in range(n)]
    # Collect all possible answerws
    ans =[]
    # start with 0th row
    solve(0)
    # At the very end, the board will be clear
    print(board)

    print(self.solve_count)
    return ans

s = Solution()
s.solveNQueens(8)

Practice DSA Plan.md

System Design repo list

https://github.com/stars/valarpirai/lists/system-design

Object oriented system design - LLD

https://github.com/tssovi/grokking-the-object-oriented-design-interview

My Courses

https://www.udemy.com/home/my-courses/learning/

DSA

Interview Questions - https://github.com/mission-peace/interview/wiki

Array

https://www.techinterviewhandbook.org/algorithms/array/ Sliding window - https://leetcode.com/problems/minimum-window-substring/solutions/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems/

practice.ipynb

practice_old.ipynb

RateLimitter.ipynb

N Queens - Total iterations 2057
Total answers - 92 (from wiki)