DSA Cheatsheet

List (Dynamic Array)

list = [1, 2, 3]

Operation	Code	Time complexity
Get / Set element	`list[i]` or `list[i] = 3`	O(1)
Add element	`list.append(3)`	O(1)
Add at an index	`list.insert(i, 3)`	O(n)
Pop last element	`list.pop()`	O(1)
Pop at an index	`list.pop(i)`	O(n)
Delete element by value	`list.remove(3)`	O(n)
Search element	`3 in x`	O(n)
Find index of element	`list.index(3)`	O(n) Use Dictionary [element → index] instead
Sort	`sorted_list = sorted(list, reverse = False)` or `list.sort()`	O(n log n)

Last element: list[-1]
Reverse: list[::-1]
Merge two lists together: list1 + list2
Use as a Stack: .append() to add and .pop() to remove.
Tuple: immutable list tuple(1, 2, 3) - can be used as a key for the dictionary (but list cant be)

Dictionary (Hash Map)

dict = {'a':1, 'b':2}

Operation	Code	Time complexity
Add / Set	`dict[k] = 3`	O(1)
Get value	`dict.get(k, default_value)`	O(1)
Delete key	`del dict[k]`	O(1)
Search key	`k in dict`	O(1)
Sort by keys	`sorted_dict = dict(sorted(dict.items(), reverse=False))`	O(n log n)
Sort by values	`sorted_dict = dict(sorted(d.items(), key=lambda item: item[1]))`	O(n log n)

For loop: for k,v in dict.items():
Just keys: dict.keys()
Just values: dict.values()
List to dictionary: labels = dict(zip(keys, values))

from collections import Counter

# Initialize
c = Counter(['a','a','b'])    # From iterable
c = Counter("hello")          # From string

# Operations
c.most_common(2)      # Top 2 frequent elements
c['a'] += 1           # Increment count
c.update("more")      # Add counts from iterable
c.total()             # Sum of all counts

Set (Hash Set)

s = set() → Unordered list with no repeating items

Add element	`s.add(3)`	O(1)
Remove element	`s.remove(3)`	O(1)
Search element	`3 in s`	O(1)

Strings

Split by white space: words_list = str.split()
Convert to lower case: str.lower()
Replace: str.replace(”new”, ”old”)
Index of substring: str.find(’sub’)
Count occurrences: str.count(’sub’)
Check for palindrome: if s==s[::-1]
Check if alphanumeric: str.isalnum()
Char to ASCII int value: ord() and back to char: chr()

# Iteration Helpers
enumerate(lst)        # Index + value pairs
zip(lst1, lst2)      # Parallel iteration
map(fn, lst)         # Apply function to all elements

# Type Conversion
int('42')            # String to int
str(42)              # Int to string
list('abc')          # String to list
''.join(['a','b'])   # List to string
set([1,2,2])         # List to set: removes duplication

# Math
abs(-5)              # Absolute value
pow(2, 3)            # Power
round(3.14159, 2)    # Round to decimals

# Sort by length then alphabetically
words.sort(key=lambda x: (len(x), x))

Binary Search: O(log n)

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l+r)//2
        if nums[mid] == target: return mid
        elif nums[mid] < target: l = mid+1
        else: r = mid-1
    return -1

Two Pointers: O(n)

Use them to decreased the time complexity of O(n^2) to O(n). When you want to traverse an array to do some computation between numbers.

Converging pointers: Initialize them in two ends of an array and move any one of them with certain conditions by comparing the two pointers themselves.

def two_sum_sorted(nums, target):
    l, r = 0, len(nums)-1
    while l < r:
        s = nums[l] + nums[r]
        if s == target: return [l, r]
        if s < target: l += 1
        else: r -= 1

Parallel pointers/Sliding window: Initialize both at the start and move in the same direction. Left pointer handles the constraint whereas right pointer goes out to explore better options. Once the right pointer exceeds the valid condition, we move the left pointer to make it valid again.

def maxProfit(self, prices: List[int]) -> int:
    # l = buy, r = sell
    l = 0
    max_profit = 0

    for r in range(len(prices)):
        if prices[r] < prices[l]:
                # shift buy pointer to the lower price
                l = r
        else:
            profit = prices[r] - prices[l]
            max_profit = max(max_profit, profit)

    return max_profit

DFS: O(m*n) → Stack

Used when a shortest path to goal is to be found.

def numIslands(self, grid: List[List[str]]) -> int:
   visited = set()
   count = 0

    for r in range(len(grid)):
        for c in range(len(grid[0])):
            
            if grid[r][c] == "1" and (r, c) not in visited: 
                count += 1
                stack = [(r, c)]

                while stack:
                    i, j = stack.pop()
                    if (i, j) not in visited and i >= 0 and i < len(grid) and j >= 0 and 
                    j < len(grid[0]) and grid[i][j] == "1":
                        visited.add((i, j))
                        stack += [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]
	return counts

Another way of writing it recursively,

visited = set()
count = 0

def dfs(r, c):
    if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0" or (r, c) in visited:
        return
        
    visited.add((r, c))
    dfs(r+1, c)
    dfs(r-1, c)
    dfs(r, c+1)
    dfs(r, c-1)
    
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "1" and (r, c) not in visited:
		    count += 1
            grid[r][c] = dfs(r, c)

DFS + Backtracking

Remove the parent node after checking all the children so that other paths can explore it.
Used when you want to compute all paths to the goal.

def dfs(r, c):
    if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0" or (r, c) in visited:
        return
        
    visited.add((r, c))
    best = min(dfs(r+1, c), dfs(r-1, c), dfs(r, c+1), dfs(r, c-1))
    visited.remove((r, c))  # Backtracking!
    return best

BFS: O(m*n) → Queue

Used we need to find the path to goal for each element in grid. So start from the goal itself and go in all directions.

def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        
  visited = set()
  queue = deque()

  # Add goals
  for r in range(rows):
      for c in range(cols):
          if grid[r][c] == 0:
              queue.append((r, c))
  
  # Run BFS
  dist = 0
  while queue:
      for i in range(len(queue)):
          r, c = queue.popleft()
          if (r, c) not in visited and r >= 0 and r < rows and c >= 0 and c < cols and grid[r][c] != -1:
              visited.add((r, c))
              grid[r][c] = dist
              queue.append((r+1, c))
              queue.append((r-1, c))
              queue.append((r, c-1))
              queue.append((r, c+1))
      dist += 1

Dynamic Programming

Watch this playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY

List (Dynamic Array)#

Dictionary (Hash Map)#

Set (Hash Set)#

Strings#

Binary Search: O(log n)#

Two Pointers: O(n)#

DFS: O(m*n) → Stack#

DFS + Backtracking#

BFS: O(m*n) → Queue#

Dynamic Programming#