A comprehensive collection of coding patterns and tricks for the NeetCode 150 problems.
Last Updated: 1/24/2026
- Arrays & Hashing (9 problems)
- Two Pointers (5 problems)
- Stack (6 problems)
- Binary Search (7 problems)
- Sliding Window (6 problems)
- Linked List (11 problems)
- Trees (15 problems)
- Tries (3 problems)
- Backtracking (10 problems)
- Heap / Priority Queue (7 problems)
- Graphs (13 problems)
- 1-D Dynamic Programming (12 problems)
- Intervals (6 problems)
- Greedy (8 problems)
- Advanced Graphs (6 problems)
- 2-D Dynamic Programming (11 problems)
- Bit Manipulation (7 problems)
- Math & Geometry (8 problems)
Problem: Contains Duplicate
Description:
Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.
Tip
💡 Trick/Pattern:
Use a hashset to track seen elements. Iterate through the array and check if the current element exists in the set. If yes, return true (duplicate found). Otherwise, add it to the set and continue.
⬆️ Back to Top | 📑 Table of Contents
Problem: Valid Anagram
Description:
Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Tip
💡 Trick/Pattern:
Use a hashmap to count character frequencies for both strings. Create count maps for s and t, then compare them. If the frequency maps are identical, the strings are anagrams.
⬆️ Back to Top | 📑 Table of Contents
Problem: Two Sum
Description:
Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.
You may assume that every input has exactly one pair of indices i and j that satisfy the condition.
Return the answer with the smaller index first.
Tip
💡 Trick/Pattern:
Use a hashmap, store the index of each element in the map. If target - nums[i] exist in map return [map[target - nums[i]], i]
Code:
mp = defaultdict(int)
for i in range(len(nums)):
if target - nums[i] in mp:
return [mp[target - nums[i]], i]
else:
mp[nums[i]] = i
return []⬆️ Back to Top | 📑 Table of Contents
Problem: Group Anagrams
Description:
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Tip
💡 Trick/Pattern:
Use a count array as the key to store the strings in a hashmap.
Code:
res = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
res[tuple(count)].append(s)
return list(res.values())⬆️ Back to Top | 📑 Table of Contents
Problem: Top K Frequent Elements
Description:
Given an integer array nums and an integer k, return the k most frequent elements within the array.
The test cases are generated such that the answer is always unique.
You may return the output in any order.
Tip
💡 Trick/Pattern:
Use a minHeap to store the k frequent elements, if the length of heap exceeds k pop from the heap.
Code:
mp = defaultdict(int)
for n in nums:
mp[n] += 1
heap = []
for key in mp:
heapq.heappush(heap,(mp[key], key))
if len(heap) > k:
heapq.heappop(heap)
ans = []
for h in heap:
ans.append(h[1])
return ans⬆️ Back to Top | 📑 Table of Contents
Problem: Encode and Decode Strings
Description:
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Tip
💡 Trick/Pattern:
Use length-prefix encoding: for each string, prepend its length followed by a delimiter (e.g., "4#word"). This handles strings containing any characters including the delimiter itself. Decode by reading the length, then extracting that many characters.
⬆️ Back to Top | 📑 Table of Contents
Problem: Products of Array Except Self
Description:
Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
Each product is guaranteed to fit in a 32-bit integer.
Tip
💡 Trick/Pattern:
Use prefix array to precompute left and right product arrays res[i] = left[i] * right[i]
Code:
left = [1] * len(nums)
right = [1] * len(nums)
for i in range(1,len(nums)):
left[i] = left[i-1] * nums[i-1]
for i in range(len(nums)-2,-1,-1):
right[i] = right[i+1] * nums[i+1]
res = [0] * len(nums)
for i in range(len(nums)):
res[i] = left[i] * right[i]
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Valid Sudoku
Description:
You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:
Each row must contain the digits 1-9 without duplicates. Each column must contain the digits 1-9 without duplicates. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates. Return true if the Sudoku board is valid, otherwise return false
Tip
💡 Trick/Pattern:
Use three hashsets: one for rows, one for columns, and one for 3×3 sub-boxes. For each cell, check if the value already exists in its row set, column set, or box set. The box index can be calculated as (r//3, c//3).
⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Consecutive Sequence
Description:
Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.
A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.
Tip
💡 Trick/Pattern:
Use a hashset and iterate over it, check if left neighbor (n - 1) exists in set, if it doesn't it's the start of the sequence and use a while loop to check the length of it.
Code:
s = set(nums)
maxLen = 0
for n in s:
length = 0
if (n-1) not in s:
while (n + length) in s:
length += 1
maxLen = max(maxLen, length)
return maxLen⬆️ Back to Top | 📑 Table of Contents
Problem: Valid Palindrome
Description:
Given a string s, return true if it is a palindrome, otherwise return false.
A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Tip
💡 Trick/Pattern:
Use two pointers i = 0, j = len(s) - 1. While i < j run a loop, if s[i] != s[j] return False, else update pointers i += 1, j -= 1.
⬆️ Back to Top | 📑 Table of Contents
Problem: Two Integer Sum II
Description:
Given an array of integers numbers that is sorted in non-decreasing order.
Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.
There will always be exactly one valid solution.
Your solution must use O(1) additional space.
Tip
💡 Trick/Pattern:
Use two pointers, i=0 and j=len(nums)-1. While i < j, if nums[i] + nums[j] == target return the indices, else if the sum is greater than target reduce j pointer by 1, else increase i pointer by 1.
Code:
i,j = 0, len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
elif numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return []⬆️ Back to Top | 📑 Table of Contents
Problem: 3Sum
Description:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.
The output should not contain any duplicate triplets. You may return the output and the triplets in any order.
Tip
💡 Trick/Pattern:
Sort the nums array and use three pointers, i remains constant while j and k move to find the target sum (similar to two sum sorted array), if the sum is found, update the j pointer by 1 while the nums[j] == nums[j-1] to remove duplicates.
Code:
nums.sort()
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
j = i + 1
k = len(nums) - 1
while j < k:
if nums[i] + nums[j] + nums[k] == 0:
res.append([nums[i],nums[j],nums[k]])
j += 1
while j < k and nums[j] == nums[j-1]:
j += 1
elif nums[i] + nums[j] + nums[k] > 0:
k -= 1
else:
j += 1
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Container With Most Water
Description:
You are given an integer array heights where heights[i] represents the height of the ith bar.
You may choose any two bars to form a container. Return the maximum amount of water a container can store.
Tip
💡 Trick/Pattern:
Use two pointers, i=0 and j=len(heights)-1, while i < j, find the maximum in each iteration, update the i and j pointers of the side which has the lower value.
Code:
i = 0
j = len(heights) - 1
maxi = 0
while i < j:
maxi = max(maxi, (j - i) * min(heights[i],heights[j]))
if heights[i] < heights[j]:
i += 1
else:
j -= 1
return maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Trapping Rain Water
Description:
You are given an array of non-negative integers height which represent an elevation map. Each value height[i] represents the height of a bar, which has a width of 1.
Return the maximum area of water that can be trapped between the bars.
Tip
💡 Trick/Pattern:
Use two pointers, i=0 and j=len(heights)-1, while i < j, find the maximum from the left and right directions. The water is updated using the side with the lower value.
Code:
i,j = 0, len(height) - 1
maxL, maxR = 0,0
water = 0
while i < j:
maxL = max(maxL, height[i])
maxR = max(maxR, height[j])
if maxL < maxR:
water += maxL - height[i]
i += 1
else:
water += maxR - height[j]
j -= 1
return water⬆️ Back to Top | 📑 Table of Contents
Problem: Valid Parentheses
Description:
You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.
The input string s is valid if and only if:
Every open bracket is closed by the same type of close bracket. Open brackets are closed in the correct order. Every close bracket has a corresponding open bracket of the same type. Return true if s is a valid string, and false otherwise.
Tip
💡 Trick/Pattern:
Use a stack, if it's a open parenthesis push to stack, if is closing parenthesis check if the top of the stack makes a pair, if yes pop and continue, else return False. At the end check if stack is empty or not.
⬆️ Back to Top | 📑 Table of Contents
Problem: Minimum Stack
Description:
Design a stack class that supports the push, pop, top, and getMin operations.
MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack.
Tip
💡 Trick/Pattern:
The top of the minStack holds the minimum value, Append the minimum of the top of the stack and the current value when pushing to minStack.
Code:
def push(self, val: int) -> None:
self.stack.append(val)
if self.minStack:
self.minStack.append(min(self.minStack[-1],val))
else:
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()⬆️ Back to Top | 📑 Table of Contents
Problem: Evaluate Reverse Polish Notation
Description:
You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.
Return the integer that represents the evaluation of the expression.
The operands may be integers or the results of other operations. The operators include '+', '-', '*', and '/'. Assume that division between integers always truncates toward zero.
Tip
💡 Trick/Pattern:
If the current char is integer push it to the stack, if it's an operator pop twice from the stack and append the result of (b (operator) a) onto the stack. At the end return top of the stack.
⬆️ Back to Top | 📑 Table of Contents
Problem: Daily Temperatures
Description:
You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.
Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.
Tip
💡 Trick/Pattern:
Use a monotonically decreasing stack. If the current temp is greater than stack top, pop from the stack and set res[stackIdx] = i - stackIdx. At the end of each iteration append the current index and temperature.
Code:
stack = []
res = [0] * len(temperatures)
for i in range(len(temperatures)):
while stack and stack[-1][1] < temperatures[i]:
idx, t = stack.pop()
res[idx] = i - idx
stack.append([i, temperatures[i]])
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Car Fleet
Description:
There are n cars traveling to the same destination on a one-lane highway.
You are given two arrays of integers position and speed, both of length n.
position[i] is the position of the ith car (in miles) speed[i] is the speed of the ith car (in miles per hour) The destination is at position target miles.
A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.
A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.
If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.
Return the number of different car fleets that will arrive at the destination.
Tip
💡 Trick/Pattern:
Sort the position and speed pairs in non-increasing order. If the time required by current pair is less than the time on stack top, don't append the time to stack, else append the current time onto the stack.
Code:
stack = []
pair = []
for i in range(len(position)):
pair.append([position[i],speed[i]])
pair.sort(reverse=True)
for p,s in pair:
time = (target - p) / s
if stack and stack[-1] >= time:
continue
stack.append(time)
return len(stack)⬆️ Back to Top | 📑 Table of Contents
Problem: Largest Rectangle In Histogram
Description:
You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.
Return the area of the largest rectangle that can be formed among the bars.
Tip
💡 Trick/Pattern:
Use a monotonically increasing stack. If stack[-1][1] > heights[i], pop from the stack and find maximum of stackHeight * (i - stackIdx), use a start variable to keep track of start of the sequence. At the end append [start, heights[i]] to the stack. If the stack exists after all the operations find the maximum from h * (len(heights) - i)
Code:
stack = []
maxi = 0
for i in range(len(heights)):
start = i
while stack and stack[-1][1] > heights[i]:
idx, h = stack.pop()
maxi = max(maxi, h * (i - idx))
start = idx
stack.append([start, heights[i]])
for i,h in stack:
maxi = max(maxi, h * (len(heights) - i))
return maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Binary Search
Description:
You are given an array of distinct integers nums, sorted in ascending order, and an integer target.
Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1
Tip
💡 Trick/Pattern:
Use binary search with two pointers i and j. While i ≤ j, calculate mid = (i+j)//2. If nums[mid] == target, return mid. If nums[mid] < target, search right half (i = mid+1). Otherwise, search left half (j = mid-1).
⬆️ Back to Top | 📑 Table of Contents
Problem: Search a 2D Matrix
Description:
You are given an m x n 2-D integer array matrix and an integer target.
Each row in matrix is sorted in non-decreasing order. The first integer of every row is greater than the last integer of the previous row. Return true if target exists within matrix or false otherwise.
Tip
💡 Trick/Pattern:
Apply binary search twice: first on rows to find the correct row (check if target is between first and last element), then binary search on that row to find the target column.
⬆️ Back to Top | 📑 Table of Contents
Problem: Koko Eating Bananas
Description:
You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas.
You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not eat from another pile in the same hour.
Return the minimum integer k such that you can eat all the bananas within h hours.
Tip
💡 Trick/Pattern:
Apply binary search on answers, the search space is 1 and max(piles).
Code:
def eat(k):
time = 0
for p in piles:
time += math.ceil(p / k)
return time <= h
i,j = 1,max(piles)
time = 1
while i <= j:
mid = (i + j) // 2
if eat(mid):
j = mid - 1
time = mid
else:
i = mid + 1
return time⬆️ Back to Top | 📑 Table of Contents
Problem: Find Minimum in Rotated Sorted Array
Description:
You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:
[3,4,5,6,1,2] if it was rotated 4 times. [1,2,3,4,5,6] if it was rotated 6 times. Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.
Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.
Tip
💡 Trick/Pattern:
Use binary search to find it in O(logn) time, While i < j find the sorted side by using nums[mid] > nums[j], at the end return nums[i].
Code:
i = 0
j = len(nums) - 1
while i < j:
mid = (i + j) // 2
if nums[mid] > nums[j]:
i = mid + 1
else:
j = mid
return nums[i]⬆️ Back to Top | 📑 Table of Contents
Problem: Search in Rotated Sorted Array
Description:
You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:
[3,4,5,6,1,2] if it was rotated 4 times. [1,2,3,4,5,6] if it was rotated 6 times. Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.
You may assume all elements in the sorted rotated array nums are unique
Tip
💡 Trick/Pattern:
Try to find the sorted side by using nums[mid] >= nums[i]. In the sorted side check if target exists in that range. If number found return mid.
Code:
i = 0
j = len(nums) - 1
while i <= j:
mid = (i + j) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[i]:
if nums[i] <= target and target < nums[mid]:
j = mid - 1
else:
i = mid + 1
else:
if nums[j] >= target and target > nums[mid]:
i = mid + 1
else:
j = mid - 1
return -1⬆️ Back to Top | 📑 Table of Contents
Problem: Time Based Key-Value Store
Description:
Implement a time-based key-value data structure that supports:
Storing multiple values for the same key at specified time stamps Retrieving the key's value at a specified timestamp Implement the TimeMap class:
TimeMap() Initializes the object. void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. String get(String key, int timestamp) Returns the most recent value of key if set was previously called on it and the most recent timestamp for that key prev_timestamp is less than or equal to the given timestamp (prev_timestamp <= timestamp). If there are no values, it returns "".
Tip
💡 Trick/Pattern:
The nature of timestamp ensures the array is sorted, so just apply binary search.
⬆️ Back to Top | 📑 Table of Contents
Problem: Median of Two Sorted Arrays
Description:
You are given two integer arrays nums1 and nums2 of size m and n respectively, where each is sorted in ascending order. Return the median value among all elements of the two arrays.
Tip
💡 Trick/Pattern:
Since both arrays are already sorted, the median can be found by binary searching a partition point so that the left halves contain exactly half the elements and all left values are ≤ all right values.
Code:
A,B = nums1, nums2
if len(A) > len(B):
A,B = B,A
total = len(A) + len(B)
half = total // 2
i = 0
j = len(A) - 1
while True:
mid = (i + j) // 2
mid2 = half - mid - 2
Aleft = A[mid] if mid >= 0 else -1e9
Aright = A[mid + 1] if (mid + 1) < len(A) else 1e9
Bleft = B[mid2] if mid2 >= 0 else -1e9
Bright = B[mid2 + 1] if (mid2 + 1) < len(B) else 1e9
if Aleft <= Bright and Bleft <= Aright:
if total % 2:
return min(Aright, Bright)
else:
return (max(Bleft,Aleft) + min(Aright,Bright)) / 2
elif Aleft > Bright:
j = mid - 1
else:
i = mid + 1⬆️ Back to Top | 📑 Table of Contents
Problem: Best Time to Buy and Sell Stock
Description:
You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.
You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.
Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.
Tip
💡 Trick/Pattern:
Apply sliding window, if prices[r] < prices[l], reset l = r. Find maximum of prices[r] - prices[l] in each iteration.
Code:
maxi = 0
l = 0
for r in range(len(prices)):
maxi = max(maxi, prices[r] - prices[l])
if prices[r] < prices[l]:
l = r
return maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Substring Without Repeating Characters
Description:
Given a string s, find the length of the longest substring 62BF without duplicate characters.
A substring is a contiguous sequence of characters within a string.
Tip
💡 Trick/Pattern:
Use a set to maintain the window contents, if s[r] in window remove s[l] while s[r] in window. Add s[r] to the window and find the max window length each iteration.
Code:
maxi = 0
window = set()
l = 0
for r in range(len(s)):
while s[r] in window:
window.remove(s[l])
l += 1
window.add(s[r])
maxi = max(maxi, r - l + 1)
return maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Repeating Character Replacement
Description:
You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.
After performing at most k replacements, return the length of the longest substring which contains only one distinct character.
Tip
💡 Trick/Pattern:
Use a hashmap to maintain the window contents, maintain the max Frequency of the window, while window length - max Frequency > k, reduce the window length. At the end find the maximum window length.
Code:
window = defaultdict(int)
maxi = 0
l = 0
maxF = 0
for r in range(len(s)):
window[s[r]] += 1
maxF = max(maxF, window[s[r]])
while (r - l + 1) - maxF > k:
window[s[l]] -= 1
l += 1
maxi = max(maxi, r - l + 1)
return maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Permutation in String
Description:
You are given two strings s1 and s2.
Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true.
Both strings only contain lowercase letters.
Tip
💡 Trick/Pattern:
Use a fixed size sliding window and two hashmaps to find if the permutation exists in the string.
Code:
if len(s1) > len(s2):
return False
s1Count , s2Count = defaultdict(int), defaultdict(int)
for s in s1:
s1Count[s] += 1
l = 0
for r in range(len(s1)):
s2Count[s2[r]] += 1
for r in range(len(s1),len(s2)):
if s1Count == s2Count:
return True
s2Count[s2[r]] += 1
s2Count[s2[l]] -= 1
if s2Count[s2[l]] == 0:
del s2Count[s2[l]]
l += 1
return s1Count == s2Count⬆️ Back to Top | 📑 Table of Contents
Problem: Minimum Window Substring
Description:
Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".
You may assume that the correct output is always unique.
Tip
💡 Trick/Pattern:
Use two hashmaps one for window and one for t string, keep track of the amount of chars match the t string, if matches == need, keep reducing the window length while matches == need. Return the window at the end.
Code:
if len(t) > len(s):
return ""
tCount, window = defaultdict(int), defaultdict(int)
matches, need = 0,0
res, resLen = [-1,-1], 1e9
for c in t:
tCount[c] += 1
l = 0
need = len(tCount)
for r in range(len(s)):
window[s[r]] += 1
if s[r] in tCount and window[s[r]] == tCount[s[r]]:
matches += 1
while matches == need:
if (r - l + 1) < resLen:
resLen = r - l + 1
res = [l,r]
window[s[l]] -= 1
if s[l] in tCount and window[s[l]] < tCount[s[l]]:
matches -= 1
l += 1
l,r = res
return s[l:r + 1] if resLen != 1e9 else ""⬆️ Back to Top | 📑 Table of Contents
Problem: Sliding Window Maximum
Description:
You are given an array of integers nums and an integer k. There is a sliding window of size k that starts at the left edge of the array. The window slides one position to the right until it reaches the right edge of the array.
Return a list that contains the maximum element in the window at each step.
Tip
💡 Trick/Pattern:
Maintain a deque that stores indices in decreasing order so the front always represents the maximum of the current window.
Code:
q = deque()
res = []
l = 0
for r in range(len(nums)):
while q and nums[q[-1]] < nums[r]:
q.pop()
q.append(r)
if l > q[0]:
q.popleft()
if r + 1 >= k:
res.append(nums[q[0]])
l += 1
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Reverse Linked List
Description:
Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.
Tip
💡 Trick/Pattern:
Use three pointers curr, prev, next to reverse the list.
⬆️ Back to Top | 📑 Table of Contents
Problem: Merge Two Sorted Linked Lists
Description:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted linked list and return the head of the new sorted linked list.
The new list should be made up of nodes from list1 and list2.
Tip
💡 Trick/Pattern:
Use a dummy node and set next pointer to the node of the list with lower value.
⬆️ Back to Top | 📑 Table of Contents
Problem: Linked List Cycle Detection
Description:
Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.
There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.
Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.
Tip
💡 Trick/Pattern:
Use Floyd's Cycle-Finding Algorithm. Use slow and fast pointers, fast moves twice as fast as slow pointer. slow = slow.next, fast = fast.next.next. If slow == fast: return True
⬆️ Back to Top | 📑 Table of Contents
Problem: Reorder Linked List
Description:
You are given the head of a singly linked-list.
The positions of a linked list of length = 7 for example, can intially be represented as:
[0, 1, 2, 3, 4, 5, 6]
Reorder the nodes of the linked list to be in the following order:
[0, 6, 1, 5, 2, 4, 3]
Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:
[0, n-1, 1, n-2, 2, n-3, ...]
Tip
💡 Trick/Pattern:
Use slow/fast to find middle, reverse the second half, then merge both halves alternately.
Code:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
curr = slow.next
slow.next = None
prev = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
first = head
second = prev
while first and second:
first_next = first.next
second_next = second.next
first.next = second
second.next = first_next
first = first_next
second = second_next⬆️ Back to Top | 📑 Table of Contents
Problem: Remove Node From End of Linked List
Description:
You are given the beginning of a linked list head, and an integer n.
Remove the nth node from the end of the list and return the beginning of the list.
Tip
💡 Trick/Pattern:
Traverse over the array to find the length, traverse to n-k and remove the node.
⬆️ Back to Top | 📑 Table of Contents
Problem: Copy Linked List with Random Pointer
Description:
You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.
Create a deep copy of the list.
The deep copy should consist of exactly n new nodes, each including:
The original value val of the copied node A next pointer to the new node corresponding to the next pointer of the original node A random pointer to the new node corresponding to the random pointer of the original node
Tip
💡 Trick/Pattern:
Use hashmap to map old nodes to new nodes and then set the pointers in another loop.
Code:
oldMp = { None : None}
curr = head
while curr:
node = Node(curr.val)
oldMp[curr] = node
curr = curr.next
curr = head
while curr:
node = oldMp[curr]
node.next = oldMp[curr.next]
node.random = oldMp[curr.random]
curr = curr.next
return oldMp[head]⬆️ Back to Top | 📑 Table of Contents
Problem: Add Two Numbers
Description:
You are given two non-empty linked lists, l1 and l2, where each represents a non-negative integer.
The digits are stored in reverse order, e.g. the number 321 is represented as 1 -> 2 -> 3 -> in the linked list.
Each of the nodes contains a single digit. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Return the sum of the two numbers as a linked list.
Tip
💡 Trick/Pattern:
Traverse both lists, add digits with carry like elementary math, store the digit, and propagate the carry.
⬆️ Back to Top | 📑 Table of Contents
Problem: Find the Duplicate Number
Description:
You are given an array of integers nums containing n + 1 integers. Each integer in nums is in the range [1, n] inclusive.
Every integer appears exactly once, except for one integer which appears two or more times. Return the integer that appears more than once.
Tip
💡 Trick/Pattern:
Use Floyd's algorithm to find the cycle entry, which is the duplicate.
Code:
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow⬆️ Back to Top | 📑 Table of Contents
Problem: LRU Cache
Description:
Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations
LRUCache(int capacity) Initialize the LRU cache of size capacity. int get(int key) Return the value corresponding to the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.
Tip
💡 Trick/Pattern:
Use a hashmap for O(1) lookup and a doubly linked list to maintain usage order; move accessed items to the right and evict from the left.
⬆️ Back to Top | 📑 Table of Contents
Problem: Merge K Sorted Linked Lists
Description:
You are given an array of k linked lists lists, where each list is sorted in ascending order.
Return the sorted linked list that is the result of merging all of the individual linked lists.
Tip
💡 Trick/Pattern:
Use divide and conquer: repeatedly merge lists in pairs until only one list remains.
Code:
if not lists or len(lists) == 0:
return None
while len(lists) > 1:
mergedLists = []
for i in range(0,len(lists),2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
mergedLists.append(self.merge(l1,l2))
lists = mergedLists
return lists[0]
def merge(self,l1,l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val < l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
if l1:
curr.next = l1
if l2:
curr.next = l2
return dummy.next⬆️ Back to Top | 📑 Table of Contents
Problem: Reverse Nodes in K-Group
Description:
You are given the head of a singly linked list head and a positive integer k.
You must reverse the first k nodes in the linked list, and then reverse the next k nodes, and so on. If there are fewer than k nodes left, leave the nodes as they are.
Return the modified list after reversing the nodes in each group of k.
You are only allowed to modify the nodes' next pointers, not the values of the nodes.
Tip
💡 Trick/Pattern:
Iterate through the list in k-sized groups, validate group size, reverse each group in place, and reconnect it to the previous group using constant space.
Code:
dummy = ListNode(0,head)
groupPrev = dummy
while True:
kth = self.findKth(groupPrev, k)
if not kth:
break
groupNext = prev = kth.next
curr = groupPrev.next
while curr != groupNext:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
groupPrev_next = groupPrev.next
groupPrev.next = kth
groupPrev = groupPrev_next
return dummy.next
def findKth(self,curr,k):
while curr and k > 0:
curr = curr.next
k -= 1
return curr⬆️ Back to Top | 📑 Table of Contents
Problem: Invert Binary Tree
Description:
You are given the root of a binary tree root. Invert the binary tree and return its root.
Tip
💡 Trick/Pattern:
Use depth first search to iterate over the tree and swap root.left, root.right = root.right, root.left
⬆️ Back to Top | 📑 Table of Contents
Problem: Maximum Depth of Binary Tree
Description:
Given the root of a binary tree, return its depth.
The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.
Tip
💡 Trick/Pattern:
Use depth first search to iterate over the tree and increase depth + 1 every step, save the maximum each step.
⬆️ Back to Top | 📑 Table of Contents
Problem: Diameter of Binary Tree
Description:
The diameter of a binary tree is defined as the length of the longest path between any two nodes within the tree. The path does not necessarily have to pass through the root.
The length of a path between two nodes in a binary tree is the number of edges between the nodes. Note that the path can not include the same node twice.
Given the root of a binary tree root, return the diameter of the tree.
Tip
💡 Trick/Pattern:
Use depth first search to iterate over the tree and return the diameter (1 + max(left,right)) from the dfs function, save the max diameter max(left + right) each step.
Code:
self.dia = 0
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
self.dia = max(self.dia, left + right)
return 1 + max(left,right)
dfs(root)
return self.dia⬆️ Back to Top | 📑 Table of Contents
Problem: Balanced Binary Tree
Description:
Given a binary tree, return true if it is height-balanced and false otherwise.
A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Tip
💡 Trick/Pattern:
Do postorder DFS, get info from left and right subtrees, combine locally (here: balance + height), and return upward.
Code:
def dfs(root):
if not root:
return [True,0]
left = dfs(root.left)
right = dfs(root.right)
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
return [balanced, 1 + max(left[1],right[1])]
return dfs(root)[0]⬆️ Back to Top | 📑 Table of Contents
Problem: Same Binary Tree
Description:
Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.
Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.
Tip
💡 Trick/Pattern:
Use recursive DFS to compare current nodes and both subtrees; return false if mismatch, true if everything matches.
⬆️ Back to Top | 📑 Table of Contents
Problem: Subtree of Another Tree
Description:
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
Tip
💡 Trick/Pattern:
Traverse each node in the main tree, at each node, use a preorder DFS to check if the subtree rooted here matches the target tree.
Code:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not subRoot:
return True
if not root:
return False
if self.sameTree(root,subRoot):
return True
return self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)
def sameTree(self,p,q):
if not p and not q:
return True
if not p and q or not q and p:
return False
if p.val != q.val:
return False
return self.sameTree(p.left,q.left) and self.sameTree(p.right,q.right)⬆️ Back to Top | 📑 Table of Contents
Problem: Lowest Common Ancestor in Binary Search Tree
Description:
Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.
The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.
Tip
💡 Trick/Pattern:
Iterate over the tree if the p and q val are less than root.val move to the left else if p and q val are more than root.val move to the right else return the current node (LCA).
Code:
curr = root
while curr:
if curr.val > p.val and curr.val > q.val:
curr = curr.left
elif curr.val < p.val and curr.val < q.val:
curr = curr.right
else:
return curr⬆️ Back to Top | 📑 Table of Contents
Problem: Binary Tree Level Order Traversal
Description:
Given a binary tree root, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.
Tip
💡 Trick/Pattern:
Use BFS with a queue. Start with the root node. For each level, process all nodes in the queue, add their values to a level list, and enqueue their children. Continue until the queue is empty.
⬆️ Back to Top | 📑 Table of Contents
Problem: Binary Tree Right Side View
Description:
You are given the root of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.
Tip
💡 Trick/Pattern:
Use bfs and return the last value from each level.
⬆️ Back to Top | 📑 Table of Contents
Problem: Count Good Nodes in Binary Tree
Description:
Within a binary tree, a node x is considered good if the path from the root of the tree to the node x contains no nodes with a value greater than the value of node x
Given the root of a binary tree root, return the number of good nodes within the tree.
Tip
💡 Trick/Pattern:
Pass the current node value as maxi, if the node val is >= maxi, set res = 1. Perform DFS ato find the result.
Code:
def dfs(root,maxi):
if not root:
return 0
maxi = max(maxi,root.val)
res = 1 if root.val >= maxi else 0
res += dfs(root.left,maxi)
res += dfs(root.right, maxi)
return res
return dfs(root,root.val)⬆️ Back to Top | 📑 Table of Contents
Problem: Valid Binary Search Tree
Description:
Given the root of a binary tree, return true if it is a valid binary search tree, otherwise return false.
A valid binary search tree satisfies the following constraints:
The left subtree of every node contains only nodes with keys less than the node's key. The right subtree of every node contains only nodes with keys greater than the node's key. Both the left and right subtrees are also binary search trees.
Tip
💡 Trick/Pattern:
Do DFS while maintaining valid ranges from ancestors; a node is valid if it lies in (low, high) and both subtrees are valid with updated ranges.
Code:
def dfs(root,low,high):
if not root:
return True
if not (low < root.val < high):
return False
return dfs(root.left,low,root.val) and dfs(root.right,root.val,high)
return dfs(root,-1e9,1e9)⬆️ Back to Top | 📑 Table of Contents
Problem: Kth Smallest Integer in BST
Description:
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) in the tree.
A binary search tree satisfies the following constraints:
The left subtree of every node contains only nodes with keys less than the node's key. The right subtree of every node contains only nodes with keys greater than the node's key. Both the left and right subtrees are also binary search trees
Tip
💡 Trick/Pattern:
Perform inorder dfs and append the node values to array. Return value at the kth index from the array.
⬆️ Back to Top | 📑 Table of Contents
Problem: Construct Binary Tree from Preorder and Inorder Traversal
Description:
You are given two integer arrays preorder and inorder.
preorder is the preorder traversal of a binary tree inorder is the inorder traversal of the same tree Both arrays are of the same size and consist of unique values. Rebuild the binary tree from the preorder and inorder traversals and return its root.
Tip
💡 Trick/Pattern:
Pick root from preorder, find it in inorder to split left/right subtrees, then recursively build each subtree.
Code:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:mid+1],inorder[:mid])
root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:])
return root⬆️ Back to Top | 📑 Table of Contents
Problem: Binary Tree Maximum Path Sum
Description:
Given the root of a non-empty binary tree, return the maximum path sum of any non-empty path.
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can not appear in the sequence more than once. The path does not necessarily need to include the root.
The path sum of a path is the sum of the node's values in the path.
Tip
💡 Trick/Pattern:
Use postorder DFS to compute max gain from each node to its parent; update a global variable to track max path sum anywhere in the tree.
Code:
self.maxi = float('-infinity')
def dfs(root):
if not root:
return 0
leftMax = max(dfs(root.left),0)
rightMax = max(dfs(root.right),0)
self.maxi = max(self.maxi,leftMax + rightMax + root.val)
return root.val + max(leftMax,rightMax)
dfs(root)
return self.maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Serialize and Deserialize Binary Tree
Description:
Implement an algorithm to serialize and deserialize a binary tree.
Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.
You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no additional restriction on how your serialization/deserialization algorithm should work.
Tip
💡 Trick/Pattern:
Serialize using preorder DFS with placeholders for null nodes, and deserialize by recursively reading the values in preorder to rebuild the tree.
Code:
# Encodes a tree to a single string.
def serialize(self, root: Optional[TreeNode]) -> str:
self.res = []
def dfs(root):
if not root:
self.res.append("#")
return
self.res.append(str(root.val))
dfs(root.left)
dfs(root.right)
dfs(root)
return ",".join(self.res)
# Decodes your encoded data to tree.
def deserialize(self, data: str) -> Optional[TreeNode]:
self.res = data.split(',')
self.i = 0
def dfs():
if self.res[self.i] == "#":
self.i+=1
return
root = TreeNode(int(self.res[self.i]))
self.i += 1
root.left = dfs()
root.right = dfs()
return root
return dfs()⬆️ Back to Top | 📑 Table of Contents
Problem: Implement Trie (Prefix Tree)
Description:
A prefix tree (also known as a trie) is a tree data structure used to efficiently store and retrieve keys in a set of strings. Some applications of this data structure include auto-complete and spell checker systems.
Implement the PrefixTree class:
PrefixTree() Initializes the prefix tree object. void insert(String word) Inserts the string word into the prefix tree. boolean search(String word) Returns true if the string word is in the prefix tree (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Tip
💡 Trick/Pattern:
Use a TrieNode class with a children hashmap (char → TrieNode) and an end-of-word boolean flag. For insert, traverse/create nodes for each character. For search/startsWith, traverse the trie and check if the path exists.
⬆️ Back to Top | 📑 Table of Contents
Problem: Design Add and Search Word Data Structure
Description:
Design a data structure that supports adding new words and searching for existing words.
Implement the WordDictionary class:
void addWord(word) Adds word to the data structure. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
Tip
💡 Trick/Pattern:
Use a trie to store the words. Use dfs to find the words, if the char is '.' try every possibility.
Code:
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
curr = self.root
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
curr.end = True
def search(self, word: str) -> bool:
def dfs(i,curr):
if i == len(word):
return curr.end
c = word[i]
if c == '.':
for child in curr.children.values():
if dfs(i + 1,child):
return True
return False
else:
if c not in curr.children:
return False
return dfs(i + 1, curr.children[c])
return dfs(0,self.root)⬆️ Back to Top | 📑 Table of Contents
Problem: Word Search II
Description:
Given a 2-D grid of characters board and a list of strings words, return all words that are present in the grid.
For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.
Tip
💡 Trick/Pattern:
Build a Trie of all words, then run DFS from each board cell, pruning paths that don’t exist in the Trie and recording words at Trie end nodes.
Code:
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
def addWord(self,word):
curr = self
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
curr.end = True
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m,n = len(board) ,len(board[0])
vis = set()
res = set()
root = TrieNode()
for word in words:
root.addWord(word)
def dfs(r,c,curr,w):
if r < 0 or c < 0 or r == m or c == n or (r,c) in vis or board[r][c] not in curr.children:
return
vis.add((r,c))
w += board[r][c]
curr = curr.children[board[r][c]]
if curr.end:
res.add(w)
dfs(r+1,c,curr,w)
dfs(r-1,c,curr,w)
dfs(r,c+1,curr,w)
dfs(r,c-1,curr,w)
vis.remove((r,c))
for r in range(m):
for c in range(n):
dfs(r,c,root,"")
return list(res)⬆️ Back to Top | 📑 Table of Contents
Problem: Subsets
Description:
Given an array nums of unique integers, return all possible subsets of nums.
The solution set must not contain duplicate subsets. You may return the solution in any order.
Tip
💡 Trick/Pattern:
Treat numbers from 0 to 2ⁿ − 1 as bitmasks, where each bit decides whether the corresponding element is included in the subset.
⬆️ Back to Top | 📑 Table of Contents
Problem: Combination Sum
Description:
You are given an array of distinct integers nums and a target integer target. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.
The same number may be chosen from nums an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.
You may return the combinations in any order and the order of the numbers in each combination can be in any order.
Tip
💡 Trick/Pattern:
DFS with two choices per index: take the current number (stay on the same index since reuse is allowed) or skip it (move to the next index).
Code:
res = []
def gen(i,s,sub):
if s == target:
res.append(sub[:])
return
if i >= len(nums) or s > target:
return
sub.append(nums[i])
gen(i, s + nums[i], sub)
sub.pop()
gen(i + 1, s, sub)
gen(0,0,[])
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Combination Sum II
Description:
You are given an array of integers candidates, which may contain duplicates, and a target integer target. Your task is to return a list of all unique combinations of candidates where the chosen numbers sum to target.
Each element from candidates may be chosen at most once within a combination. The solution set must not contain duplicate combinations.
You may return the combinations in any order and the order of the numbers in each combination can be in any order.
Tip
💡 Trick/Pattern:
Sort first so duplicates are adjacent; during DFS, take the number once, and when you skip it, advance the index past all identical values to prevent duplicate combinations.
Code:
res = []
candidates.sort()
def gen(i,s,sub):
if s == target:
res.append(sub[:])
return
if i >= len(candidates) or s > target:
return
sub.append(candidates[i])
gen(i + 1, s + candidates[i], sub)
sub.pop()
while i + 1 < len(candidates) and candidates[i] == candidates[i+1]:
i += 1
gen(i + 1, s, sub)
gen(0,0,[])
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Permutations
Description:
Given an array nums of unique integers, return all the possible permutations. You may return the answer in any order.
Tip
💡 Trick/Pattern:
Start with an empty permutation; for each number, insert it into all positions of every existing permutation to generate the next layer.
Code:
perms = [[]]
for n in nums:
new_perm = []
for p in perms:
for i in range(len(p) + 1):
p_copy = p.copy()
p_copy.insert(i,n)
new_perm.append(p_copy)
perms = new_perm
return perms⬆️ Back to Top | 📑 Table of Contents
Problem: Subsets II
Description:
You are given an array nums of integers, which may contain duplicates. Return all possible subsets.
The solution must not contain duplicate subsets. You may return the solution in any order.
Tip
💡 Trick/Pattern:
Sort the array, then use backtracking; when you skip a number, skip all of its duplicates to avoid duplicate subsets.
Code:
res = []
nums.sort()
def gen(i,sub):
if i == len(nums):
res.append(sub[:])
return
sub.append(nums[i])
gen(i + 1, sub)
sub.pop()
while i + 1 < len(nums) and nums[i] == nums[i+1]:
i += 1
gen(i + 1, sub)
gen(0,[])
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Generate Parentheses
Description:
You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.
Tip
💡 Trick/Pattern:
Backtrack while keeping counts of open and closed parentheses; you can add ( if opens < n, and ) only if closes < opens.
Code:
res = []
part = []
def gen(openN,closedN):
if openN == closedN == n:
res.append("".join(part[:]))
return
if openN < n:
part.append('(')
gen(openN + 1,closedN)
part.pop()
if closedN < openN:
part.append(')')
gen(openN, closedN + 1)
part.pop()
gen(0,0)
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Word Search
Description:
Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.
For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.
Tip
💡 Trick/Pattern:
Start DFS from every cell, match characters one by one, mark cells as visited during the path, and backtrack after exploring.
⬆️ Back to Top | 📑 Table of Contents
Problem: Palindrome Partitioning
Description:
Given a string s, split s into substrings where every substring is a palindrome. Return all possible lists of palindromic substrings.
Tip
💡 Trick/Pattern:
Backtrack by cutting the string at every possible index, and only recurse when the chosen substring is a palindrome.
Code:
def partition(self, s: str) -> List[List[str]]:
parts = []
res = []
def gen(i):
if i >= len(s):
res.append(parts[:])
return
for j in range(i,len(s)):
if self.isPalindrome(s,i,j):
parts.append(s[i:j+1])
gen(j + 1)
parts.pop()
gen(0)
return res
def isPalindrome(self,s,l,r):
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True⬆️ Back to Top | 📑 Table of Contents
Problem: Letter Combinations of a Phone Number
Description:
You are given a string digits made up of digits from 2 through 9 inclusive.
Each digit (not including 1) is mapped to a set of characters as shown below:
A digit could represent any one of the characters it maps to.
Return all possible letter combinations that digits could represent. You may return the answer in any order.
Tip
💡 Trick/Pattern:
Backtrack over the digit string, and for each digit, try all mapped letters before moving to the next digit.
Code:
mp = {
"2": ["a","b","c"],
"3": ["d","e","f"],
"4": ["g","h","i"],
62BF
"5": ["j","k","l"],
"6": ["m","n","o"],
"7": ["p","q","r","s"],
"8": ["t","u","v"],
"9": ["w","x","y","z"],
}
sub = []
res = []
def gen(i):
if i >= len(digits):
res.append("".join(sub[:]))
return
for digit in mp[digits[i]]:
sub.append(digit)
gen(i+1)
sub.pop()
if digits:
gen(0)
return res⬆️ Back to Top | 📑 Table of Contents
Problem: N-Queens
Description:
The n-queens puzzle is the problem of placing n queens on an n x n chessboard so that no two queens can attack each other.
A queen in a chessboard can attack horizontally, vertically, and diagonally.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a unique board layout where the queen pieces are placed. 'Q' indicates a queen and '.' indicates an empty space.
Tip
💡 Trick/Pattern:
Backtrack row by row, and track used columns, positive diagonals (r+c), and negative diagonals (r−c) to ensure constant-time validity checks.
Code:
col,pos,neg = set(),set(),set()
board = [['.'] * n for _ in range(n)]
res = []
def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if c in col or (r+c) in pos or (r-c) in neg:
continue
col.add(c)
pos.add(r+c)
neg.add(r-c)
board[r][c] = 'Q'
backtrack(r+1)
col.remove(c)
pos.remove(r+c)
neg.remove(r-c)
board[r][c] = '.'
backtrack(0)
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Kth Largest Element In a Stream
Description:
Design a class to find the kth largest integer in a stream of values, including duplicates. E.g. the 2nd largest from [1, 2, 3, 3] is 3. The stream is not necessarily sorted.
Implement the following methods:
constructor(int k, int[] nums) Initializes the object given an integer k and the stream of integers nums. int add(int val) Adds the integer val to the stream and returns the kth largest integer in the stream.
Tip
💡 Trick/Pattern:
Use a heap
⬆️ Back to Top | 📑 Table of Contents
Problem: Last Stone Weight
Description:
You are given an array of integers stones where stones[i] represents the weight of the ith stone.
We want to run a simulation on the stones as follows:
At each step we choose the two heaviest stones, with weight x and y and smash them togethers If x == y, both stones are destroyed If x < y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. Continue the simulation until there is no more than one stone remaining.
Return the weight of the last remaining stone or return 0 if none remain.
Tip
💡 Trick/Pattern:
Push all stones into a max-heap, repeatedly pop the two largest, and if they’re unequal, push back their difference until one or zero stones remain.
Code:
heap = [-stone for stone in stones]
heapq.heapify(heap)
while len(heap) > 1:
x = heapq.heappop(heap)
y = heapq.heappop(heap)
if x != y:
y = abs(y - x)
heapq.heappush(heap,-y)
return -heap[0] if heap else 0⬆️ Back to Top | 📑 Table of Contents
Problem: K Closest Points to Origin
Description:
You are given an 2-D array points where points[i] = [xi, yi] represents the coordinates of a point on an X-Y axis plane. You are also given an integer k.
Return the k closest points to the origin (0, 0).
The distance between two points is defined as the Euclidean distance (sqrt((x1 - x2)^2 + (y1 - y2)^2)).
You may return the answer in any order.
Tip
💡 Trick/Pattern:
Use a max-heap of size k to maintain the k closest points, pushing new points and popping the farthest if the heap grows.
⬆️ Back to Top | 📑 Table of Contents
Problem: Kth Largest Element in an Array
Description:
Given an unsorted array of integers nums and an integer k, return the kth largest element in the array.
By kth largest element, we mean the kth largest element in the sorted order, not the kth distinct element
Tip
💡 Trick/Pattern:
Push each number into a min-heap of size k, popping the smallest when the heap exceeds k, at the end, the heap root is the answer.
⬆️ Back to Top | 📑 Table of Contents
Problem: Task Scheduler
Description:
You are given an array of CPU tasks tasks, where tasks[i] is an uppercase english character from A to Z. You are also given an integer n.
Each CPU cycle allows the completion of a single task, and tasks may be compl A901 eted in any order.
The only constraint is that identical tasks must be separated by at least n CPU cycles, to cooldown the CPU.
Return the minimum number of CPU cycles required to complete all tasks.
Tip
💡 Trick/Pattern:
Count task frequencies, push them as negative values in a max-heap, and at each timestep, execute the top task if available, push tasks into a cooldown queue with the time they can be reused.
Code:
count = Counter(tasks)
heap = [-cnt for cnt in count.values()]
heapq.heapify(heap)
q = deque()
time = 0
while heap or q:
time += 1
if heap:
cnt = 1 + heapq.heappop(heap)
if cnt:
q.append([cnt,time + n])
⬆️ Back to Top | 📑 Table of Contents
Problem: Design Twitter
Description:
Implement a simplified version of Twitter which allows users to post tweets, follow/unfollow each other, and view the 10 most recent tweets within their own news feed.
Users and tweets are uniquely identified by their IDs (integers).
Implement the following methods:
Twitter() Initializes the twitter object. void postTweet(int userId, int tweetId) Publish a new tweet with ID tweetId by the user userId. You may assume that each tweetId is unique. List getNewsFeed(int userId) Fetches at most the 10 most recent tweet IDs in the user's news feed. Each item must be posted by users who the user is following or by the user themself. Tweets IDs should be ordered from most recent to least recent. void follow(int followerId, int followeeId) The user with ID followerId follows the user with ID followeeId. void unfollow(int followerId, int followeeId) The user with ID followerId unfollows the user with ID followeeId.
Tip
💡 Trick/Pattern:
Store each user’s tweets in a list with a timestamp (using a decreasing counter to simulate max-heap ordering). For the news feed, push the latest tweet of each followee into a heap and pop the 10 most recent, pushing the next tweet from that followee if available.
Code:
class Twitter:
def __init__(self):
self.posts = defaultdict(list)
self.followers = defaultdict(set)
self.count = 0
def postTweet(self, userId: int, tweetId: int) -> None:
self.posts[userId].append([self.count,tweetId])
self.count -= 1
def getNewsFeed(self, userId: int) -> List[int]:
heap = []
res = []
self.followers[userId].add(userId)
for followeeId in self.followers[userId]:
if followeeId in self.posts:
index = len(self.posts[followeeId]) - 1
count,tweetId = self.posts[followeeId][index]
heapq.heappush(heap,[count,tweetId,followeeId,index - 1])
while heap and len(res) < 10:
count,tweetId,followeeId,index = heapq.heappop(heap)
res.append(tweetId)
if index >= 0:
count,tweetId = self.posts[followeeId][index]
heapq.heappush(heap,[count,tweetId,followeeId,index - 1])
return res
def follow(self, followerId: int, followeeId: int) -> None:
self.followers[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followeeId in self.followers[followerId]:
self.followers[followerId].remove(followeeId)⬆️ Back to Top | 📑 Table of Contents
Problem: Find Median From Data Stream
Description:
The median is the middle value in a sorted list of integers. For lists of even length, there is no middle value, so the median is the mean of the two middle values.
For example:
For arr = [1,2,3], the median is 2. For arr = [1,2], the median is (1 + 2) / 2 = 1.5 Implement the MedianFinder class:
MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure. double findMedian() returns the median of all elements so far.
Tip
💡 Trick/Pattern:
Maintain two heaps a max-heap for the smaller half and a min-heap for the larger half so the median is always at the top of the heaps.
Code:
class MedianFinder:
def __init__(self):
self.small,self.large = [],[]
def addNum(self, num: int) -> None:
heapq.heappush(self.small,-num)
if self.small and self.large and -self.small[0] > self.large[0]:
val = -heapq.heappop(self.small)
heapq.heappush(self.large,val)
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large,val)
if len(self.large) > len(self.small):
val = heapq.heappop(self.large)
heapq.heappush(self.small,-val)
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
if len(self.large) > len(self.small):
return self.large[0]
return (-self.small[0] + self.large[0]) / 2
⬆️ Back to Top | 📑 Table of Contents
Problem: Number of Islands
Description:
Given a 2D grid grid where '1' represents land and '0' represents water, count and return the number of islands.
An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).
Tip
💡 Trick/Pattern:
Iterate over the grid, and when an unvisited '1' is found, start a DFS to mark all connected '1' cells. Increment the island count for each DFS start.
Code:
vis = set()
m,n = len(grid), len(grid[0])
i = 0
def dfs(r,c):
if r < 0 or c < 0 or r == m or c == n or (r,c) in vis or grid[r][c] != "1":
return
vis.add((r,c))
dfs(r+1,c)
dfs(r-1,c)
dfs(r,c+1)
dfs(r,c-1)
for r in range(m):
for c in range(n):
if grid[r][c] == '1' and (r,c) not in vis:
i += 1
dfs(r,c)
return i⬆️ Back to Top | 📑 Table of Contents
Problem: Max Area of Island
Description:
You are given a matrix grid where grid[i] is either a 0 (representing water) or 1 (representing land).
An island is defined as a group of 1's connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
The area of an island is defined as the number of cells within the island.
Return the maximum area of an island in grid. If no island exists, return 0.
Tip
💡 Trick/Pattern:
Iterate over the grid; when an unvisited '1' is found, DFS to count all connected cells. Keep track of the maximum area encountered.
Code:
m,n = len(grid),len(grid[0])
vis = set()
def dfs(r,c):
if r < 0 or c < 0 or r == m or c == n or (r,c) in vis or grid[r][c] != 1:
return 0
vis.add((r,c))
area = 1
area += dfs(r+1,c)
area += dfs(r-1,c)
area += dfs(r,c+1)
area += dfs(r,c-1)
return area
maxi = 0
for r in range(m):
for c in range(n):
maxi = max(maxi,dfs(r,c))
return maxi⬆️ Back to Top | 📑 Table of Contents
Problem: Clone Graph
Description:
Given a node in a connected undirected graph, return a deep copy of the graph.
Tip
💡 Trick/Pattern:
Use DFS to copy nodes, and a hashmap to avoid revisiting nodes and handle cycles.
Code:
oldMp = {}
def dfs(node):
if node in oldMp:
return oldMp[node]
copy = Node(node.val)
oldMp[node] = copy
for nei in node.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node) if node else None⬆️ Back to Top | 📑 Table of Contents
Problem: Islands and Treasure
Description:
You are given an m×n 2D grid initialized with these three possible values:
-1 - A water cell that can not be traversed. 0 - A treasure chest. INF - A land cell that can be traversed. We use the integer 2^31 - 1 = 2147483647 to represent INF. Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest then the value should remain INF.
Assume the grid can only be traversed up, down, left, or right.
Modify the grid in-place.
Tip
💡 Trick/Pattern:
Enqueue all gate positions at the start. At each BFS level, increment distance and fill empty rooms with the current distance. This guarantees the shortest distance from any gate.
Code:
m,n = len(grid),len(grid[0])
vis = set()
q = deque()
def addRoom(r,c):
if r < 0 or c < 0 or r == m or c == n or (r,c) in vis or grid[r][c] == -1:
return
vis.add((r,c))
q.append((r,c))
for r in range(m):
for c in range(n):
if grid[r][c] == 0:
vis.add((r,c))
q.append((r,c))
dist = 0
while q:
for _ in range(len(q)):
r,c = q.popleft()
grid[r][c] = dist
addRoom(r+1,c)
addRoom(r-1,c)
addRoom(r,c+1)
addRoom(r,c-1)
dist += 1⬆️ Back to Top | 📑 Table of Contents
Problem: Rotting Fruit
Description:
You are given a 2-D matrix grid. Each cell can have one of three possible values:
0 representing an empty cell 1 representing a fresh fruit 2 representing a rotten fruit Every minute, if a fresh fruit is horizontally or vertically adjacent to a rotten fruit, then the fresh fruit also becomes rotten.
Return the minimum number of minutes that must elapse until there are zero fresh fruits remaining. If this state is impossible within the grid, return -1.
Tip
💡 Trick/Pattern:
Enqueue all initial rotten oranges. At each BFS level, rot all adjacent fresh oranges and count them. Track the time taken; if any fresh oranges remain unrotted, return -1.
Code:
m,n = len(grid),len(grid[0])
q = deque()
self.rotten,total = 0,0
def addFruit(r,c):
if r < 0 or c < 0 or r == m or c == n or grid[r][c] != 1:
return
grid[r][c] = 2
self.rotten += 1
q.append((r,c))
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
self.rotten += 1
total += 1
q.append((r,c))
elif grid[r][c] == 1:
total += 1
time = 0
while q and self.rotten < total:
for _ in range(len(q)):
r,c = q.popleft()
addFruit(r+1,c)
addFruit(r-1,c)
addFruit(r,c+1)
addFruit(r,c-1)
time += 1
return time if self.rotten == total else -1⬆️ Back to Top | 📑 Table of Contents
Problem: Pacific Atlantic Water Flow
Description:
You are given a rectangular island heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The islands borders the Pacific Ocean from the top and left sides, and borders the Atlantic Ocean from the bottom and right sides.
Water can flow in four directions (up, down, left, or right) from a cell to a neighboring cell with height equal or lower. Water can also flow into the ocean from cells adjacent to the ocean.
Find all cells where water can flow from that cell to both the Pacific and Atlantic oceans. Return it as a 2D list where each element is a list [r, c] representing the row and column of the cell. You may return the answer in any order.
Tip
💡 Trick/Pattern:
Start DFS from all Pacific-border cells (top row + left column) and Atlantic-border cells (bottom row + right column). For each DFS, only move to cells with height ≥ previous to simulate water flow. The cells visited by both DFS runs are the answer.
Code:
m,n = len(heights),len(heights[0])
pac,atl = set(),set()
def dfs(r,c,vis,prev):
if r < 0 or c < 0 or r == m or c == n or (r,c) in vis or prev > heights[r][c]:
return
vis.add((r,c))
dfs(r+1,c,vis,heights[r][c])
dfs(r-1,c,vis,heights[r][c])
dfs(r,c+1,vis,heights[r][c])
dfs(r,c-1,vis,heights[r][c])
for r in range(m):
dfs(r,0,pac,heights[r][0])
dfs(r,n-1,atl,heights[r][n-1])
for c in range(n):
dfs(0,c,pac,heights[0][c])
dfs(m-1,c,atl,heights[m-1][c])
res = []
for r in range(m):
for c in range(n):
if (r,c) in pac and (r,c) in atl:
res.append([r,c])
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Surrounded Regions
Description:
You are given a 2-D matrix board containing 'X' and 'O' characters.
If a continous, four-directionally connected group of 'O's is surrounded by 'X's, it is considered to be surrounded.
Change all surrounded regions of 'O's to 'X's and do so in-place by modifying the input board.
Tip
💡 Trick/Pattern:
Start DFS from all ‘O’s on the borders, temporarily marking them as safe (e.g., ‘T’). After DFS, iterate the grid: convert remaining ‘O’s to ‘X’ (captured), and convert ‘T’s back to ‘O’ (safe).
Code:
m,n = len(board),len(board[0])
vis = set()
def dfs(r,c):
if r < 0 or c < 0 or r == m or c == n or (r,c) in vis or board[r][c] != 'O':
return
vis.add((r,c))
board[r][c] = 'T'
dfs(r+1,c)
dfs(r-1,c)
dfs(r,c+1)
dfs(r,c-1)
for r in range(m):
dfs(r,0)
dfs(r,n-1)
for c in range(n):
dfs(0,c)
dfs(m-1,c)
for r in range(m):
for c in range(n):
if board[r][c] == 'O':
board[r][c] = 'X'
if board[r][c] == 'T':
board[r][c] = 'O'⬆️ Back to Top | 📑 Table of Contents
Problem: Course Schedule
Description:
You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.
The pair [0, 1], indicates that must take course 1 before taking course 0.
There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.
Return true if it is possible to finish all courses, otherwise return false.
Tip
💡 Trick/Pattern:
Detect a cycle in the directed graph using DFS for topological sort, if any node is visited again in the current recursion path, there’s a cycle and you cannot finish all courses.
Code:
adjList = {i: [] for i in range(numCourses)}
for x,y in prerequisites:
adjList[x].append(y)
vis,cycle = set(),set()
def dfs(i):
if i in vis:
return True
if i in cycle:
return False
cycle.add(i)
for nei in adjList[i]:
if not dfs(nei):
return False
cycle.remove(i)
vis.add(i)
return True
for i in range(numCourses):
if not dfs(i):
return False
return True⬆️ Back to Top | 📑 Table of Contents
Problem: Course Schedule II
Description:
You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.
Return a valid ordering of courses you can take to finish all courses. If there are many valid answers, return any of them. If it's not possible to finish all courses, return an empty array.
Tip
💡 Trick/Pattern:
Run DFS for topological sort with cycle detection, if a node revisits itself on the current recursion stack it’s cyclic (no valid order), else collect nodes in post‑DFS order to form the course schedule.
Code:
adjList = {i: [] for i in range(numCourses)}
for x,y in prerequisites:
adjList[x].append(y)
vis,cycle = set(),set()
res = []
def dfs(i):
if i in vis:
return True
if i in cycle:
return False
cycle.add(i)
for nei in adjList[i]:
if not dfs(nei):
return False
cycle.remove(i)
vis.add(i)
res.append(i)
return True
for i in range(numCourses):
if not dfs(i):
return []
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Graph Valid Tree
Description:
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Tip
💡 Trick/Pattern:
DFS from any node, ignore the parent to avoid trivial cycles, and check that all nodes are visited; if so, it’s a single connected acyclic tree.
Code:
adjList = {i: [] for i in range(n)}
for x,y in edges:
adjList[x].append(y)
adjList[y].append(x)
vis = set()
def dfs(i,parent):
if i in vis:
return False
vis.add(i)
for nei in adjList[i]:
if nei != parent:
if not dfs(nei,i):
return False
return True
return dfs(0,-1) and len(vis) == n⬆️ Back to Top | 📑 Table of Contents
Problem: Number of Connected Components in an Undirected Graph
Description:
There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.
The nodes are numbered from 0 to n - 1.
Return the total number of connected components in that graph.
Tip
💡 Trick/Pattern:
Use Union-Find with path compression and union by rank; start with n components and subtract 1 for each successful union, remaining count is the number of connected components.
Code:
par = [i for i in range(n)]
rank = [1] * n
def find(n1):
res = n1
while res != par[res]:
par[res] = par[par[res]]
res = par[res]
return res
def union(n1,n2):
p1,p2 = find(n1), find(n2)
if p1 == p2:
return 0
if rank[p2] > rank[p1]:
par[p1] = p2
rank[p2] += rank[p1]
else:
par[p2]= p1
rank[p1] += rank[p2]
return 1
res = n
for n1,n2 in edges:
res -= union(n1,n2)
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Redundant Connection
Description:
You are given a connected undirected graph with n nodes labeled from 1 to n. Initially, it contained no cycles and consisted of n-1 edges.
We have now added one additional edge to the graph. The edge has two different vertices chosen from 1 to n, and was not an edge that previously existed in the graph.
The graph is represented as an array edges of length n where edges[i] = [ai, bi] represents an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the graph is still a connected non-cyclical graph. If there are multiple answers, return the edge that appears last in the input edges.
Tip
💡 Trick/Pattern:
Use Union-Find with path compression; the first edge whose endpoints are already connected is the redundant one.
⬆️ Back to Top | 📑 Table of Contents
Problem: Word Ladder
Description:
You are given two words, beginWord and endWord, and also a list of words wordList. All of the given words are of the same length, consisting of lowercase English letters, and are all distinct.
Your goal is to transform beginWord into endWord by following the rules:
You may transform beginWord to any word within wordList, provided that at exactly one position the words have a different character, and the rest of the positions have the same characters. You may repeat the previous step with the new word that you obtain, and you may do this as many times as needed. Return the minimum number of words within the transformation sequence needed to obtain the endWord, or 0 if no such sequence exists.
Tip
💡 Trick/Pattern:
Precompute all * wildcard patterns to find neighbors in O(1); then BFS from beginWord, counting levels until endWord is reached.
Code:
adjList = defaultdict(list)
wordList.append(beginWord)
vis = set([beginWord])
q = deque([beginWord])
for word in wordList:
for j in range(len(word)):
pattern = word[:j] + "*" + word[j+1:]
adjList[pattern].append(word)
res = 1
while q:
for _ in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + "*" + word[j+1:]
for nei in adjList[pattern]:
if nei not in vis:
vis.add(nei)
q.append(nei)
res += 1
return 0⬆️ Back to Top | 📑 Table of Contents
Problem: Climbing Stairs
Description:
You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time.
Return the number of distinct ways to climb 62BF to the top of the staircase
Tip
💡 Trick/Pattern:
Use top-down DP with memoization: the ways to reach step i = ways to reach i-1 + ways to reach i-2
⬆️ Back to Top | 📑 Table of Contents
Problem: Min Cost Climbing Stairs
Description:
You are given an array of integers cost where cost[i] is the cost of taking a step from the ith floor of a staircase. After paying the cost, you can step to either the (i + 1)th floor or the (i + 2)th floor.
You may choose to start at the index 0 or the index 1 floor.
Return the minimum cost to reach the top of the staircase, i.e. just past the last index in cost.
Tip
💡 Trick/Pattern:
Use top-down DP: the min cost to reach the top from step i = cost[i] + min(f(i+1), f(i+2)); start from step 0 or 1.
⬆️ Back to Top | 📑 Table of Contents
Problem: House Robber
Description:
You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a straight line, i.e. the ith house is the neighbor of the (i-1)th and (i+1)th house.
You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.
Return the maximum amount of money you can rob without alerting the police.
Tip
💡 Trick/Pattern:
Use top-down DP: at each house i, max loot = max(nums[i] + f(i+2), f(i+1)); memoize to avoid recomputation.
⬆️ Back to Top | 📑 Table of Contents
Problem: House Robber II
Description:
You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.
You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.
Return the maximum amount of money you can rob without alerting the police.
Tip
💡 Trick/Pattern:
Since first and last houses are neighbors, run House Robber twice—once excluding the first house, once excluding the last—then take the max.
Code:
if len(nums) <= 1:
return nums[0]
dp = {}
def f(i,arr):
if i >= len(arr):
return 0
if i in dp:
return dp[i]
take = arr[i] + f(i+2,arr)
notTake = f(i+1,arr)
dp[i] = max(take,notTake)
return dp[i]
ans1 = f(0,nums[1:])
dp = {}
ans2 = f(0,nums[:-1])
return max(ans1,ans2)⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Palindromic Substring
Description:
Given a string s, return the longest substring of s that is a palindrome.
A palindrome is a string that reads the same forward and backward.
If there are multiple palindromic substrings that have the same length, return any one of them.
Tip
💡 Trick/Pattern:
Expand around every center (both single and double characters) and track the longest palindrome seen.
Code:
res = ""
for i in range(len(s)):
l,r = i,i
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1
r += 1
l,r = i,i+1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1
r += 1
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Palindromic Substrings
Description:
Given a string s, return the number of substrings within s that are palindromes.
A palindrome is a string that reads the same forward and backward.
Tip
💡 Trick/Pattern:
Expand around every center (single and double) and count each valid palindrome as you go.
⬆️ Back to Top | 📑 Table of Contents
Problem: Decode Ways
Description:
A string consisting of uppercase english characters can be encoded to a number using the following mapping:
'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, "1012" can be mapped into:
"JAB" with the grouping (10 1 2) "JL" with the grouping (10 12) The grouping (1 01 2) is invalid because 01 cannot be mapped into a letter since it contains a leading zero.
Tip
💡 Trick/Pattern:
Use top-down DP: at index i, ways = f(i+1) if single digit is valid + f(i+2) if two-digit number is 10–26; memoize results.
Code:
dp = {}
def f(i):
if i == len(s):
return 1
if s[i] == '0':
return 0
if i in dp:
return dp[i]
res = f(i+1)
if (i + 1) < len(s) and (s[i] == '1' or (s[i] == '2' and s[i+1] in '0123456')):
res += f(i+2)
dp[i] = res
return res
return f(0)⬆️ Back to Top | 📑 Table of Contents
Problem: Coin Change
Description:
You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.
Return the fewest number of coins that you need to make up the exact target amount. If it is impossible to make up the amount, return -1.
You may assume that you have an unlimited number of each coin.
Tip
💡 Trick/Pattern:
Use top-down DP: at coin index i and current sum s, min coins = min(1 + f(i, s+coins[i]), f(i+1, s)); return -1 if impossible.
⬆️ Back to Top | 📑 Table of Contents
Problem: Maximum Product Subarray
Description:
Given an integer array nums, find a subarray that has the largest product within the array and return it.
A subarray is a contiguous non-empty sequence of elements within an array.
You can assume the output will fit into a 32-bit integer.
Tip
💡 Trick/Pattern:
Track both current max and min products at each step; max product = max(currMax, ncurrMax, ncurrMin) and min similarly, to handle negatives.
Code:
currMin,currMax = 1,1
res = max(nums)
for n in nums:
tmp = n * currMax
currMax = max(tmp,n * currMin,n)
currMin = min(tmp, n * currMin, n)
res = max(res,currMax)
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Word Break
Description:
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.
You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.
Tip
💡 Trick/Pattern:
Use top-down DP: at index i, try every word that matches the substring starting at i; if any path reaches the end, return True, else memoize False.
Code:
dp = {}
def f(i):
if i == len(s):
return True
if i in dp:
return dp[i]
for w in wordDict:
if i + len(w) <= len(s) and s[i:i+len(w)] == w:
if f(i+len(w)):
return True
dp[i] = False
return False
return f(0)⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Increasing Subsequence
Description:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.
For example, "cat" is a subsequence of "crabt".
Tip
💡 Trick/Pattern:
Use top-down DP with (index, previous value) as state: at each step, either take nums[i] if it’s bigger than prev or skip it; max length = max(take, skip).
⬆️ Back to Top | 📑 Table of Contents
Problem: Partition Equal Subset Sum
Description:
You are given an array of positive integers nums.
Return true if you can partition the array into two subsets, subset1 and subset2 where sum(subset1) == sum(subset2). Otherwise, return false.
Tip
💡 Trick/Pattern:
Use top-down DP: try to form target = sum(nums)//2 by either taking or skipping each number, if any combination reaches target, return True.
Code:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [[-1] * (target + 1) for _ in range(len(nums))]
def f(i,s):
if s == target:
return True
if s > target or i >= len(nums):
return False
if dp[i][s] != -1:
return dp[i][s]
take = f(i+1,s + nums[i])
notTake = f(i+1,s)
dp[i][s] = take or notTake
return dp[i][s]
return f(0,0)⬆️ Back to Top | 📑 Table of Contents
Problem: Insert Interval
Description:
You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represents the start and the end time of the ith interval. intervals is initially sorted in ascending order by start_i.
You are given another interval newInterval = [start, end].
Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and also intervals still does not have any overlapping intervals. You may merge the overlapping intervals if needed.
Return intervals after adding newInterval.
Tip
💡 Trick/Pattern:
Iterate intervals once: append non-overlapping intervals before, merge overlaps into newInterval, then append the rest.
Code:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [min(newInterval[0],intervals[i][0]),max(newInterval[1],intervals[i][1])]
res.append(newInterval)
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Merge Intervals
Description:
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
You may return the answer in any order.
Note: Intervals are non-overlapping if they have no common point. For example, [1, 2] and [3, 4] are non-overlapping, but [1, 2] and [2, 3] are overlapping.
Tip
💡 Trick/Pattern:
First, sort intervals by start. Then iterate through them: if the current interval overlaps with the last interval in the result, merge them by updating the end; otherwise, append the interval. One pass after sorting gives the merged intervals.
Code:
intervals.sort(key=lambda x:x[0])
res = [intervals[0]]
for start,end in intervals[1:]:
last = res[-1][1]
if start <= last:
res[-1][1] = max(end,last)
else:
res.append([start,end])
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Non-overlapping Intervals
Description:
Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note: Intervals are non-overlapping even if they have a common point. For example, [1, 3] and [2, 4] are overlapping, but [1, 2] and [2, 3] are non-overlapping.
Tip
💡 Trick/Pattern:
Sort intervals by end time. Then iterate: if an interval starts before the last kept interval’s end, it overlaps → remove it (count it). Otherwise, update last to the current interval’s end. The count gives the minimum removals.
Code:
intervals.sort(key=lambda x:x[1])
last = intervals[0][1]
res = 0
for start,end in intervals[1:]:
if start < last:
res += 1
else:
last = end
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Meeting Rooms
Description:
Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), determine if a person could add all meetings to their schedule without any conflicts.
Tip
💡 Trick/Pattern:
Sort intervals by start time, then check each interval: if the current start < previous end, there’s an overlap → return False. Otherwise, update the previous end. If no overlaps are found, return True.
⬆️ Back to Top | 📑 Table of Contents
Problem: Meeting Rooms II
Description:
Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of days required to schedule all meetings without any conflicts.
Tip
💡 Trick/Pattern:
Sort by start → min-heap of end times → reuse room if possible → heap size = min rooms.
Code:
if not intervals:
return 0
intervals.sort(key=lambda x:x.start)
heap = []
for it in intervals:
if heap and heap[0] <= it.start:
heapq.heappop(heap)
heapq.heappush(heap,it.end)
return len(heap)⬆️ Back to Top | 📑 Table of Contents
Problem: Minimum Interval to Include Each Query
Description:
You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] represents the ith interval starting at left_i and ending at right_i (inclusive).
You are also given an integer array of query points queries. The result of query[j] is the length of the shortest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the result of this query is -1.
Return an array output where output[j] is the result of query[j].
Tip
💡 Trick/Pattern:
Sort intervals by start and queries in order. Use a min-heap of (length, end) to track intervals covering each query. For each query, push intervals starting before it and remove intervals that end before it. The top of the heap gives the smallest interval covering the query, or -1 if none.
Code:
intervals.sort()
heap = []
res = {}
i = 0
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
l,r = intervals[i]
heapq.heappush(heap,(r-l+1,r))
i += 1
while heap and heap[0][1] < q:
heapq.heappop(heap)
res[q] = heap[0][0] if heap else -1
return [res[q] for q in queries] ⬆️ Back to Top | 📑 Table of Contents
Problem: Jump Game
Description:
You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.
Return true if you can reach the last index starting from index 0, or false otherwise.
Tip
💡 Trick/Pattern:
Track the furthest reachable index (jump) as you iterate. If the current index exceeds jump, return False. Otherwise, update jump to the maximum of itself and i + nums[i]. If you reach the end, return True.
Code:
jump = 0
for i in range(len(nums)):
if i > jump:
return False
jump = max(jump,i + nums[i])
return True⬆️ Back to Top | 📑 Table of Contents
Problem: Jump Game II
Description:
You are given an array of integers nums, where nums[i] represents the maximum length of a jump towards the right from index i. For example, if you are at nums[i], you can jump to any index i + j where:
j <= nums[i] i + j < nums.length You are initially positioned at nums[0].
Return the minimum number of jumps to reach the last position in the array (index nums.length - 1). You may assume there is always a valid answer.
Tip
💡 Trick/Pattern:
Use a greedy layer-by-layer approach. Track the current range [l, r] of reachable indices. For each layer, find the furthest index reachable (maxi) within that range, then move to the next layer and increment jumps. Repeat until the end is reachable.
Code:
l = r =0
jump = 0
while r < len(nums) - 1:
maxi = 0
for i in range(l,r+1):
maxi = max(maxi,i+nums[i])
l = r + 1
r = maxi
jump+=1
return jump⬆️ Back to Top | 📑 Table of Contents
Problem: Gas Station
Description:
There are n gas stations along a circular route. You are given two integer arrays gas and cost where:
gas[i] is the amount of gas at the ith station. cost[i] is the amount of gas needed to travel from the ith station to the (i + 1)th station. (The last station is connected to the first station) You have a car that can store an unlimited amount of gas, but you begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index such that you can travel around the circuit once in the clockwise direction. If it's impossible, then return -1.
It's guaranteed that at most one solution exists.
Tip
💡 Trick/Pattern:
First, check if the total gas is enough to cover total cost; if not, return -1. Then, iterate through the stations, tracking the current gas balance. If it drops below zero, reset the balance and start the next candidate from the next station. The last reset index is the starting station that can complete the circuit.
Code:
if sum(gas) < sum(cost):
return -1
res = 0
total = 0
for i in range(len(gas)):
total += gas[i] - cost[i]
if total < 0:
total = 0
res = i + 1
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Hand of Straights
Description:
You are given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize.
You want to rearrange the cards into groups so that each group is of size groupSize, and card values are consecutively increasing by 1.
Return true if it's possible to rearrange the cards in this way, otherwise, return false.
Tip
💡 Trick/Pattern:
Check if the hand size is divisible by groupSize. Use a min-heap to start from the smallest card and build consecutive sequences of length groupSize, decrementing counts and removing cards when zero. If any card is missing or out of order, return False; otherwise, True.
Code:
if len(hand) % groupSize:
return False
count = Counter(hand)
heap = list(count.keys())
heapq.heapify(heap)
while heap:
first = heap[0]
for i in range(first,first + groupSize):
if i not in count:
return False
count[i] -= 1
if count[i] == 0:
if i != heap[0]:
return False
heapq.heappop(heap)
return True⬆️ Back to Top | 📑 Table of Contents
Problem: Merge Triplets to Form Target
Description:
You are given a 2D array of integers triplets, where triplets[i] = [ai, bi, ci] represents the ith triplet. You are also given an array of integers target = [x, y, z] which is the triplet we want to obtain.
To obtain target, you may apply the following operation on triplets zero or more times:
Choose two different triplets triplets[i] and triplets[j] and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
- E.g. if triplets[i] = [1, 3, 1] and triplets[j] = [2, 1, 2], triplets[j] will be updated to [max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2].
Return true if it is possible to obtain target as an element of triplets, or false otherwise.
Tip
💡 Trick/Pattern:
Iterate through the triplets that don’t exceed the target in any coordinate. Track the maximum value for each dimension. If the max values match the target, return True; otherwise, False.
Code:
m,n,o = target
max_a = max_b = max_c = 0
for a,b,c in triplets:
if a <= m and b <= n and c <= o:
max_a = max(max_a,a)
max_b = max(max_b,b)
max_c = max(max_c,c)
return [max_a,max_b,max_c] == target⬆️ Back to Top | 📑 Table of Contents
Problem: Partition Labels
Description:
You are given a string s consisting of lowercase english letters.
We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.
Return a list of integers representing the size of these substrings in the order they appear in the string.
Tip
💡 Trick/Pattern:
First, record the last occurrence of each character. Then iterate through the string, expanding the current partition to the furthest last occurrence seen so far. When the current index reaches that end, close the partition, record its size, and start a new one.
Code:
mp = defaultdict(int)
res = []
for i,c in enumerate(s):
mp[c] = i
end = size = 0
for i,c in enumerate(s):
size += 1
end = max(end,mp[c])
if i == end:
res.append(size)
size = 0
return res⬆️ Back to Top | 📑 Table of Contents
Problem: Valid Parenthesis String
Description:
You are given a string s which contains only three types of characters: '(', ')' and '*'.
Return true if s is valid, otherwise return false.
A string is valid if it follows all of the following rules:
Every left parenthesis '(' must have a corresponding right parenthesis ')'. Every right parenthesis ')' must have a corresponding left parenthesis '('. Left parenthesis '(' must go before the corresponding right parenthesis ')'. A '*' could be treated as a right parenthesis ')' character or a left parenthesis '(' character, or as an empty string "".
Tip
💡 Trick/Pattern:
Track the minimum and maximum possible open parentheses while scanning the string. For ( increment both, for ) decrement both, and for * treat it as -1 or +1. If max < 0 return False, and clamp min to 0. At the end, the string is valid if min == 0.
Code:
leftMin,leftMax = 0,0
for c in s:
if c == '(':
leftMin,leftMax = leftMin + 1,leftMax + 1
elif c == ')':
leftMin,leftMax = leftMin - 1,leftMax - 1
else:
leftMin,leftMax = leftMin -1, leftMax + 1
if leftMax < 0:
return False
if leftMin < 0:
leftMin = 0
return leftMin == 0⬆️ Back to Top | 📑 Table of Contents
Problem: Maximum Subarray
Description:
Given an array of integers nums, find the subarray with the largest sum and return the sum.
A subarray is a contiguous non-empty sequence of elements within an array.
Tip
💡 Trick/Pattern:
Iterate through the array, maintaining the current subarray sum. Add each number to it and update the maximum seen so far. If the sum becomes negative, reset it to 0. The maximum tracked is the answer.
⬆️ Back to Top | 📑 Table of Contents
Problem: Network Delay Time
Description:
You are given a network of n directed nodes, labeled from 1 to n. You are also given times, a list of directed edges where times[i] = (ui, vi, ti).
ui is the source node (an integer from 1 to n) vi is the target node (an integer from 1 to n) ti is the time it takes for a signal to travel from the source to the target node (an integer greater than or equal to 0). You are also given an integer k, representing the node that we will send a signal from.
Return the minimum time it takes for all of the n nodes to receive the signal. If it is impossible for all the nodes to receive the signal, return -1 instead.
Tip
💡 Trick/Pattern:
Build the graph as an adjacency list. Use a min-heap (Dijkstra’s algorithm) to always visit the node with the smallest accumulated time. Track visited nodes and update the current time. If all nodes are reached, return the maximum time; otherwise, return -1.
Code:
adj = defaultdict(list)
for u,v,t in times:
adj[u].append([v,t])
vis = set()
heap = [(0,k)]
t = 0
while heap:
cost, i = heapq.heappop(heap)
if i in vis:
continue
vis.add(i)
t = max(t,cost)
for nei, neiCost in adj[i]:
if nei not in vis:
heapq.heappush(heap,[cost + neiCost,nei])
return t if len(vis) == n else -1⬆️ Back to Top | 📑 Table of Contents
Problem: Reconstruct Flight Path
Description:
You are given a list of flight tickets tickets where tickets[i] = [from_i, to_i] represent the source airport and the destination airport.
Each from_i and to_i consists of three uppercase English letters.
Reconstruct the itinerary in order and return it.
All of the tickets belong to someone who originally departed from "JFK". Your objective is to reconstruct the flight path that this person took, assuming each ticket was used exactly once.
If there are multiple valid flight paths, return the lexicographically smallest one.
For example, the itinerary ["JFK", "SEA"] has a smaller lexical order than ["JFK", "SFO"]. You may assume all the tickets form at least one valid flight path.
Tip
💡 Trick/Pattern:
Build a graph of flights and sort destinations in reverse lexical order. Use DFS, always taking the last available destination (smallest lexically) and append nodes after visiting all outgoing flights. Reverse the result at the end to get the correct itinerary.
Code:
adj = defaultdict(list)
for u,v in tickets:
adj[u].append(v)
for src in adj:
adj[src].sort(reverse=True)
res = []
def dfs(src):
while adj[src]:
dfs(adj[src].pop())
res.append(src)
dfs("JFK")
return res[::-1]⬆️ Back to Top | 📑 Table of Contents
Problem: Min Cost to Connect Points
Description:
You are given a 2-D integer array points, where points[i] = [xi, yi]. Each points[i] represents a distinct point on a 2-D plane.
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between the two points, i.e. |xi - xj| + |yi - yj|.
Return the minimum cost to connect all points together, such that there exists exactly one path between each pair of points.
Tip
💡 Trick/Pattern:
Treat points as a complete graph with Manhattan distances as edge weights. Use Prim’s algorithm with a min-heap: start from any point, always pick the smallest edge connecting a new point, add its cost, and repeat until all points are connected. The total cost is the MST.
Code:
n = len(points)
adj = defaultdict(list)
for i in range(n):
x1,y1 = points[i]
for j in range(i+1,n):
x2,y2 = points[j]
dest = abs(x2-x1) + abs(y2-y1)
adj[i].append([dest,j])
adj[j].append([dest,i])
heap = [[0,0]]
vis = set()
res = 0
while len(vis) < n:
cost,i = heapq.heappop(heap)
if i in vis:
continue
vis.add(i)
res += cost
for neiCost,nei in adj[i]:
if nei not in vis:
heapq.heappush(heap,[neiCost,nei])
return res⬆️ Back to Top | 62BF 📑 Table of Contents
Problem: Swim in Rising Water
Description:
You are given a square 2-D matrix of distinct integers grid where each integer grid[i][j] represents the elevation at position (i, j).
Rain starts to fall at time = 0, which causes the water level to rise. At time t, the water level across the entire grid is t.
You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time t.
Starting from the top left square (0, 0), return the minimum amount of time it will take until it is possible to reach the bottom right square (n - 1, n - 1).
Tip
💡 Trick/Pattern:
Treat the grid as a weighted graph where each cell’s value is the earliest time it can be entered. Use a min-heap (Dijkstra-like approach) starting from (0,0), always moving to the neighbor with the smallest maximum elevation along the path. Stop when reaching the bottom-right; the maximum value along that path is the answer.
Code:
n = len(grid)
vis = set()
heap = [[grid[0][0],0,0]]
vis.add((0,0))
def expand(r,c,t):
if r < 0 or c < 0 or r == n or c == n or (r,c) in vis:
return
vis.add((r,c))
heapq.heappush(heap,[max(t,grid[r][c]),r,c])
while heap:
t,r,c = heapq.heappop(heap)
if r == n-1 and c == n-1:
return t
expand(r+1,c,t)
expand(r-1,c,t)
expand(r,c+1,t)
expand(r,c-1,t)⬆️ Back to Top | 📑 Table of Contents
Problem: Alien Dictionary
Description:
There is a foreign language which uses the latin alphabet, but the order among letters is not "a", "b", "c" ... "z" as in English.
You receive a list of non-empty strings words from the dictionary, where the words are sorted lexicographically based on the rules of this new language.
Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return any of them.
A string a is lexicographically smaller than a string b if either of the following is true:
The first letter where they differ is smaller in a than in b. a is a prefix of b and a.length < b.length.
Tip
💡 Trick/Pattern:
Build a graph of character dependencies by comparing consecutive words. Detect invalid order if a longer word comes before its prefix. Then, use DFS with cycle detection to perform a topological sort. If a cycle exists, return ""; otherwise, reverse the DFS result for the character order.
Code:
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1,w2 = words[i],words[i+1]
minLen = min(len(w1),len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break
vis = {}
res = []
def dfs(c):
if c in vis:
return vis[c]
vis[c] = True
for nei in adj[c]:
if dfs(nei):
return True
vis[c] = False
res.append(c)
for c in adj:
if dfs(c):
return ""
return "".join(res[::-1])⬆️ Back to Top | 📑 Table of Contents
Problem: Cheapest Flights Within K Stops
Description:
There are n airports, labeled from 0 to n - 1, which are connected by some flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] represents a one-way flight from airport from_i to airport to_i with cost price_i. You may assume there are no duplicate flights and no flights from an airport to itself.
You are also given three integers src, dst, and k where:
src is the starting airport dst is the destination airport src != dst k is the maximum number of stops you can make (not including src and dst) Return the cheapest price from src to dst with at most k stops, or return -1 if it is impossible.
Tip
💡 Trick/Pattern:
Use a modified Bellman-Ford approach: track the minimum cost to each city with up to k stops. In each iteration, update costs for all flights using a temporary copy to avoid overwriting the current layer. After k+1 iterations, the cost to the destination is the answer, or -1 if unreachable.
Code:
prices = [float('inf')] * n
prices[src] = 0
for i in range(k+1):
tmp = prices.copy()
for s,d,p in flights:
if prices[s] == float('inf'):
continue
if prices[s] + p < tmp[d]:
tmp[d] = prices[s] + p
prices = tmp
return -1 if prices[dst] == float('inf') else prices[dst] ⬆️ Back to Top | 📑 Table of Contents
Problem: Unique Paths
Description:
There is an m x n grid where you are allowed to move either down or to the right at any point in time.
Given the two integers m and n, return the number of possible unique paths that can be taken from the top-left corner of the grid (grid[0][0]) to the bottom-right corner (grid[m - 1][n - 1]).
You may assume the output will fit in a 32-bit integer.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization: from each cell, recursively count paths by moving right or down. Cache results to avoid recomputation. The number of unique paths from (0,0) to (m-1,n-1) is the final answer.
⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Common Subsequence
Description:
Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.
A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.
For example, "cat" is a subsequence of "crabt". A common subsequence of two strings is a subsequence that exists in both strings.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization: for each pair of indices (i,j), if characters match, take 1 + LCS(i+1,j+1); otherwise, take the max of skipping a character in either string. Cache results to avoid recomputation. The final answer is LCS(0,0).
⬆️ Back to Top | 📑 Table of Contents
Problem: Best Time to Buy and Sell Stock with Cooldown
Description:
You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.
You may buy and sell one NeetCoin multiple times with the following restrictions:
After you sell your NeetCoin, you cannot buy another one on the next day (i.e., there is a cooldown period of one day). You may only own at most one NeetCoin at a time. You may complete as many transactions as you like.
Return the maximum profit you can achieve.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization. Track the state (index, canBuy). At each day, either do nothing (cooldown) or buy/sell depending on the state. After selling, skip one day due to the cooldown. The maximum profit starts from (0, True).
Code:
dp ={}
def f(i,buy):
if i >= len(prices):
return 0
if (i, buy) in dp:
return dp[(i, buy)]
cooldown = f(i + 1, buy)
if buy:
buying = f(i+1,not buy) - prices[i]
dp[(i,buy)] = max(buying,cooldown)
else:
sell = f(i+2,not buy) + prices[i]
dp[(i,buy)] = max(sell,cooldown)
return dp[(i,buy)]
return f(0,True)⬆️ Back to Top | 📑 Table of Contents
Problem: Coin Change II
Description:
You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.
Return the number of distinct combinations that total up to amount. If it's impossible to make up the amount, return 0.
You may assume that you have an unlimited number of each coin and that each value in coins is unique.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization: at each coin index i and remaining amount s, either take the coin (stay at i and reduce s) or skip it (move to i+1). Sum both choices. Base cases: 0 amount → 1 way, negative amount → 0 ways.
⬆️ Back to Top | 📑 Table of Contents
Problem: Target Sum
Description:
You are given an array of integers nums and an integer target.
For each number in the array, you can choose to either add or subtract it to a total sum.
For example, if nums = [1, 2], one possible sum would be "+1-2=-1". If nums=[1,1], there are two different ways to sum the input numbers to get a sum of 0: "+1-1" and "-1+1".
Return the number of different ways that you can build the expression such that the total sum equals target.
Example 1:
Tip
💡 Trick/Pattern:
Use top-down DP with memoization: at each index i and current sum s, you can either add or subtract nums[i]. Cache (i,s) to avoid recomputation. At the end, return the total ways to reach target starting from (0,0).
Code:
dp = {}
def f(i,s):
if i == len(nums):
return 1 if s == target else 0
if (i,s) in dp:
return dp[(i,s)]
add = f(i+1,s + nums[i])
sub = f(i+1,s - nums[i])
dp[(i,s)] = add + sub
return dp[(i,s)]
return f(0,0)⬆️ Back to Top | 📑 Table of Contents
Problem: Interleaving String
Description:
You are given three strings s1, s2, and s3. Return true if s3 is formed by interleaving s1 and s2 together or false otherwise.
Interleaving two strings s and t is done by dividing s and t into n and m substrings respectively, where the following conditions are met
|n - m| <= 1, i.e. the difference between the number of substrings of s and t is at most 1. s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm Interleaving s and t is s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ... You may assume that s1, s2 and s3 consist of lowercase English letters.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization. Track indices (i,j) in s1 and s2; the corresponding index in s3 is i+j. At each step, try to match the next character from either s1 or s2. Cache results to avoid recomputation. Return True if you can reach the end of both strings.
Code:
if len(s3) != len(s1) + len(s2):
return False
dp = {}
def dfs(i, j):
if (i, j) in dp:
return dp[(i, j)]
if i == len(s1) and j == len(s2):
return True
k = i + j
ans = False
if i < len(s1) and s1[i] == s3[k]:
ans = dfs(i + 1, j)
if not ans and j < len(s2) and s2[j] == s3[k]:
ans = dfs(i, j + 1)
dp[(i, j)] = ans
return ans
return dfs(0, 0)⬆️ Back to Top | 📑 Table of Contents
Problem: Longest Increasing Path in Matrix
Description:
You are given a 2-D grid of integers matrix, where each integer is greater than or equal to 0.
Return the length of the longest strictly increasing path within matrix.
From each cell within the path, you can move either horizontally or vertically. You may not move diagonally
Tip
💡 Trick/Pattern:
Use DFS with memoization. From each cell, recursively explore all four directions only if the next value is larger. Cache the longest path starting from each cell to avoid recomputation. The answer is the maximum path length among all cells.
Code:
m,n = len(matrix),len(matrix[0])
dp = {}
def dfs(r,c,prev):
if r < 0 or c < 0 or r == m or c == n:
return 0
if prev >= matrix[r][c]:
return 0
res = 1 + max(dfs(r+1,c,matrix[r][c]),dfs(r-1,c,matrix[r][c]),dfs(r,c+1,matrix[r][c]),dfs(r,c-1,matrix[r][c]))
dp[(r,c)] = res
return res
for i in range(m):
for j in range(n):
dfs(i,j,float('-inf'))
return max(dp.values())⬆️ Back to Top | 📑 Table of Contents
Problem: Distinct Subsequences
Description:
You are given two strings s and t, both consisting of english letters.
Return the number of distinct subsequences of s which are equal to t.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization. At each index (i,j) in s and t, if the characters match, you can either use it or skip it. If they don’t match, skip the character in s. The total ways to form t from s start from (0,0).
Code:
dp = {}
def f(i,j):
if j == len(t):
return 1
if i == len(s):
return 0
if (i,j) in dp:
return dp[(i,j)]
if s[i] == t[j]:
dp[(i,j)] = f(i+1,j+1) + f(i+1,j)
else:
dp[(i,j)] = f(i+1,j)
return dp[(i,j)]
return f(0,0)⬆️ Back to Top | 📑 Table of Contents
Problem: Edit Distance
Description:
You are given two strings word1 and word2, each consisting of lowercase English letters.
You are allowed to perform three operations on word1 an unlimited number of times:
Insert a character at any position Delete a character at any position Replace a character at any position Return the minimum number of operations to make word1 equal word2.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization. At each pair of indices (i,j), if characters match, move both forward. Otherwise, consider replace, insert, or delete and take the minimum +1. The answer is the minimum edits from (0,0) to transform word1 into word2.
Code:
m,n = len(word1),len(word2)
dp = {}
def f(i,j):
if i == m:
return n - j
if j == n:
return m - i
if (i,j) in dp:
return dp[(i,j)]
if word1[i] == word2[j]:
dp[(i,j)] = f(i+1,j+1)
else:
res = min(f(i+1,j+1),f(i,j+1),f(i+1,j))
dp[(i,j)] = 1 + res
return dp[(i,j)]
return f(0,0) ⬆️ Back to Top | 📑 Table of Contents
Problem: Burst Balloons
Description:
You are given an array of integers nums of size n. The ith element represents a balloon with an integer value of nums[i]. You must burst all of the balloons.
If you burst the ith balloon, you will receive nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then assume the out of bounds value is 1.
Return the maximum number of coins you can receive by bursting all of the balloons.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization on intervals. For each subarray (l,r), try bursting each balloon last in that range. The coins gained are nums[l-1] * nums[i] * nums[r+1] plus the results of left and right subarrays. Return the maximum coins for (1, n) after padding the array with 1’s at both ends.
Code:
nums = [1] + nums + [1]
dp = {}
def dfs(l,r):
if l > r:
return 0
if (l,r) in dp:
return dp[(l,r)]
dp[(l,r)] = 0
for i in range(l,r+1):
coins = nums[l-1] * nums[i] * nums[r+1]
coins += dfs(l,i-1) + dfs(i+1,r)
dp[(l,r)] = max(dp[(l,r)],coins)
return dp[(l,r)]
return dfs(1,len(nums)-2)⬆️ Back to Top | 📑 Table of Contents
Problem: Regular Expression Matching
Description:
You are given an input string s consisting of lowercase english letters, and a pattern p consisting of lowercase english letters, as well as '.', and '*' characters.
Return true if the pattern matches the entire input string, otherwise return false.
'.' Matches any single character '*' Matches zero or more of the preceding element.
Tip
💡 Trick/Pattern:
Use top-down DP with memoization. At each (i,j), check if characters match (s[i] == p[j] or .). Handle * by either skipping it or using it if matched. Otherwise, move both pointers forward if they match. Cache results to avoid recomputation.
Code:
dp = {}
def dfs(i,j):
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False
if (i,j) in dp:
return dp[(i,j)]
match = i < len(s) and (s[i] == p[j] or p[j] == '.')
if (j+1) < len(p) and p[j+1] == "*":
dp[(i,j)] = dfs(i,j + 2) or (match and dfs(i + 1,j))
return dp[(i,j)]
if match:
dp[(i,j)] = dfs(i+1,j+1)
return dp[(i,j)]
dp[(i,j)] = False
return dp[(i,j)]
return dfs(0,0)⬆️ Back to Top | 📑 Table of Contents
Problem: Single Number
Description:
You are given a non-empty array of integers nums. Every integer appears twice except for one.
Return the integer that appears only once.
Tip
💡 Trick/Pattern:
Use bitwise XOR: XOR all numbers together. Pairs cancel out because n ^ n = 0, leaving only the unique number.
⬆️ Back to Top | 📑 Table of Contents
Problem: Number of One Bits
Description:
You are given an unsigned integer n. Return the number of 1 bits in its binary representation.
You may assume n is a non-negative integer which fits within 32-bits.
Tip
💡 Trick/Pattern:
Iterate through the bits of n, incrementing a counter whenever the last bit is 1 (n & 1). Right-shift n until it becomes 0. The counter is the number of 1’s in the binary representation.
⬆️ Back to Top | 📑 Table of Contents
Problem: Counting Bits
Description:
Given an integer n, count the number of 1's in the binary representation of every number in the range [0, n].
Return an array output where output[i] is the number of 1's in the binary representation of i.
Tip
💡 Trick/Pattern:
For each number from 0 to n, count the number of 1’s in its binary representation by checking each bit (temp & 1) and right-shifting until 0. Append the count to the result list.
⬆️ Back to Top | 📑 Table of Contents
Problem: Reverse Bits
Description:
Given a 32-bit unsigned integer n, reverse the bits of the binary representation of n and return the result.
Tip
💡 Trick/Pattern:
Extract each of the 32 bits of n using (n >> i) & 1 or bitmasking, store them in a list, reverse the list, and reconstruct the number by summing 2^i for each bit that is 1.
⬆️ Back to Top | 📑 Table of Contents
Problem: Missing Number
Description:
Given an array nums containing n integers in the range [0, n] without any duplicates, return the single number in the range that is missing from nums.
Tip
💡 Trick/Pattern:
Use bitwise XOR: XOR all indices and all numbers in the array together. Since duplicates cancel out (n ^ n = 0), the result is the missing number.
⬆️ Back to Top | 📑 Table of Contents
Problem: Sum of Two Integers
Description:
Given two integers a and b, return the sum of the two integers without using the + and - operators.
Tip
💡 Trick/Pattern:
Use bitwise operations: XOR a ^ b gives the sum without carry, AND a & b shifted left gives the carry. Repeat until there’s no carry. Handle 32-bit signed integers with masking to return the correct result.
⬆️ Back to Top | 📑 Table of Contents
Problem: Reverse Integer
Description:
You are given a signed 32-bit integer x.
Return x after reversing each of its digits. After reversing, if x goes outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0 instead.
Solve the problem without using integers that are outside the signed 32-bit integer range
Tip
💡 Trick/Pattern:
Convert the integer to a string, reverse it, and restore the sign. Return 0 if the reversed number overflows 32-bit integer range.
⬆️ Back to Top | 📑 Table of Contents
Problem: Rotate Image
Description:
Given a square n x n matrix of integers matrix, rotate it by 90 degrees clockwise.
You must rotate the matrix in-place. Do not allocate another 2D matrix and do the rotation.
Tip
💡 Trick/Pattern:
Reverse the matrix vertically, then transpose it by swapping matrix[i][j] with matrix[j][i] for j > i. This rotates the matrix 90° clockwise in-place.
⬆️ Back to Top | 📑 Table of Contents
Problem: Spiral Matrix
Description:
Given an m x n matrix of integers matrix, return a list of all elements within the matrix in spiral order.
Tip
💡 Trick/Pattern:
Use recursive layer-by-layer traversal. At each layer, move in the current direction for the number of steps, then rotate the direction clockwise and reduce the row/column counts. Collect elements until all layers are traversed.
⬆️ Back to Top | 📑 Table of Contents
Problem: Set Matrix Zeroes
Description:
Given an m x n matrix of integers matrix, if an element is 0, set its entire row and column to 0's.
You must update the matrix in-place.
Tip
💡 Trick/Pattern:
First, scan the matrix to record rows and columns that contain zeros. Then, iterate again and set all elements in those rows and columns to 0. This handles zero propagation efficiently.
⬆️ Back to Top | 📑 Table of Contents
Problem: Non-Cyclical Number
Description:
A non-cyclical number is an integer defined by the following algorithm:
Given a positive integer, replace it with the sum of the squares of its digits. Repeat the above step until the number equals 1, or it loops infinitely in a cycle which does not include 1. If it stops at 1, then the number is a non-cyclical number. Given a positive integer n, return true if it is a non-cyclical number, otherwise return false.
Tip
💡 Trick/Pattern:
Use Floyd’s cycle detection (slow & fast pointers) on the sequence of sums of squares of digits. If the fast pointer reaches 1, the number is happy; if slow meets fast, a cycle exists and it’s not happy.
⬆️ Back to Top | 📑 Table of Contents
Problem: Plus One
Description:
You are given an integer array digits, where each digits[i] is the ith digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.
Return the digits of the given integer after incrementing it by one.
Tip
💡 Trick/Pattern:
Start from the last digit and handle carry. If a digit is less than 9, increment and stop. If it’s 9, set to 0 and move left. If you reach the start, insert 1 at the front.
⬆️ Back to Top | 📑 Table of Contents
Problem: Pow(x, n)
Description:
Pow(x, n) is a mathematical function to calculate the value of x raised to the power of n (i.e., x^n).
Given a floating-point value x and an integer value n, implement the myPow(x, n) function, which calculates x raised to the power n.
You may not use any built-in library functions.
Tip
💡 Trick/Pattern:
Use fast exponentiation (divide & conquer). Recursively compute x^(n//2) and square it. Multiply by x if n is odd. For negative n, return 1 / x^|n|.
⬆️ Back to Top | 📑 Table of Contents
Problem: Multiply Strings
Description:
You are given two strings num1 and num2 that represent non-negative integers.
Return the product of num1 and num2 in the form of a string.
Assume that neither num1 nor num2 contain any leading zero, unless they are the number 0 itself.
Note: You can not use any built-in library to convert the inputs directly into integers.
Tip
💡 Trick/Pattern:
Convert both strings to integers, multiply them directly, and convert the result back to a string.
⬆️ Back to Top | 📑 Table of Contents
Problem: Detect Squares
Description:
You are given a stream of points consisting of x-y coordinates on a 2-D plane. Points can be added and queried as follows:
Add - new points can be added to the stream into a data structure. Duplicate points are allowed and should be treated as separate points. Query - Given a single query point, count the number of ways to choose three additional points from the data structure such that the three points and the query point form a square. The square must have all sides parallel to the x-axis and y-axis, i.e. no diagonal squares are allowed. Recall that a square must have four equal sides. Implement the CountSquares class:
CountSquares() Initializes the object. void add(int[] point) Adds a new point point = [x, y]. int count(int[] point) Counts the number of ways to form valid squares with point point = [x, y] as described above.
Tip
💡 Trick/Pattern:
Store all points with their counts. To count squares with a query point (px, py), iterate through existing points and check if they can form a diagonal of a square (abs(px - x) == abs(py - y) and not on the same row/column). Multiply counts of the other two corners to get total squares.
Code:
class CountSquares:
def __init__(self):
self.ptsCount = defaultdict(int)
self.pts = []
def add(self, point: List[int]) -> None:
self.ptsCount[tuple(point)] += 1
self.pts.append(point)
def count(self, point: List[int]) -> int:
res = 0
px, py = point
for x, y in self.pts:
if (abs(py - y) != abs(px - x)) or x == px or y == py:
continue
res += self.ptsCount[(x, py)] * self.ptsCount[(px, y)]
return res⬆️ Back to Top | 📑 Table of Contents
- Total Problems: 150
- Categories: 18
- Progress: 100% of NeetCode 150
Made with ❤️ by Pradyum Mistry