Neetcode

algorithm cheetsheet in Python3 summarised by data types

Data Structure Implementations

• HashMap
• Set
• Deque
• Heap
• LRU Cache
• MRU Cache
• LFU Cache
• Priority Cache
• Message Queue Scheduled
• Rate Limiter

Int

• Greedy

  • Get Prime Factors

String

• Math Calculation O(1) time

  count combination

  • Splits Count Equal Num Char

• Greedy O(N) time - rolling update with condition

  substring(shortest, longest, len, min, max) -> greedy, sliding window

  • Substring Longest Palindromic palindromic
  • Combination Validate Parentheses left_min, left_max

• Greedy & Hashmap O(C) space - index/count related condition

  string(index, count, last, match) -> Hashmap

  • Group by Anagram {sorted_string: list}
  • Substring Longest with Char Replacement {char: count}
  • Substring Longest without Repeating Characters {char: last}, seen[c] >= i
  • Substring Check Target Anagram {char: count}
  • Splits Count Equal Unique Chars {char: first}, {char: last}
  • Splits Char Unique Part {char: last}

• 1D Dynamic Programming O(N) time, O(1 or N) space - multiple relations to between n-x and n

  subsequence, combination(count, match, min, max) -> dynamic programming

  • Splits Count by Dict if match_condition: dp[n] += dp[n-1] or dp[n-2]
  • Splits Count Match by Dict dp[i] = True if any(dp[n-len(w)] and s[i-len(w):i] == w)

• 2D Dynamic Programming O(M*N) time, O(M or N or M*N) space - multiple relations and multiple strings

  two subsequences, subsequence match -> 2d dynamic programming

  • Subsequence Count Longest Common of Two Strings
  • Subsequence Count Match Another String

• Backtracking or DFS O(N*O^L) time - conditional generation or search

  combination(generate) -> backtracking, combination(dictionary) -> DFS

  • Combination Generate Parentheses
  • Combination Dictionary Search Match Sum

1D Array

• Math Calculation O(1) time

• Binary Search O(LogN) time - search until match or left-right condition

  sorted search, search peak -> binary search

  • Rotated Sorted Array Search
  • Rotated Sorted Array Min target is converged boundary
  • Search Element Peak left on uphill, right on downhill

• Binary Search + Greedy

  • Subsequence Fixed Size Max Min Gap binary search on possible gap

• Greedy O(N) time - rolling update on condition

  subarray(max, min, longest, except self) -> greedy

  • Subarray Max Product rolling vals, min, max
  • Subarray Min Size Sum rolling res, sliding window
  • Search Min Max Diff After Operation all possible cases, sort pair iterate
  • Subarray Longest Consecutive consecutive, set
  • Subarray Product Except Self async except-self product
  • Subarray Addition Multiple lazy rolling addition
  • Consecutive Int Missing sum diff
  • Triplet Check Increasing anchor if elif else

• Greedy + Sliding/Two-Pointer Window O(1) space - forward and backward

  subarray(area, remove, longest, shortest) -> sliding window

  • Subarray Max Containable Area shrinking width updating min height
  • Subarray Total Patch Containable update the bar on the smaller side
  • Subarray Shortest Remove to Sort shortest window
  • Subarray Longest Sum Within K
  • Triplets Count Increasing Sum Within K
  • Sorted Array Two Indexes Sum to K

• Greedy + Implicit BFS

  • Subsequence Min Jumps
  • Circular Index Cover Cost

• Greedy & Hashmap O(N) space - index/count related condition

  array(index, count, last) -> Hashmap

  • Search Two Indexes Sum to K {match_condition: index}
  • Subarray Count Sum to K {sum: count}``sum[i:j] = sum[:j] - sum[:i]
  • Subarray Count Sum Divisible by K {sum%k: count}

• Greedy & Stack O(N) time, O(K) space

  stream sliding window max, rectangle area -> stack

  • Stream Sliding Window Maxes [index of max until i]
  • Subarray Max Area Rectangle [(left, height)]

• Greedy & Heap O(K*LogN or N*LogK) time, O(N) space - rank, sort

  stream k, kth, median, subgroups consecutive -> heap

  • Search K Elements Closest to Origin
  • Stream Find Median min max heaps
  • Stream Sliding Window Median min max heaps, lazy removal
  • Subgroups Fixed Size Check Consecutive

• Greedy & Combinations O(N^2) time

  • (Triplet) Search Three Indexes Sum to K negative positive combinations

• 1D Dynamic Programming O(N) time, O(N or 1) space - multiple relations to between n-x and n

  subsequence or combination(fewest, sum to, longest) -> dynamic programming

  • Combination Count Sum To K dp[i] += dp[i-coin]
  • Subsequence Longest Increasing dp[j] = max(dp[i]+1 if nums[i] < nums[j])
  • Two Arrays Min Path Cost from_red, from_blue dp

• 1D Dynamic Programming + Cached DFS

  • Combination Fewest Elements Sum to K dp[a] = min(dp[a], 1 + dp[a - c])

• 2D Dynamic Programming

  subsequence(average)

  • Subsequence Search Equal Average dp[i] |= {s+a for s in dp[i+1] if s+a <= HALF}

• Backtracking, DFS O(N*O^L) time - conditional combinations

  combination(generate) -> backtracking

  • Combination Generate Sum to K

2D Array

• Binary Search O(LogM*LogN) time

  sorted search, search peak -> binary search

  • Sorted Matrix Search
  • Search Element Peak

• Greedy & Set O(M*N) time, O(1) space

  • Validate Soduku

• BFS O(M*N) time, O(M*N) space - shortest path

  shortest path, shortest distance, edge areas -> BFS

  • Search Shortest Path
  • Search Shortest Spread
  • Update Shortest Distance
  • Update by Area Surrounded

• 2D Dynamic Programming or cached DFS O(M*N) time, O(M*N) space

  count longest path

  • Search Longest Path Increasing

• DFS O(M*N or M*N*O^L) time, O(O^L) space - known target

  longest path, target sequence, edge areas -> DFS

  • Search Longest Path
  • Search Sequence
  • Update by Area Surrounded

Bit

n << 1 <=> n * 2 n >> 1 <=> n // 2 n & 1 <=> n % 2

• Bit Iteration, Shift O(1) time

  range(32) or range(31, -1, -1)

  • Reverse Bits
  • Bitwise AND non zero
  • Divide by Deduction
  • Min Operation to Zero

• As an Array

  bit base(conversion, calculation)

  • Add Negative Binary
  • Convert to Negative Base

Tree

• Recursion O(N) time, O(N) space

  • Invert
  • Binary Search Tree Validate

• BFS O(N) time, O(N) space

  • Search Rightest Nodes

• DFS or Backtracking O(N) time, O(N) space

  • Path Sum Max

Linked List

• Simple Forward O(N) time, O(1) space

  • Reverse
  • Add Two Numbers

• Fast Slow Pointers O(N) time, O(1) space

  • Reorder from Mid Point
  • Cycle Detection

Graph

• DSU(Root Union) O(C) time, O(N) space {node: root}

  undirected set

  • Undirected Stream Largest Set
  • Undirected Remove Cycle

• Topological Sort O(C) time, O(C+N) space {up: [downs]}, [up_counts]

  directed cycle, pathes

  • Directed Detect Cycle
  • Directed Search Pathes All Nodes

• DFS O(N^2) time {node: [connection]}

  matrix count groups

  • (Undirected) Matrix Count Groups

Geometry

• Triangle

  • Check Point in Triangle