Welcome to my LeetCode repository! Here you will find my solutions and descriptions for LeetCode's 75 most frequently asked questions, along with detailed explanations and notes for each topic.
LeetCode is a platform for preparing technical coding interviews. It provides a wide range of coding problems, ranging from easy to hard, across various topics such as algorithms, data structures, dynamic programming, and more.
Array / String - Notes
1. Merge Strings Alternately - Easy
2. Greatest Common Divisor of Strings - Easy
3. Kids With the Greatest Number of Candies - Easy
4. Can Place Flowers - Easy
5. Reverse Vowels of a String - Easy
6. Reverse Words in a String - Medium
7. Product of Array Except Self - Medium
8. Increasing Triplet Subsequence - Medium
9. String Compression - Medium
Two Pointers - Notes
10. Move Zeroes - Easy
11. Is Subsequence - Easy
12. Container With Most Water - Medium
13. Max Number of K-Sum Pairs - Medium
Sliding Window - Notes
14. Maximum Average Subarray I - Easy
15. Maximum Number of Vowels in a Substring of Given Length - Medium
16. Max Consecutive Ones III - Medium
17. Longest Subarray of 1's After Deleting One Element - Medium
Prefix Sum - Notes
18. Find the Highest Altitude - Easy
19. Find Pivot Index - Easy
Hash Map / Set - Notes
20. Find the Difference of Two Arrays - Easy
21. Unique Number of Occurrences - Easy
22. Determine if Two Strings Are Close - Medium
23. Equal Row and Column Pairs - Medium
Stack - Notes
24. Removing Stars From a String - Medium
25. Asteroid Collision - Medium
26. Decode String - Medium
Queue - Notes
27. Number of Recent Calls - Easy
28. Dota2 Senate - Medium
Linked List - Notes
29. Delete the Middle Node of a Linked List - Medium
30. Odd Even Linked List - Medium
31. Reverse Linked List - Easy
32. Maximum Twin Sum of a Linked List - Medium
Binary Tree - DFS - Notes
33. Maximum Depth of Binary Tree - Easy
34. Leaf-Similar Trees - Easy
35. Count Good Nodes in Binary Tree - Medium
36. Path Sum III - Medium
37. Longest ZigZag Path in a Binary Tree - Medium
38. Lowest Common Ancestor of a Binary Tree - Medium
Binary Tree - BFS - Notes
39. Binary Tree Right Side View - Medium
40. Maximum Level Sum of a Binary Tree - Medium
Binary Search Tree - Notes
41. Search in a Binary Search Tree - Easy
42. Delete Node in a BST - Medium
Graphs - DFS - Notes
43. Keys and Rooms - Medium
44. Number of Provinces - Medium
45. Reorder Routes to Make All Paths Lead to the City Zero - Medium
46. Evaluate Division - Medium
Graphs - BFS - Notes
47. Nearest Exit from Entrance in Maze - Medium
48. Rotting Oranges - Medium
Heap / Priority Queue - Notes
49. Kth Largest Element in an Array - Medium
50. Smallest Number in Infinite Set - Medium
51. Maximum Subsequence Score - Medium
52. Total Cost to Hire K Workers - Medium
Binary Search - Notes
53. Guess Number Higher or Lower - Easy
54. Successful Pairs of Spells and Potions - Medium
55. Find Peak Element - Medium
56. Koko Eating Bananas - Medium
Backtracking - Notes
57. Letter Combinations of a Phone Number - Medium
58. Combination Sum III - Medium
DP - 1D - Notes
59. N-th Tribonacci Number - Easy
60. Min Cost Climbing Stairs - Easy
61. House Robber - Medium
62. Domino and Tromino Tiling - Medium
DP - Multidimensional - Notes
63. Unique Paths - Medium
64. Longest Common Subsequence - Medium
65. Best Time to Buy and Sell Stock with Transaction Fee - Medium
66. Edit Distance - Medium
Bit Manipulation - Notes
67. Counting Bits - Easy
68. Single Number - Easy
69. Minimum Flips to Make a OR b Equal to c - Medium
Trie - Notes
70. Implement Trie (Prefix Tree) - Medium
71. Search Suggestions System - Medium
Intervals - Notes
72. Non-overlapping Intervals - Medium
73. Minimum Number of Arrows to Burst Balloons - Medium
Monotonic Stack - Notes
74. Daily Temperatures - Medium
75. Online Stock Span - Medium
Each solution is accompanied by problem descriptions and brief notes explaining the approach. These notes aim to provide insights into various techniques and algorithms used to solve each problem.
Feel free to explore the solutions and notes. If you have any questions or suggestions, don't hesitate to reach out! Happy coding! 🚀
Below are further notes on tips to approach each category of problem:
- Split a string -
string_name.split() - Join a list into a string -
''.join(list_name) - Reverse a list -
list_name[::-1] - Positive & Negative Infinity -
float('inf')&float('-inf') - List comprehension -
[i * 3 for i in list_name] - Sort a list -
list_name.sort()
- Have pointers starting at start and end of the list
left, right = 0, len(list_name) - 1while left < right:
- Have a fast and slow pointer
slow = 0for fast in range(len(list_name)):
- For a window of size 'k', calculate requested value for the initial window
for i in range(k, len(list_name)):- remove first element
list_name[i-k] - add the next element
list_name[i] - recalculate requested value
- remove first element
- Often used with a postfix sum
preSum, postSum = 0, sum(list_name) for i in range(len(list_name)):- preSum stores sum of values up to i:
preSum += list_name[i] - postSum stores sum of values from i to the end of the list:
postSum -= list_name[i]
- preSum stores sum of values up to i:
-
Unordered data structures with unique elements.
-
Adding elements to a dictionary:
for i in list_name: if i not in my_dict: my_dict[i] = 1 else: my_dict[i] += 1
or defaultdict has default value = 0
from collections import defaultdict my_dict = defaultdict() for i in list_name my_dict[i] += 1
-
Values in dictionary -
my_dict.values() -
Different values between sets -
set1 - set2
- Data structure where it is quick to append and pop elements to and from the top of the stack (end of the list in python).
- Append element to top -
stack.append(i) - Remove top element -
stack.pop()
- Data structure where it is quick to add elements to the back of the queue and remove elements from the front.
- Create a queue:
from collections import dequequeue_name = deque() - Remove element from front -
queue_name.popleft() - Add element to back -
queue_name.append(i)
-
Data structure with a value and pointer to the next element in the list
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
-
Reverse a linked list:
while current: # traverse linked list next_node = current.next # store next node current.next = new_list # attach current to front of reversed list new_list = current # update new front of reversed list to current current = next_node # stored next node becomes current node
-
Midpoint of linked list - use two pointers and have fast pointer move twice as fast as slow, so when it's at the end of the list, slow is at the midpoint
while fast.next and fast.next.next: slow = slow.next fast = fast.next.next
-
Binary Tree is a data structure where each node has a value and at most two children, left and right child, and the top node is known as the root
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right e.g. 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 / 10
-
Depth First Search involves searching by traversing the tree in a depthward motion, starting from the root and visiting as far as possible along each branch before backtracking
-
Solve DFS questions recursively with general solution:
ans = [] # initialise answer data structure def dfs(root, value): # takes a root node and some value we are trying to calculate if root is None: # deal with reaching end of the branch return default # usually returning 0 or depth # Calculations involving ans or to get new value ans.append(value) # run recursively for left and right children, checking all the way to the left first return dfs(root.left, value) + dfs(root.right, value) dfs(root, value) return ans
-
Breadth First Search explores the neighbour nodes at the present depth before moving on to the nodes at the next depth level
-
Solve BFS questions recursively with general solution:
ans = [] # initialise answer data structure def bfs(root, ans, value): # takes a root node and some value we are trying to calculate if root is None: # deal with reaching end of the branch return # usually just return nothing # Calculations involving ans or to get new value ans.append(root.val) # run recursively for right and left children. # need to pass ans as variable to maintain a shared state across all recursive calls to bfs bfs(root.right, ans, value + 1) bfs(root.left, ans, value + 1) bfs(root, value) return ans
-
Different questions could require doing the calculations before, between or after the recursive bfs call
- A binary search tree is a binary tree with the additional properties that:
- The value of all nodes in the left subtree of a node is less than the value of the node
- The value of all nodes in the right subtree of a node is greater than the value of the node
- The left and right subtrees of each node are also binary search trees
e.g. 4 / \ 2 6 / \ \ 1 3 7
- A graph is a data structure that consists of a set of nodes (vertices) and a set of edges connecting these nodes
- General solution:
- Start with an initial node (usually provided in the problem statement) and push it onto the stack.
- While the stack is not empty, pop a node and process it.
- For each neighbor of the popped node that hasn't been visited yet, mark it as visited, push it onto the stack, and recursively call the DFS function.
- Continue until the stack is empty or until you reach the desired condition specified in the problem.
- Don't need a stack if all edges are stored in another data structure like a matrix or dictionary
visited = set() # can keep track of visited nodes using a set # check if nodes are connected by calling dfs on all connections to the start node def dfs(i): if i in visited: return visited.add(i) for j in range(n): if connections[i][j]: # connections stores data about edges between nodes dfs(j)
- Start with an initial node (usually provided in the problem statement) and enqueue it into the queue
- While the queue is not empty, dequeue a node and process it
- For each neighbor of the dequeued node that hasn't been visited yet, mark it as visited, enqueue it into the queue, and update any necessary information (e.g., distances).
- Continue until the queue is empty or until you reach the desired condition specified in the problem.
- A heap, often implemented as a priority queue is a data structure where the minimum / maximum element is always at the root, depending on if you want a min or max heap. Default is min-heap.
- Import heap module -
import heapq - Turn list into a min-heap -
heapq.heapify(list_name) - Pop min element of the heap -
heapq.heappop(heap_name) - Add an element to a heap -
heapq.heappush(heap_name, number)
- Achieves O(logn) complexity by halving the number of elements to search with each step
- For a sorted list, simple binary search uses two pointers:
l, r = 0 , len(list_name)-1 while l < r: mid = l+(r-l)//2 if list_name[mid] > target_value: r = mid else: l = mid + 1 return l
- Backtracking is used to incrementally build a candidate solution, exploring various choices at each step. When a choice leads to a dead-end or violates a constraint, the algorithm backtracks to the previous decision point and explores other options.
- A general solution involves:
- A base case or termination condition that indicates when a valid solution has been found or when the search should stop
- Recursive calls to explore the decision space, making choices at each step and recursively exploring subsequent choices
- Caching improves runtime if recursive calls are repeated:
from functools import lru_cache @lru_cache
-
Dynamic programming is an algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems and solving each subproblem only once.
-
Buttom-up approach (tabulation):
- In this approach, the problem is solved iteratively from the smallest subproblems to the largest, with solutions stored in a table (usually implemented as a dictionary or a list)
- The algorithm starts by solving the smallest subproblems and gradually builds up to larger subproblems, reusing solutions to smaller subproblems as needed
- In some cases, it's possible to perform tabulation in-place, meaning that the solution table can overwrite the input data structure without requiring additional memory
- Need to hard code in the solutions to most simple subproblems
-
Top-down approach (memoization):
- The solutions to subproblems stored in a memoization table (usually implemented as a cache
@lru_cache) - Before solving a subproblem, the algorithm checks if the solution is already known from previous computations. If so, it retrieves the solution from the memoization table instead of recomputing it
- The solutions to subproblems stored in a memoization table (usually implemented as a cache
- Multidimensional Dynamic Programming is very similar to 1D tabulation method, except need to use a multidemensional list to store subproblem solutions:
grid = [[0] * n for _ in range(m)] - Need to hard code in the solutions to most simple subproblems:
grid[0] = [1 for _ in range(n)]
- These problems often require efficient manipulation of binary digits (bits) to solve a variety of computational tasks
- Bitwise operations:
- Bitwise AND -
a&b - Bitwise OR -
a|b - Bitwise XOR -
a^b - Bitwise NOT -
~a - Bitwise shift right and left -
a >>= 1anda <<= 2, where numbers are amount of shifts- e.g. 101 (5) would become 10 (2) and 10100 (20)
- Dividing / multiplying a number by 2 is the same as shifting the number's bits to the left / right
- For even number n:
sum_bits(n) = sum_bits(n/2)
- For even number n:
- Bitwise AND -
-
A trie or prefix tree is a data structure which stores strings one letter per node, with its children as all the potential next letters from stored words
class Trie: def __init__(self): self.root = {} def insert(self, word: str) -> None: cur = self.root for i in word: if i not in cur: cur[i] = {} cur = cur[i]
-
Intervals are often represented using pairs of numbers (start, end) which includes all values greater than start and less than end
-
Interval problems often require using a pointer to keep track of the end of the interval and iterating over the sorted list of intervals
intervals = sorted(intervals, key=lambda x: x[0]) res = 0 end_pointer = float('-inf') for start, end in intervals: if start > end_pointer: res += 1 end_pointer = end elif end < end_pointer: end_pointer = end
- A monotonic stack is a data structure used to efficiently solve problems related to finding the next smaller or larger element in a sequence. It maintains a stack where the elements are either strictly increasing or strictly decreasing.
- Implemented by using storing the indices of values in the sequence in a stack, and popping indices from the stack if current element is larger than the indices at the top of the stack
for i in range(len(sequence)): while stack and sequence[i] > sequence[stack[-1]]: indices = stack.pop() result[indices] = i - indices stack.append(i)