Arrays and Subarrays
Time Complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | O(1) | |
| Search | O(n) | |
| Search (sorted array) | O(log(n)) | Binary Search |
| Insert | O(n) | Insertion would require shifting all the subsequent elements to the right by one and that takes O(n) |
| Insert (at the end) | O(1) | Special case of insertion where no other element needs to be shifted |
| Remove | O(n) | Removal would require shifting all the subsequent elements to the left by one and that takes O(n) |
| Remove (at the end) | O(1) | Special case of removal where no other element needs to be shifted |
Common Approaches to Arrays and Subarrays Questions
Prefix Sum
nums = [10, 20, 5, 15]
prefixSum = [10, 30, 35, 50]
prefixSum[i] = prefixSum[i - 1] + arr[i]
Sliding Window
Subarray Sum
Kadane's Algorithm
Example Solutions
Maximum Subarray
Solutions are adapted from this LeetCode discussion by archit91
Solution 1: Dynamic Programming + Memoization
Bottom-up approach. dp array will store the maximum subarray sum at its respective index
def maxSubArray(self, nums):
dp = nums
for i in range(1, len(nums)):
# Store maximum of nums[i] or nums[i] + previous maximum
dp[i] = max(nums[i], dp[i-1] + nums[i])
return max(dp)
nums = [-2,1,-3,4,-1,2,1,-5,4]
dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5] # dp array after running
Time Complexity: O(n) for looping through the nums array.
Space Complexity: O(n) for storing dp array of size n.
Solution 2: Kadane's Algorithm (Prefered Solution)
Optimize previous solution in terms of space by only storing the maximum of each iteration. The global maximum will then be the maximum of all the iterations.
def maxSubArray(self, nums):
globalMax = localMax = nums[0] # Starts with nums[0]
for num in nums[1:]: # Iterate through remaining array nums[1:]
localMax = max(num, localMax + num)
globalMax = max(globalMax, localMax)
return globalMax
Time Complexity: O(n) for looping through the nums array.
Space Complexity: O(1) for 2 variables globalMax and localMax.
Container With Most Water
Solution 1: Sliding Window
def maxArea(self, height):
max_area = 0
left = 0
right = len(height) - 1
while left <= right: # terminating condition: left > right
h = min(height[left], height[right])
area = h * (right - left)
max_area = max(max_area, area)
# Shift window
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
Time Complexity: O(n) for looping through the height array.
Space Complexity: O(1) for 3 variables max_area and left and right.
Trapping Rain Water
Solution 1: Sliding Window (Easier to understand)
def trap(self, height):
water = 0
i, j = 0, len(height) - 1
lmax, rmax = height[i], height[j]
while i <= j: # Terminates when i > j
lmax = max(lmax, height[i])
rmax = max(rmax, height[j])
if lmax <= rmax:
water += lmax - height[i] # Add height difference from lmax
i += 1
else:
water += rmax - height[j] # Add height difference from rmax
j -= 1
return water
Time Complexity: O(n) for looping through the height array.
Space Complexity: O(1) for constant variables.
Solution 2: Stack
def trap(self, height):
water = 0
stack = []
for i, h in enumerate(height):
if stack and h > height[stack[-1]]:
deal = stack.pop()
if stack:
w = i - stack[-1] - 1
water += (min(h, height[deal]) - height[i]) * w
stack.append(i)
return water
Invariant: Stack always contain the indexes which have bar heights in decreasing order.
When we encounter a higher bar, we will pop the stack until we meet invariant then push the stack again.
Time Complexity: O(n) for looping through the height array.
Space Complexity: O(n) for using a stack.
Product of Array Except Self
Solution: Prefix + Postfix
Here is an excellent video explanation by NeetCode.
Prefix product: Product of all numbers in the array before the current index.
Postfix product: Product of all numbers in the array after the current index.
Idea: Product except self is the product of prefix and postfix
nums = [1, 2, 3, 4]
prefix = [1, 2, 6, 24]
postfix = [24, 24, 12, 4]
result = [24, 12, 8, 6]
# Example: index 1
# prefix for nums[1] = 1
# postfix for nums[1] = 12
# product = 12
'''
nums = [1, 2, 3, 4]
res = [1, 1, 1, 1] - initial
prefix = [1, 1, 2, 6] - shifted by 1
postfix = [24, 12, 4, 1] - shifted by 1
res = [24, 12, 8, 6]
'''
def productExceptSelf(self, nums):
n = len(nums)
prefix = postfix = 1 # initialized as 1
res = [1] * n
for i in range(nums):
res[i] *= prefix
prefix *= nums[i]
res[n-1-i] *= postfix
postfix *= nums[n-1-i]
return res
Time Complexity: O(n) for looping through the nums array.
Space Complexity: O(1) as result array is not counted.
Insert Interval
Solution:
def insert(self, intervals, newInterval):
n = newInterval
res = []
for index, i in enumerate(intervals):
# Case 1: n greater than i
if n[0] > i[1]:
res.append(i)
# Case 2: n smaller than i
elif n[1] < i[0]:
res.append(n)
return res + intervals[index:]
# Case 3: n overlaps with i -> merge
else:
n = [min(n[0], i[0]), max(n[1], i[1])]
# append n to end of list
res.append(n)
return res
Time Complexity: O(n) for looping through the intervals array.
Space Complexity: O(1) as result array is not counted.
Sort Colors
Amazing answer explanation by NeetCode.
Solution:
- left pointer pointing to the first 1
- right pointer pointing to the non-2
def sortColors(self, nums):
l = i = 0
r = len(nums) - 1
while i <= r:
if nums[i] == 0: # swap with left pointer
nums[l], nums[i] = nums[i], nums[l]
l += 1 # move left pointer
elif nums[i] == 2: # swap with right pointer
nums[r], nums[i] = nums[i], nums[r]
r -= 1 # move right pointer
i -= 1 # Edge case: swapped 0 to nums[i]
i += 1
Time Complexity: O(n) for one pass solution.
Space Complexity: O(1) as solution is in-place.
Find All Anagrams in a String
Amazing answer explanation by NeetCode.
Solution:
- Sliding window solution: Update dictionary according to sliding window
def findAnagrams(self, s, p):
if len(p) > len(s):
return []
pCount, sCount = {}, {}
for i in range(len(p)):
pCount[p[i]] = 1 + pCount.get(p[i], 0) # default to 0 if not found
sCount[s[i]] = 1 + sCount.get(s[i], 0)
res = [0] if pCount == sCount else []
l = 0
for r in range(len(p), len(s)): # Starts from len(p) onwards
sCount[s[r]] = 1 + sCount.get(s[r], 0)
sCount[s[l]] -= 1
if sCount[s[l]] == 0: # Remove key from dict
sCount.pop(s[l])
l += 1
if sCount == pCount:
res.append(l)
return res
Time Complexity: O(n) for one pass solution.
Space Complexity: O(1) as maximum space used is dictionary for 26 characters in the alphabet.
Minimum Window Substring
Solution: Sliding window with Hashmaps
Here is an excellent video explanation by NeetCode.
def minWindow(self, s, t):
if t == "":
return t
wMap, tMap = {}, {}
for i in t:
tMap = 1 + tMap.get(i, 0)
have, need = 0, len(tMap)
res, resLen = [-1,-1], len(s) + 1
l = 0
for r in range(len(s)):
c = s[r]
wMap[c] = wMap.get(c, 0)
if c in tMap and wMap[c] == tMap[c]:
have += 1
while have == need:
# update result
if (r - l + 1) < resLen:
res = [l, r]
resLen = r - l + 1
# pop left
lc = s[l]
wMap[lc] -= 1
if lc in tMap and wMap[lc] < tMap[lc]:
have -= 1
l += 1
l, r = res
return s[l, r-1] if resLen != len(s) + 1 else ""
Time Complexity: O(n + m) for looping through the string s of length n and string t of length m.
Space Complexity: O(n + m) for hashmaps used for wMap and tMap.
K Closest Points to Origin
Solution 1: Quick Select
def kClosest(self, points):
def euclidean(point):
return point[0]**2 + point[1]**2
def partition(l, r):
rand = randint(l, r) # choose random pivot
points[r], points[rand] = points[rand], points[r] # move pivot to end
i, pivotDist = l, euclidean(points[rand])
for j in range(l, r+1):
if euclidean(points[j]) <= pivotDist:
points[i], points[j] = points[j], points[i]
i += 1
return i-1
l, r, p = 0, len(points) - 1, len(points)
while p != k:
p = partition(l, r)
if p < k:
l = p + 1
else:
r = p - 1
return points[:pivot]
Time Complexity: O(n) on average, the partitions roughly eliminates half of the remaining elements each time => O(2N).
Space Complexity: O(1), only constant space used.
3Sum
Solution: Sort then 2Sum
def threeSum(self, nums):
res = set()
nums.sort()
for index, i in enumerate(nums):
target = 0 - i
seen = {}
for j in nums[i+1:]:
diff = target - j
if diff in seen:
res.add(tuple([i, j, diff]))
seen[j] = j
return res
Time Complexity: O(n*2)
Space Complexity: O(n)
Next Permutation
Solution:
Idea:
- find last ascending position
k - find smallest num from the end that is greater than
nums[k] - reverse
nums[k+1:]
def nextPermutation(self, nums):
i = j = len(nums) - 1
# Find last ascending position
while i > 0 and nums[i-1] > nums[i]:
i -= 1
if i == 0: # nums is sorted in decreasing order
nums.reverse()
return
k = i - 1
# Find min nums[j] that is greater than nums[k]
while nums[j] < nums[k]:
j -= 1
nums[j], nums[k] = nums[k], nums[j] # swap
# Reverse nums[k+1:]
l, r = i, len(nums) - 1
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
Time Complexity: O(n)
Space Complexity: O(1)