Algo Notes

notes.py

Array/List
---

Product of array except self

# Optimal Solution
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l_mult = 1
        r_mult = 1
        n = len(nums)
        l_arr = [0] * n
        r_arr = [0] * n
        
        for i in range(n): 
            j = -i -1
            l_arr[i] = l_mult
            r_arr[j] = r_mult
            l_mult *= nums[i]
            r_mult *= nums[j]

        return [l*r for l, r in zip(l_arr, r_arr)]

# Time Complexity: O(n)
# Space Complexity: O(n)


Dynamic Programming
----

1D: min cost stairs

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # Top Down DP (Memoization)
        n = len(cost)
        memo = {0:0, 1:0}
        def min_cost(i):
            if i in memo:
                return memo[i]
            else:
                memo[i] = min(cost[i-2] + min_cost(i-2),
                              cost[i-1] + min_cost(i-1))
                return memo[i]

        return min_cost(n)
        # Time: O(n)
        # Space: O(n)


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # Bottom Up DP (Tabulation)
        n = len(cost)
        dp = [0] * (n+1)
        
        for i in range(2, n+1):
            dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])
        
        return dp[-1]

        # Time: O(n)
        # Space: O(n)
  
 2D: Unique paths
  
 class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Top Down DP (Memoization)
        # Time: O(m*n)
        # Space: O(m*n)

        memo = {(0,0): 1}
        def paths(i, j):
            if (i,j) in memo:
                return memo[(i,j)]
            elif i < 0 or j < 0 or i == m or j == n:
                return 0
            else:
                val = paths(i, j-1) + paths(i-1, j)
                memo[(i,j)] = val
                return val
        
        return paths(m-1, n-1)



class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Bottom Up DP (Tabulation)
        # Time: O(m*n)
        # Space: O(m*n)

        dp = []
        for _ in range(m):
            dp.append([0] * n)
        
        dp[0][0] = 1
        
        for i in range(m):
            for j in range(n):
                if i == j == 0:
                    continue
                    
                val = 0
                if i > 0:
                    val += dp[i-1][j]
                if j > 0:
                    val += dp[i][j-1]
                
                dp[i][j] = val
        
        return dp[m-1][n-1]
  

jump game
---
# Brute Force
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        smallest = [float('inf')]

        def backtrack(i=0, jumps=0):
            if i == n-1:
                smallest[0] = min(smallest[0], jumps)
                return
            
            max_jump = nums[i]
            max_reachable_index = min(i+max_jump, n-1)

            for new_index in range(max_reachable_index, i, -1):
                backtrack(new_index, jumps+1)
        
        backtrack()
        return smallest[0]
    
    
# Optimal    
class Solution:
    def jump(self, nums: List[int]) -> int:
        smallest = 0
        n = len(nums)
        end, far = 0, 0

        for i in range(n-1):
            far = max(far, i+nums[i])
            
            if i == end:
                smallest += 1
                end = far
        
        return smallest
        # Time: O(n)
        # Space: O(1)
        

      
 Graphs
----

Topo: Course Schedule
  
 class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        order = []
        g = defaultdict(list)
        for a, b in prerequisites:
            g[a].append(b)
        
        UNVISITED, VISITING, VISITED = 0, 1, 2
        states = [UNVISITED] * numCourses
        
        def dfs(i):
            if states[i] == VISITING:
                return False
            elif states[i] == VISITED:
                return True
            states[i] = VISITING

            for nei in g[i]:
                if not dfs(nei):
                    return False

            states[i] = VISITED
            order.append(i)
            return True

        
        for i in range(numCourses):
            if not dfs(i):
                return []
        
        return order # Time: O(V + E), Space: O(V + E)
      
      
No of Islands
---

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
                return
            else:
                grid[i][j] = "0"
                dfs(i, j + 1)
                dfs(i + 1, j)
                dfs(i, j - 1)
                dfs(i - 1, j)

        num_islands = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    num_islands += 1
                    dfs(i, j)

        return num_islands

# Time Complexity: O(m*n)
# Space Complexity: O(m*n)

Backtracking:
  
 Permute:
  class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans, sol = [], []

        def backtrack():
            if len(sol) == n:
                ans.append(sol[:])
                return

            for x in nums:
                if x not in sol:
                    sol.append(x)
                    backtrack()
                    sol.pop()

        backtrack()
        return ans
  
 Combine:
  
  class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans, sol = [], []

        def backtrack(x):
            if len(sol) == k:
                ans.append(sol[:])
                return

            left = x
            still_need = k - len(sol)

            if left > still_need:
                backtrack(x - 1)

            sol.append(x)
            backtrack(x - 1)
            sol.pop()

        backtrack(n)
        return ans
  
 letter in phone:
  
  class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []

        ans, sol = [], []
        
        letter_map = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        
        n = len(digits)

        def backtrack(i=0):
            if i == n:
                ans.append("".join(sol))
                return

            for letter in letter_map[digits[i]]:
                sol.append(letter)
                backtrack(i + 1)
                sol.pop()

        backtrack(0)
        return ans

# Time Complexity: O(n * 4^n)
# Space Complexity: O(n)

Heaps
----

Kth closet to origin
--
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        def dist(x, y):
            return x**2 + y**2

        heap = []
        for x, y in points:
            d = dist(x, y)
            if len(heap) < k:
                heapq.heappush(heap, (-d, x, y))
            else:
                heapq.heappushpop(heap, (-d, x, y))

        return [(x, y) for d, x, y in heap]

# Time Complexity: O(n log k)
# Space Complexity: O(k)

Top k frequest element
---
import heapq
from collections import Counter

def top_k_frequent(nums, k):
    # Step 1: Count frequency
    freq_map = Counter(nums)

    # Step 2: Use max heap (invert frequency to simulate max heap)
    max_heap = [(-freq, num) for num, freq in freq_map.items()]
    heapq.heapify(max_heap)  # Convert list into a heap in O(n)

    # Step 3: Extract k most frequent elements
    result = [heapq.heappop(max_heap)[1] for _ in range(k)]
    return result
    # Max Heap
    

 Trie
---
class Trie:
    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        d = self.trie

        for c in word:
            if c not in d:
                d[c] = {}
            d = d[c]

        d['.'] = '.'

    def search(self, word: str) -> bool:
        d = self.trie

        for c in word:
            if c not in d:
                return False
            d = d[c]

        return '.' in d

    def startsWith(self, prefix: str) -> bool:
        d = self.trie

        for c in prefix:
            if c not in d:
                return False
            d = d[c]

        return True
        
        # Time: O(N) where N is the length of any string
        # Space: O(T) where T is the total number of stored characters

 
Sliding Window
----

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        longest = 0
        sett = set()
        n = len(s)

        for r in range(n):
            while s[r] in sett:
                sett.remove(s[l])
                l += 1

            w = (r - l) + 1
            longest = max(longest, w)
            sett.add(s[r])

        return longest

# Time Complexity: O(n)

Binary Tree - max depth
----

# DFS
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return 1 + max(left, right)

# Time Complexity: O(n)
# Space Complexity: O(h) { here "h" is the height of the binary tree }

# BFS
class Solution:
    def maxDepth(self, root):
        if not root:
            return 0  # Height of an empty tree is 0
        
        queue = deque([root])
        height = 0

        while queue:
            level_size = len(queue)  # Number of nodes at the current level
            
            for _ in range(level_size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            height += 1  # Increment height at each level
        
        return height
    # Time Complexity: O(n)
    # Space Complexity: O(n)

Binary Search
---

Search in rotated array
--
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = 0
        r = n - 1

        while l < r:
            m = (l + r) // 2

            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m

        min_i = l

        if min_i == 0:
            l, r = 0, n - 1
        elif target >= nums[0] and target <= nums[min_i - 1]:
            l, r = 0, min_i - 1
        else:
            l, r = min_i, n - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        return -1

# Time Complexity: O(log(n))
# Space Complexity: O(1)

Linked List
---

remove nth node
--

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        behind = ahead = dummy

        for _ in range(n + 1):
            ahead = ahead.next

        while ahead:
            behind = behind.next
            ahead = ahead.next

        behind.next = behind.next.next

        return dummy.next

# Time Complexity: O(n)
# Space Complexity: O(1)

Stack:
---

reverse polish
---
from math import ceil, floor
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stk = []
        for t in tokens:
            if t in "+-*/":
                b, a = stk.pop(), stk.pop()

                if t == "+":
                    stk.append(a + b)
                elif t == "-":
                    stk.append(a - b)
                elif t == "*":
                    stk.append(a * b)
                else:
                    division = a / b
                    if division < 0:
                        stk.append(ceil(division))
                    else:
                        stk.append(floor(division))
            else:
                stk.append(int(t))

        return stk[0]

# Time Complexity: O(n)
# Space Complexity: O(n)

Two Pointers
---

Container most water
--
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l = 0
        r = n - 1
        max_area = 0

        while l < r:
            w = r - l
            h = min(height[l], height[r])
            a = w * h
            max_area = max(max_area, a)
            
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return max_area

# Time Complexity: O(n)
# Space Complexity: O(1)

Heaps
---

group anagram 
--

# Optimal Solution
from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams_dict = defaultdict(list)
        for s in strs: # n
            count = [0] * 26
            for c in s:
                count[ord(c) - ord("a")] += 1
            key = tuple(count)
            anagrams_dict[key].append(s)

        return anagrams_dict.values()
# n is the number of strings, m is the length of largest string
# Time Complexity: O(n * m)
# Space Complexity: O(n * m)