Arrays / Lists

1D List

l = [0] * 3 # list of size 3 with all elements initialized to 0

2D List

l = [[0] * 3] * 3 # list of size 3 with all elements initialized to [0, 0, 0]

Insert element at the end of the list

l.append(1)

Peek element at the end of the list

l[-1]

Remove element from the end of the list

l.pop()

Remove element from the list

l.remove(1) # removes the first item that matches the item

Different ways of iterating over a list

for i in range(len(l)):
  print(l[i])

for i in l:
  print(i)

for i, item in enumerate(l):
  print(i, item) # i is the index, item is the value

Map, Filter, Zip, Extend

map(lambda x: x * 2, [1, 2, 3]) # [2, 4, 6]

filter(lambda x: x % 2 == 0, [1, 2, 3]) # [2]

zip([1, 2, 3], [4, 5, 6]) # [(1, 4), (2, 5), (3, 6)]

l1, l2 = [1, 2, 3, 4], [5, 6, 7, 8]
l1.extend(l2) # [1, 2, 3, 4, 5, 6, 7, 8]

List Comprehension

l = [i for i in range(10)] # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Hashmaps / Dictionaries

Insert element into the dictionary

d = {}
d["key"] = "value"

Remove element from the dictionary

del d["key"]

Check if key exists in the dictionary

if "key" in d:
  print("key exists")

setdefault

# The setdefault() method returns the value of the item with the specified key.
# If the key does not exist, insert the key, with the specified value, see example below
x = car.setdefault("model", "Bronco")

pop

If key is in the dictionary, returns its value and removes it from the dictionary.
If key not in the dictionary, returns the value in default.
If key not in the dictionary and default is not given, raises KeyError.

x = car.pop(key, default)

Different ways of iterating over a dictionary

for key in d:
  print(key, d[key])

for value in d.values():
  print(value)

for key, value in d.items():
  print(key, value)

Sets

Insert element into the set

s = set()
s.add(1)

Remove element from the set

s.remove(1)

Check if element exists in the set

if 1 in s:
  print("1 exists")

Different ways of iterating over a set

for i in s:
  print(i)

Remove and return an arbitrary element from the set

s.pop()

Deque

Insert element at the end of the deque

d = deque()
d.append(1)

Insert element at the beginning of the deque

d.appendleft(1)

Peek element at the end of the deque

d[-1]

Peek element at the beginning of the deque

d[0]

Remove element from the end of the deque

d.pop()

Remove element from the beginning of the deque

d.popleft()

Different ways of iterating over a deque

for i in d:
  print(i)

for i in range(len(d)):
  print(d[i])

Priority Queue / Heaps

Heaps (or priority queues) are a data structure that can be used to implement a queue with a priority. By default, the heap is a min heap, but you can change it to a max heap by negating.

import heapq
heap = []

Push the value item onto the heap, maintaining the heap invariant.

heappush(heap, item)

Pop and return the smallest item from the heap, maintaining the heap invariant.

heappop(heap)

Push item on the heap, then pop and return the smallest item from the heap.

heappushpop(heap, item)

Transform list x into a heap, in-place, in linear time.

heapify(x)

Return a list with the n largest elements from the dataset defined by iterable.

nlargest(n, iterable, key=None)

Return a list with the n smallest elements from the dataset defined by iterable.

nsmallest(n, iterable, key=None)

Numbers

divmod

m, n = 12, 4
quotient, remainder = divmod(m,n)
print(quotient) # 3
print(remainder) # 0

Strings

Split string into list of words

s = "hello world"
l = s.split() # ["hello", "world"]

Split string into list of characters

s = "hello world"
l = list(s) # ["h", "e", "l", "l", "o", " ", "w", "o", "r", "l", "d"]

Join list of words into string

l = ["hello", "world"]
s = " ".join(l) # "hello world"
s = ", ".join(l) # "hello, world"

Custom Implementation of Doubly Linked List

Simple double linked list implementation.

class LinkedListNode:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        # Head and Tail are dummy nodes
        self.head = LinkedListNode(0, 0)
        self.tail = LinkedListNode(0, 0)
        # Link head and tail
        self.head.next = self.tail
        self.tail.prev = self.head
    def add(self, node: LinkedListNode) -> None:
        # Add node in the front after head
        head_next = self.head.next
        head_next.prev = node
        self.head.next = node
        node.prev = self.head
        node.next = head_next
    def remove(self, node: LinkedListNode) -> None:
        # Remove node from DLinkedList
        node_next = node.next
        node_prev = node.prev
        node_next.prev = node_prev
        node_prev.next = node_next

Other things that might be useful

Get midpoint of a list

def mid(head: Optional[ListNode]) -> Optional[ListNode]:
  slow, fast = head, head
  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
  return slow

Reverse a list

def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
  if head is None or head.next is None:
    return head
  reversed_list = self.reverse(head.next)
  head.next.next = head
  head.next = None
  return reversed_list

Inorder traversal of a tree (iterative)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        ans = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                root = stack.pop()
                ans.append(root.val)
                root = root.right
        return ans

Common Pitfalls

When an Optional type is used, the way we check for None is different.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def is_balanced(root: Optional[TreeNode]) -> bool:
      if not root: return True # Will not work
      if root is None: return True # Correct check
      left_height = self.height(root.left)
      right_height = self.height(root.right)
      return abs(left_height - right_height) <= 1

Quickselect algo in Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def findKthLargest(start, end, smallest_index):
            pivot = random.randint(start, end)
            i = partition(start, end, pivot)

            if i == smallest_index: return nums[i]
            elif i > smallest_index:
                return findKthLargest(start, i - 1, smallest_index)
            else:
                return findKthLargest(i + 1, end, smallest_index)

        def partition(start, end, pivot):
            swap(pivot, end)

            curr = start
            for i in range(start, end + 1):
                if nums[i] < nums[end]:
                    swap(i, curr)
                    curr += 1

            swap(curr, end)
            return curr

        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]

        return findKthLargest(0, len(nums) - 1, len(nums) - k)

Everything you need to know about Python for LeetCode.