Neetcode 150 Flashcards
136.Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
Constraints:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
Each element in the array appears twice except for one element which appears only once
Pattern: Bit Manipulation
Brute Force:
Iterate through numbers
if num is not in set:
add it to set and add in a total sum
else:
remove that number from total
return total
Complexity:
Time: O(n) Space: O(n) → uses a hash map
More optimal approach: Sort it and compare neighbors
Time: O(n log n) → due to sorting
Space: O(1) if sorting in place
Optimal Approach:
Loop through all elements and xor them one by one.
Whats left if the single integer
Time: O(n) ✅
Space: O(1) ✅
Number of 1 Bits
Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
Example 2:
Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
Constraints:
1 <= n <= 231 - 1
Follow up: If this function is called many times, how would you optimize it?
Pattern: Bit Manipulation
Brute Force:
Intuition: You can code the method to get binary numbers through decimal numbers by the standard method of division and getting the modulus.
Psuedo Code:
First take a list and append to it after % 2, then floor divide the number.
In another loop, just count the number of ones.
⏱️ Complexity:
Time: O(log n) because we're dividing by 2 each time (same as checking each bit) Space: O(1)
More optimized solution: Iterate through all 32 bits and count how many are set to 1.
Code:
def hammingWeight(n):
count = 0
while n:
count += n & 1 # check least significant bit
n»_space;= 1 # right shift
return count
Time: O(32) = O(1) constant time, because integers are ≤ 32-bit
Space: O(1)
Optimized solution:
Intuition : n &= (n - 1) solution. Brian Kernighan’s Algorithm
Time: O(k), where k is the number of set bits → much faster when n is sparse
Space: O(1)
Psuedo Code:
ans = 0
while n:
n &= (n - 1)
ans += 1
return ans
- Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 –> 0
1 –> 1
2 –> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101
Constraints:
0 <= n <= 105
Follow up:
It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
Pattern: Bit Manipulation
Brute force:
Intuition: You could loop through every single element and do another loop which will XOR all the numbers until they are zero. But this is O(n^2) time complexity.
Optimized solution: You can use DP for this. maintain a 1D dp.
Intuition: There is repetition in the bits in a periodic fashion. What you can do is build a dp of the size n+ 1 with all elements 0. Then maintain an offset variable, as you get 2,4,8,16, etc (powers of 2, so you can keep multiplying them by 2 to get the next one), increase the offset. And for each i, do dp[i] = 1 + dp[i - offset]
psuedo code:
dp = [0] * (n + 1)
offset = 1
loop through 1 , n + 1 (dp[0] is already 0)
if offset * 2 == i:
offset = i
dp [i] = 1 + dp[i - offset]
return dp
Time and Space Complexity:
Time: O(n) → one pass, constant time per i Space: O(n) for result array
- Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.
Example 1:
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
Constraints:
The input must be a binary string of length 32
Follow up: If this function is called many times, how would you optimize it?
Pattern: Bit Manipulation
Intuition: Here, you need to right shift every bit to the units place and take every bit by anding it with 1, then put it back to its original place and ‘OR’ it with a result.
Code:
res = 0
for i in range (0,32):
bits = (n»_space; i) & 1
res = res | (bits «_space;(31 - i))
return res
⏱️ Time and Space Complexity
Time: O(32) = O(1) Space: O(1)
- Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
Pattern: Bit Manipulation
Brute Force:
Idea:
Check every number from 0 to n and see which one is missing.
Complexity:
Time: O(n) Space: O(n) → uses a set
❌ Violates space constraint in follow-up
Optimized intuition:
For a single pass, xor the number itself in the result along with the i index that you are using. that will ensure that the missing number will remain in res as all others will become zero.
psuedo code:
loop through i to nums.length
res ^= 1
res ^= nums[i]
Time & Space:
Time: O(n) Space: O(1)
- Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = 2, b = 3
Output: 5
Constraints:
-1000 <= a, b <= 1000
Pattern: Bit Manipulation
Intuition: You need to xor both the numbers, then deal with the carries. After xoring, they update b with (a&b) «_space;1, and keep xoring until b becomes zero. This ensures that all carries are taken care of.
psuedo code:
while b is not 0:
temp = (a & b) «_space;1;
a = a ^ b
b = temp
⏱️ Time and Space Complexity
Time: O(1) in practice (fixed 32-bit loop, at most 32 iterations) Space: O(1)
48 . Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
Pattern: Math and Geometry
Intuition: Think of processing all of the outer layer at once. There are multiple sub boxes in there. then think about what box where go where and there would be an offset which will be used. After one go, update the variables to go in the inner layer.
Code:
left = 0
right = len(matrix[0]) - 1
top = 0
bottom = len(matrix) - 1
offset = 0
while left < right:
for offset in range (right - left):
temp = matrix[top][left + offset]
matrix[top][left + offset] = matrix[bottom - offset][left]
matrix[bottom - offset][left] = matrix[bottom][right - offset]
matrix[bottom][right - offset] = matrix[top + offset][right]
matrix[top + offset][right] = temp
left = left + 1
right = right - 1
top = top + 1
bottom = bottom - 1
- Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Pattern: Math and Geometry
Intuition: Maintain top,bottom,left,right. Go through a row/column then update that variable accordingly. dont forget the condition in the middle to break, which doesnt come intuitively.
Code:
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
left,right = 0, len(matrix[0]) - 1
top, bottom = 0, len(matrix) - 1
res = []
while left < right and top < bottom:
for i in range (left,right):
res.append(matrix[top][i])
print(matrix[top][i])
left = left + 1
for i in range(top,bottom + 1):
res.append(matrix[i][right])
print(matrix[i][right])
right = right - 1
if left < right and top < bottom:
break
for i in range(right,left-2,-1):
res.append(matrix[bottom][i])
print(matrix[bottom][i])
bottom = bottom - 1
for i in range(bottom,top-1,-1):
res.append(matrix[i][left-1])
print(matrix[i][left-1])
left = left + 1
return res
Time: O(m × n)
Space: O(1) extra space (excluding output list)
- Set Matrix Zeroes
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
Follow up:
A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Pattern: Math and Geometry
Brute force: Make a deep copy, find all zeros and set corresponding rows and columns in the copy.
Time & Space:
Time: O(m × n × (m + n)) worst-case Space: O(m × n)
Better approach: Use two arrays, one for rows and one for columns, then apply zero in the second pass.
Time & Space:
Time: O(m × n) Space: O(m + n)
Optimized approach:
Intuition: Use the first row and column to maintain if there are zeros in there. For the first row and column, it can cause issues, because a single cell exists for row 0 and column 0, so maintain two separate variables for that.
Code:
m = len(matrix)
n = len(matrix[0])
first_row_has_zero = False
first_col_has_zero = False
# iterate through matrix to mark the zero row and cols
for row in range(m):
for col in range(n):
if matrix[row][col] == 0:
if row == 0:
first_row_has_zero = True
if col == 0:
first_col_has_zero = True
matrix[row][0] = matrix[0][col] = 0
# iterate through matrix to update the cell to be zero if it's in a zero row or col
for row in range(1, m):
for col in range(1, n):
matrix[row][col] = 0 if matrix[0][col] == 0 or matrix[row][0] == 0 else matrix[row][col]
# update the first row and col if they're zero
if first_row_has_zero:
for col in range(n):
matrix[0][col] = 0
if first_col_has_zero:
for row in range(m):
matrix[row][0] = 0
You said:
268. Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
ChatGPT said:
Let’s walk through the solution to Leetcode 268. Missing Number step-by-step, optimizing progressively:
🔹 Problem Summary
You’re given an array nums of length n containing distinct integers from 0 to n (inclusive range), but one number in this range is missing. Your task is to find the missing number.
✅ Constraints Recap
All nums[i] are unique nums contains n numbers out of the range [0, n], so exactly one number is missing Must find the missing number
✅ Step 1: Naive Approach (Brute Force)
Idea:
Use a hash set to store all elements and check from 0 to n which one is missing.
Code:
def missingNumber(nums):
num_set = set(nums)
for i in range(len(nums) + 1):
if i not in num_set:
return i
Time & Space:
Time: O(n) Space: O(n) for the set
Why it’s naive:
Uses extra space proportional to input size (O(n)), which violates the follow-up constraint.
✅ Step 2: Intermediate Optimization (Sorting)
Idea:
Sort the array and find the first index i where nums[i] != i.
Code:
def missingNumber(nums):
nums.sort()
for i in range(len(nums)):
if nums[i] != i:
return i
return len(nums)
Time & Space:
Time: O(n log n) for sorting Space: O(1) if sorting in-place
Why it’s better:
Reduces space, but time is now worse than optimal O(n) for this problem.
✅ Step 3: Optimal Solution (O(n) time, O(1) space)
✅ Method 1: Sum Formula Trick (Arithmetic Series)
Idea:
Sum of numbers from 0 to n is n*(n+1)//2 Subtract sum of all elements in nums from this expected sum
Code:
def missingNumber(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
Time & Space:
Time: O(n) Space: O(1)
Why it works:
Uses mathematical property of sum to find the missing value directly.
✅ Method 2: Bit Manipulation (XOR Trick)
Idea:
XOR all numbers from 0 to n and all numbers in nums Duplicate values cancel out, leaving the missing number
Code:
def missingNumber(nums):
n = len(nums)
xor = 0
for i in range(n + 1):
xor ^= i
for num in nums:
xor ^= num
return xor
Time & Space:
Time: O(n) Space: O(1)
Why it’s clever:
No math overflows, no extra space, and constant time operations per element.
🔚 Final Recommendation
Use the XOR trick or the sum formula trick for optimal performance:
Sum trick is intuitive and fast XOR trick is elegant and avoids integer overflow in languages with fixed-size integers
Would you like to see this extended to finding two missing numbers, or how this fits into similar “missing element” problems?
You said:
54. Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
ChatGPT said:
Let’s solve Leetcode 54. Spiral Matrix in progressive steps from naive to optimal.
🔹 Problem Summary
You are given a 2D m x n matrix. Traverse it in spiral order (clockwise) and return the elements in that order as a list.
✅ Step 1: Naive Idea (Simulation with visited matrix)
Idea:
Simulate movement in 4 directions (right → down → left → up) and mark visited cells using a boolean matrix.
Code:
def spiralOrder(matrix):
m, n = len(matrix), len(matrix[0])
visited = [[False] * n for _ in range(m)]
result = []
# Directions: right, down, left, up
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
dir_idx = 0
r = c = 0
for _ in range(m * n):
result.append(matrix[r][c])
visited[r][c] = True
# Calculate next position
nr, nc = r + dirs[dir_idx][0], c + dirs[dir_idx][1]
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
r, c = nr, nc
else:
# Change direction
dir_idx = (dir_idx + 1) % 4
r += dirs[dir_idx][0]
c += dirs[dir_idx][1]
return result
Time & Space:
Time: O(m × n) Space: O(m × n) for the visited matrix
Why it’s naive:
Requires extra space to track visited cells, even though we can avoid it by adjusting bounds.
✅ Step 2: Optimal Solution (Layer-by-layer traversal)
Idea:
Keep four pointers: top, bottom, left, and right. Traverse each layer of the matrix in spiral order and then shrink the boundaries inward.
Code:
def spiralOrder(matrix):
result = []
if not matrix:
return result
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Traverse from left to right
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Traverse down
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
if top <= bottom:
# Traverse from right to left
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
if left <= right:
# Traverse up
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
Time & Space:
Time: O(m × n) Space: O(1) extra space (excluding output list)
✅ Summary of Optimization
Approach Time Space Notes
Simulation with visited O(m×n) O(m×n) Easy to understand, uses extra space
Boundary shrinking O(m×n) O(1) Optimal, clean and elegant
Would you like a visual walkthrough or see how to generalize this to spiral matrix II (filling a matrix)?
You said:
73. Set Matrix Zeroes
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
Follow up:
A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
ChatGPT said:
Let’s solve Leetcode 73. Set Matrix Zeroes in progressive levels of optimization—from intuitive to optimal with constant space.
🔹 Problem Summary
Given an m x n matrix, if an element is 0, set its entire row and column to 0 — and do this in-place.
✅ Step 1: Naive Approach — Use an Extra Matrix
Idea:
Make a deep copy of the matrix, find all zeroes, and set corresponding rows and columns in the copy.
Code:
import copy
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
copy_matrix = copy.deepcopy(matrix)
for i in range(m):
for j in range(n):
if copy_matrix[i][j] == 0:
for k in range(n): matrix[i][k] = 0
for k in range(m): matrix[k][j] = 0
Time & Space:
Time: O(m × n × (m + n)) worst-case Space: O(m × n)
Why it’s naive:
Uses full space for a copy, and time is inefficient.
✅ Step 2: Improved Approach — Use O(m + n) Space
Idea:
Use two marker arrays: one for rows, one for columns. Mark rows/columns to zero, then apply zeroing in a second pass.
Code:
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
rows, cols = set(), set()
# First pass: record which rows and columns to zero
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
# Second pass: apply zeroing
for i in range(m):
for j in range(n):
if i in rows or j in cols:
matrix[i][j] = 0
Time & Space:
Time: O(m × n) Space: O(m + n)
Why it’s better:
Avoids full copy, but still uses extra space for bookkeeping.
✅ Step 3: Optimal Approach — Constant Space O(1)
Key Insight:
Use first row and first column of the matrix as markers!
Steps:
Use first row to mark columns, first column to mark rows that should be zeroed. Store separately whether the first row or column itself should be zeroed (to avoid conflicts). Traverse matrix again to apply zeroing based on markers.
Code:
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# Mark rows and columns
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Apply marks (excluding first row/col)
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Handle first row
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
# Handle first column
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
Time & Space:
Time: O(m × n) Space: O(1) ✅ in-place with no extra space
- Plus One
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.
Increment the large integer by one and return the resulting array of digits.
Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
Example 3:
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].
Constraints:
1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0’s.
Pattern: Math and Geometry
Intuition: Go through the elements in reverse.
First store it in temp and calculate what the carry might be. then check if temp is 9, what the digit is going to be updated to. Finally, if there is an extra carry, add it to the very first index.
Code:
carry = 0
for loop in reverse
if i == len(digits) - 1:
temp = digits[i] + 1
else:
temp = digits[i] + carry
carry = 0
if temp > 9:
digits[i] = temp % 10
carry = 1
else:
digits[i] = temp
if carry>0:
add carry to the first index
return digits
Time & Space Complexity:
Time: O(n), worst-case when all digits are 9 Space: O(1) extra (ignoring output list)
- Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don’t need to modify intervals in-place. You can make a new array and return it.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105
Pattern: Intervals
Intuition: Make a new result array. There are three conditions you should be thinking about: the new interval comes before the current interval, in which case you should append and return return res + intervals[i:]. Second case is that the new interval comes after the current one, then just append the current one with the result. and finally that none of these conditions are true, then take the minimum and maximum for start and end., but dont append. Outside the loop append and return result.
Code:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
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(intervals[i][0],newInterval[0]),max(intervals[i][1],newInterval[1])]
res.append(newInterval)
return res
Time & Space Complexity
Time: O(n) — one pass through intervals Space: O(n) — result list holds output
- Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
Pattern: Intervals
Intuition: Sort the intervals first, since they are unsorted. Essentially you are going to look at the last element of the result and check if it the current interval intersects with it or not. If yes, then update the end and continue without adding. Else just add the current one as a separate one.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort (key = lambda i: i[0])
end = intervals[0][1]
res = [intervals[0]]
for i in range (1,len(intervals)):
end = res[-1][1]
if intervals[i][0] <= end:
res[-1][1] = max (end,intervals[i][1])
else:
res.append(intervals[i])
return res
Time & Space Complexity
Time: O(n log n) — for sorting Space: O(n) — for the merged result
- Non-overlapping Intervals
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don’t need to remove any of the intervals since they’re already non-overlapping.
Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
Pattern: Intervals
Intuition: First sort the intervals as they are unsorted. Maintain a prevend, start from the second element, and see if the current interval overlaps with the last one, if no then update the prevend pointer. Else increase the count, take the minumum of end or prevend. The idea here is to only drop the one that ends later, so taking the minimum is as good as dropping the one after.
Code:
intervals.sort(key= lambda i : i[0])
prevend = intervals[0][1]
count = 0
for start,end in intervals[1:]:
if start >= prevend:
prevend = end
else:
count += 1
prevend = min(prevend,end)
return count
⏱ Time & Space Complexity
Time: O(n log n) for sorting Space: O(1) extra (in-place iteration)
Meeting Rooms
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: true
Constraints:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106
Patterns: Intervals
Intuition: Just check if the current start is less than the previous end. If yes, then return false. When out of the loop return True.
Code:
intervals.sort(key = lambda i: i[0])
for i in range(1,len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return False
return True
⏱ Time & Space Complexity
Time: O(n log n) — for sorting Space: O(1) — in-place processing
Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1
Constraints:
1 <= intervals.length <= 104
0 <= start < end <= 106
Pattern: Intervals
Intution: Maintain two arrays, start and end. You have to see how many starts are there before the first end. then as the start goes equal and above the ends, increase the ends too. This will ensure you will count all of the meetings manually. and maintain a maxcount variable.
Code:
starts = []
ends = []
count = 0
maxcount = 0
for interval in intervals:
starts.append(interval[0])
ends.append(interval[1])
starts.sort()
ends.sort()
print(starts,ends)
i,j = 0, 0
while j < len(ends) and i < len(starts):
if starts[i] < ends[j]:
count+=1
i += 1
else:
count -= 1
j += 1
maxcount = max(count,maxcount)
return maxcount
⏱ Time & Space Complexity
Time: O(n log n) for sorting Space: O(n) for start and end arrays
- Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Pattern: Greedy
Intuition: maintain a sum, and if it goes below zero then start afresh. also maintain a maxsum. then return it. Basic Greedy problem.
Note: The reason that we are comparing cursum before and then adding the num to cursum is because, if you added it before, and reset it to zero, the maxsum will compare to 0 instead of the negative number, and the maxarea will be 0. Also one more intuition is that you need to start the maxsum with nums[0] instead of zero.
Code:
cursum = 0
maxsum = nums[0]
for num in nums:
if cursum < 0:
cursum = 0
cursum += num
maxsum = max(cursum,maxsum)
return maxsum
Time: O(n)
Space: O(1)
- Jump Game
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 105
Pattern: Greedy
Brute force: Naive Backtracking (Too Slow) TLE for large inputs
Time: O(2^n) worst case
Space: O(n) recursion stack
Intuition: Maintain a goal variable, and go in reverse and check if you can go till that goal. if you can, then update that as the goal. if you reach this the first index then return True
Code:
def canJump(self, nums: List[int]) -> bool:
size = len(nums)
goal = nums[size - 1]
for i in range (size - 1, -1, -1):
if (i + nums[i]) >= goal:
goal = i
return goal == 0
Time & Space Complexity
Time: O(n) Space: O(1)
- Jump Game II
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
It’s guaranteed that you can reach nums[n - 1].
Pattern: Greedy
Intuition: Here we dont just want to find IF we can reach, but whats the minimum. So think of the ranges to which you can go at MAX, then from that MAX see whats the next MAX you can go to. This is a good greedy way to solve it.
def jump(self, nums: List[int]) -> int:
res = 0
l = r = 0
while r < len(nums) - 1:
farthest = 0
for i in range(l,r + 1):
farthest = max(farthest, i + nums[i])
l = r + 1
r = farthest
res += 1
return res
Time O(n) ✅
Space O(1) ✅
- Gas Station
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.
Constraints:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
Pattern: Greedy
Intuition: Greedy approach. make an array of the difference between gas and cost. Maintain a total, if that total goes below zero then reset it. there will be an index after which it is never reset, return that index. since you would have enough gas to keep moving forward after that one.
Code:
size = len(gas)
total = 0
start = 0
if sum (gas) < sum(cost):
return -1
for i in range(size):
total += (gas[i] - cost[i])
if total < 0:
total = 0
start = i + 1
return start
Time and Space Complexity
Metric Complexity
Time O(n)
Space O(1)
- Hand of Straights
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
Example 1:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice’s hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice’s hand can not be rearranged into groups of 4.
Constraints:
1 <= hand.length <= 104
0 <= hand[i] <= 109
1 <= groupSize <= hand.length
Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
Pattern: Greedy
Intuition: Here, you have to make a heap, and a count dictionary. The heap helps in determining which is the smallest number. Then you keep going through a loop until heap becomes empty. In a second loop inside, go through all of the elements from the current smallest to smallest + groupsize. Then check the following conditions:
1) if i was never in the count dict, then return false
2) Reduce the count of i in dict.
3) If count is now zero, pop the min element from the heap
4) also if count has become 0 and also the current element is not the smallest element then return false (which explains why the above condition never pops a non smallest elements ever)
Code:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize:
return False
count = {}
for num in hand:
count[num] = 1 + count.get(num,0)
minh = list (count.keys())
heapq.heapify(minh)
while minh:
first = minh[0]
for i in range(first,first+groupSize):
if i not in count:
return False
count[i] -= 1
if count[i] == 0:
if i != minh[0]:
return False
heapq.heappop(minh)
return True
Metric Value
Time O(n log n)
Space O(n)
- Merge Triplets to Form Target Triplet
A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.
To obtain target, you may apply the following operation on triplets any number of times (possibly zero):
Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].
Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.
Example 1:
Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.
Example 2:
Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.
Example 3:
Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.
Constraints:
1 <= triplets.length <= 105
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000
Pattern: Greedy
Intuition: You just need to filter out all the triplets which are more than the numbers that we are looking for. Then check if each number exists in there at least once. If all three flags are yes then return true.
Code:
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
res = []
for triplet in triplets:
if triplet[0] <= target[0] and triplet[1] <= target[1] and triplet[2] <= target[2] :
res.append(triplet)
print(res)
flag1 = False
flag2 = False
flag3 = False
for triplet in res:
if (target[0] == triplet[0]):
flag1 = True
if (target[1] == triplet[1]):
flag2 = True
if (target[2] == triplet[2]):
flag3 = True
return flag1 and flag2 and flag3
Time & Space Complexity
Metric Complexity
Time O(n)
Space O(1)
- Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
Seen this question in a real interview before?
1/5
Pattern: 1D DP
Intuition: Since you can take two steps at once, Imagine creating a tree with all of the choices. The last step and second last step will have one way to reach the top. Then go in reverse and simply add the next two (ways). It means you are adding up the number of ways in reverse and return the lowest one as the answer.
Code:
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n+1)
dp[n] = 1
dp [n-1] = 1
if n == 1:
return 1
if n == 2:
return 2
for i in range (n-2,-1,-1):
dp[i] = dp [i + 1] + dp [i + 2]
return dp [0]
- Min Cost Climbing Stairs
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
Constraints:
2 <= cost.length <= 1000
0 <= cost[i] <= 999
sion (239)
Pattern: 1D DP
Intuition: Here, top means the stair after the final one. So add a 0 to the entire array. Then You can take one step or two, and need to decide which one will cost less. So go in reverse, and from the last element, take the minimum from the sum of current and next or sum of current and next of next.
dp = cost + [0]
size = len (dp)
#print (dp)
for i in range(size - 3, -1, -1):
dp[i] = min (dp[i] + dp[i+1],dp[i] + dp[i+2])
print(dp)
res = min (dp[0],dp[1]) return res
- House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 400
Pattern: 1D DP
Intuition: Here you are either allowed to pick the current node or the skip the current one. Maintain a dp array starting from 0 and take in it the max of either the last one, or current one and the one before the last one. then return the last element.
Code:
size = len(nums)
if size == 1:
return nums[0]
nums[1] = max (nums[0],nums[1])
for i in range(2,len(nums)):
nums[i] = max (nums[i-1],nums[i-2]+nums[i])
return nums[size-1]
