Medium: Arrays & Strings (11-20)
Medium array and string problems are the most common interview questions at AI/ML companies. These ten problems cover two pointers, sliding window, hash maps, sorting, and prefix sums — the patterns that account for roughly 40% of all coding interview questions.
Problem 11: 3Sum
LeetCode #15 — Given an integer array, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.
Pattern: Sort + Two Pointers — Fix one element, use two pointers on the remaining sorted array.
ML Context: Feature interaction search in automated feature engineering uses similar combinatorial search patterns with pruning to avoid redundant combinations.
def threeSum(nums):
"""
Time: O(n^2) - sort O(n log n) + two pointer scan O(n) per element
Space: O(1) extra (excluding output)
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]: # skip duplicates
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # skip duplicates
while left < right and nums[right] == nums[right - 1]:
right -= 1 # skip duplicates
left += 1
right -= 1
return result
# threeSum([-1,0,1,2,-1,-4]) -> [[-1,-1,2],[-1,0,1]]Problem 12: Container With Most Water
LeetCode #11 — Given n non-negative integers height where each represents a point (i, height[i]), find two lines that form a container holding the most water.
Pattern: Two Pointers — Start at widest container, shrink from the shorter side.
ML Context: Optimization problems where you maximize an objective by adjusting two parameters from boundary conditions inward appear in hyperparameter grid search and constraint satisfaction.
def maxArea(height):
"""
Time: O(n) - two pointers meet in the middle
Space: O(1)
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
h = min(height[left], height[right])
max_water = max(max_water, width * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
# maxArea([1,8,6,2,5,4,8,3,7]) -> 49Problem 13: Longest Substring Without Repeating Characters
LeetCode #3 — Given a string s, find the length of the longest substring without repeating characters.
Pattern: Sliding Window + Hash Map — Expand right, shrink left when a duplicate is found.
ML Context: Sliding windows are used extensively in NLP tokenization (subword segmentation), time-series feature extraction, and convolutional operations over sequences.
def lengthOfLongestSubstring(s):
"""
Time: O(n) - each character visited at most twice
Space: O(min(m, n)) where m is charset size
"""
char_index = {}
max_len = 0
left = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# lengthOfLongestSubstring("abcabcbb") -> 3 ("abc")
# lengthOfLongestSubstring("bbbbb") -> 1 ("b")
# lengthOfLongestSubstring("pwwkew") -> 3 ("wke")Problem 14: Product of Array Except Self
LeetCode #238 — Given an integer array nums, return an array answer such that answer[i] is the product of all elements except nums[i]. You must solve it without division and in O(n) time.
Pattern: Prefix/Suffix Products — Build left products, then multiply by right products.
ML Context: Prefix/suffix computations are used in parallel scan algorithms on GPUs, which are foundational to efficient transformer implementations and cumulative statistics in streaming ML systems.
def productExceptSelf(nums):
"""
Time: O(n) - two passes
Space: O(1) extra (output array not counted)
"""
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of all elements to the left
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply by product of all elements to the right
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
# productExceptSelf([1,2,3,4]) -> [24,12,8,6]
# productExceptSelf([-1,1,0,-3,3]) -> [0,0,9,0,0]Problem 15: Group Anagrams
LeetCode #49 — Given an array of strings, group the anagrams together. An anagram is a word formed by rearranging the letters of another word.
Pattern: Hash Map with sorted key — Two strings are anagrams if their sorted forms are equal.
ML Context: Grouping by canonical form is used in entity resolution and deduplication in NLP pipelines. Named entity linking groups different surface forms of the same entity.
from collections import defaultdict
def groupAnagrams(strs):
"""
Time: O(n * k log k) where k is max string length
Space: O(n * k) for the hash map
"""
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
groups[key].append(s)
return list(groups.values())
# Alternative O(n*k) using character counts as key:
def groupAnagramsOptimal(strs):
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())
# groupAnagrams(["eat","tea","tan","ate","nat","bat"])
# -> [["eat","tea","ate"],["tan","nat"],["bat"]]Problem 16: Merge Intervals
LeetCode #56 — Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals.
Pattern: Sort + Linear Scan — Sort by start time, merge if current overlaps with previous.
ML Context: Interval merging is used in GPU memory management for model training, time-series event deduplication, and scheduling training jobs on shared clusters.
def merge(intervals):
"""
Time: O(n log n) for sorting
Space: O(n) for output
"""
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# merge([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]
# merge([[1,4],[4,5]]) -> [[1,5]]Problem 17: Sort Colors
LeetCode #75 — Given an array with n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent (Dutch National Flag problem).
Pattern: Three-way Partition (Dutch National Flag) — Three pointers: low, mid, high.
ML Context: Three-way partitioning is used in quickselect for finding k-th percentile features and in data stratification for balanced train/validation/test splits.
def sortColors(nums):
"""
Dutch National Flag Algorithm
Time: O(n) - single pass
Space: O(1) - in-place
"""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# nums = [2,0,2,1,1,0]; sortColors(nums) -> [0,0,1,1,2,2]Problem 18: Subarray Sum Equals K
LeetCode #560 — Given an array of integers and an integer k, return the total number of subarrays whose sum equals k.
Pattern: Prefix Sum + Hash Map — Store prefix sum frequencies; count[prefix - k] gives subarrays ending here with sum k.
ML Context: Prefix sum techniques are used in computing cumulative statistics for streaming data, efficient attention score computation, and integral images for object detection.
from collections import defaultdict
def subarraySum(nums, k):
"""
Time: O(n) - single pass
Space: O(n) - hash map of prefix sums
"""
count = 0
prefix_sum = 0
prefix_counts = defaultdict(int)
prefix_counts[0] = 1 # empty subarray
for num in nums:
prefix_sum += num
count += prefix_counts[prefix_sum - k]
prefix_counts[prefix_sum] += 1
return count
# subarraySum([1,1,1], 2) -> 2
# subarraySum([1,2,3], 3) -> 2 ([1,2] and [3])Problem 19: Rotate Array
LeetCode #189 — Given an integer array nums, rotate the array to the right by k steps.
Pattern: Reverse Three Times — Reverse all, reverse first k, reverse rest.
ML Context: Array rotation and circular buffer operations appear in ring buffers for experience replay in reinforcement learning and circular data loading patterns in training pipelines.
def rotate(nums, k):
"""
Time: O(n) - three reversals
Space: O(1) - in-place
"""
k = k % len(nums)
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, len(nums) - 1) # reverse all
reverse(0, k - 1) # reverse first k
reverse(k, len(nums) - 1) # reverse rest
# nums = [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]Problem 20: Spiral Matrix
LeetCode #54 — Given an m x n matrix, return all elements in spiral order.
Pattern: Boundary Simulation — Maintain top/bottom/left/right boundaries, shrink after each pass.
ML Context: Matrix traversal patterns are fundamental to understanding how convolution kernels slide over feature maps in CNNs. Spiral and zigzag scans appear in image compression (JPEG) and quantization.
def spiralOrder(matrix):
"""
Time: O(m * n) - visit every element
Space: O(1) extra (excluding output)
"""
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for col in range(left, right + 1): # go right
result.append(matrix[top][col])
top += 1
for row in range(top, bottom + 1): # go down
result.append(matrix[row][right])
right -= 1
if top <= bottom:
for col in range(right, left - 1, -1): # go left
result.append(matrix[bottom][col])
bottom -= 1
if left <= right:
for row in range(bottom, top - 1, -1): # go up
result.append(matrix[row][left])
left += 1
return result
# spiralOrder([[1,2,3],[4,5,6],[7,8,9]]) -> [1,2,3,6,9,8,7,4,5]Key Takeaways
- Two pointers on sorted data (3Sum, Container) reduces O(n^2) to O(n) per fixed element. Always consider sorting first.
- Sliding window (Longest Substring) handles variable-length subarray/substring problems efficiently.
- Prefix sums (Product of Array, Subarray Sum K) precompute cumulative values for O(1) range queries.
- Hash maps for grouping (Group Anagrams) are the standard approach for classification-by-key problems.
- In-place algorithms (Sort Colors, Rotate Array) demonstrate the space optimization skills interviewers value.