1. Problems 111–120
Same format as the previous modules: expand a problem to see the approach and both commented solutions. This is the last set — problem 120 closes out all 120 problems across the full Coding Practice series.
P111
Two Sum
[2,7,11,15], target 9 → indices [0, 1] (2 + 7 = 9).
Two Sum
[2,7,11,15], target 9 → indices [0, 1] (2 + 7 = 9).
Approach: for each number, compute what its partner would need to be (target - number) and check a hash map of numbers already seen. If the partner's there, done — this turns an O(n²) "check every pair" brute force into a single O(n) pass.
JavaScript
// A hash map remembers "what number would complete a pair with the number I've
// already seen" -- turning an O(n^2) brute force into a single O(n) pass.
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1] (2 + 7 = 9)Python
def two_sum(nums: list, target: int) -> list:
seen = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1] (2 + 7 = 9)
P112
Three Sum
Find every triplet in a list that sums to zero.
Three Sum
Find every triplet in a list that sums to zero.
Approach: sort first, then fix one number at a time and two-pointer-search the rest of the array for a pair that completes the sum to zero — skipping past duplicate values so the same triplet doesn't get reported twice.
JavaScript
// Sort first, fix one number, then two-pointer-search the rest for a pair
// that completes the target sum of zero -- skipping duplicates along the way.
function threeSum(nums) {
const sorted = [...nums].sort((a, b) => a - b);
const result = [];
for (let i = 0; i < sorted.length - 2; i++) {
if (i > 0 && sorted[i] === sorted[i - 1]) continue; // skip duplicate first numbers
let left = i + 1, right = sorted.length - 1;
while (left < right) {
const sum = sorted[i] + sorted[left] + sorted[right];
if (sum === 0) {
result.push([sorted[i], sorted[left], sorted[right]]);
while (left < right && sorted[left] === sorted[left + 1]) left++; // skip duplicates
while (left < right && sorted[right] === sorted[right - 1]) right--;
left++; right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
console.log(threeSum([-1, 0, 1, 2, -1, -4])); // [[-1, -1, 2], [-1, 0, 1]]Python
def three_sum(nums: list) -> list:
sorted_nums = sorted(nums)
result = []
for i in range(len(sorted_nums) - 2):
if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
continue # skip duplicate first numbers
left, right = i + 1, len(sorted_nums) - 1
while left < right:
total = sorted_nums[i] + sorted_nums[left] + sorted_nums[right]
if total == 0:
result.append([sorted_nums[i], sorted_nums[left], sorted_nums[right]])
while left < right and sorted_nums[left] == sorted_nums[left + 1]:
left += 1 # skip duplicates
while left < right and sorted_nums[right] == sorted_nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]
P113
Maximum Subarray (Kadane's Algorithm)
The best contiguous run inside a list of positive and negative numbers.
Maximum Subarray (Kadane's Algorithm)
The best contiguous run inside a list of positive and negative numbers.
Approach: at each position, decide: extend the running subarray, or abandon it and start fresh here? Extending only helps once the running sum has gone negative — a negative running sum can only ever drag a future subarray down.
JavaScript
// At each position, decide: extend the previous subarray, or start fresh here?
// Extending only helps if the running sum is still positive.
function maxSubArray(nums) {
let maxSoFar = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]); // extend or restart
maxSoFar = Math.max(maxSoFar, currentSum);
}
return maxSoFar;
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 ([4, -1, 2, 1])Python
def max_sub_array(nums: list) -> int:
max_so_far = nums[0]
current_sum = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i]) # extend or restart
max_so_far = max(max_so_far, current_sum)
return max_so_far
print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6 ([4, -1, 2, 1])
P114
Product of Array Except Self
[1,2,3,4] → [24,12,8,6], without ever dividing.
Product of Array Except Self
[1,2,3,4] → [24,12,8,6], without ever dividing.
Approach: the obvious solution (multiply everything, then divide out each element) breaks the moment a zero appears. Instead, do it in two passes: for each index, the answer is "everything to its left" multiplied by "everything to its right" — a running product built up from each direction separately.
JavaScript
// Without division: for each index, multiply everything to its left by
// everything to its right, computed in two passes.
function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n).fill(1);
let leftProduct = 1;
for (let i = 0; i < n; i++) {
result[i] = leftProduct; // product of everything to the left of i
leftProduct *= nums[i];
}
let rightProduct = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= rightProduct; // multiply in the product of everything to the right
rightProduct *= nums[i];
}
return result;
}
console.log(productExceptSelf([1, 2, 3, 4])); // [24, 12, 8, 6]Python
def product_except_self(nums: list) -> list:
n = len(nums)
result = [1] * n
left_product = 1
for i in range(n):
result[i] = left_product # product of everything to the left of i
left_product *= nums[i]
right_product = 1
for i in range(n - 1, -1, -1):
result[i] *= right_product # multiply in the product of everything to the right
right_product *= nums[i]
return result
print(product_except_self([1, 2, 3, 4])) # [24, 12, 8, 6]
P115
Merge Overlapping Intervals
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].
Merge Overlapping Intervals
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].
Approach: sort by start time first — once sorted, any interval that overlaps the current merged one is guaranteed to appear immediately after it, so a single left-to-right pass is enough.
JavaScript
// Sort by start time first -- once sorted, any interval that overlaps the
// current merged one must come immediately after it.
function mergeIntervals(intervals) {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const merged = [sorted[0]];
for (let i = 1; i < sorted.length; i++) {
const last = merged[merged.length - 1];
const current = sorted[i];
if (current[0] <= last[1]) { // overlaps -- extend the last merged interval
last[1] = Math.max(last[1], current[1]);
} else {
merged.push(current); // no overlap -- start a new interval
}
}
return merged;
}
console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1, 6], [8, 10], [15, 18]]Python
def merge_intervals(intervals: list) -> list:
sorted_intervals = sorted(intervals, key=lambda pair: pair[0])
merged = [sorted_intervals[0]]
for current in sorted_intervals[1:]:
last = merged[-1]
if current[0] <= last[1]: # overlaps -- extend the last merged interval
last[1] = max(last[1], current[1])
else:
merged.append(current) # no overlap -- start a new interval
return merged
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
P116
Longest Substring Without Repeating Characters
"abcabcbb" → 3, the length of "abc".
Longest Substring Without Repeating Characters
"abcabcbb" → 3, the length of "abc".
Approach: a sliding window. Grow the window's right edge one character at a time; the moment a repeat shows up, jump the window's left edge past that character's earlier occurrence instead of resetting all the way back to the start.
JavaScript
// A sliding window: grow the right edge; whenever a repeat is seen, shrink
// the left edge past the previous occurrence of that character.
function lengthOfLongestSubstring(s) {
const lastSeen = new Map();
let start = 0, maxLength = 0;
for (let end = 0; end < s.length; end++) {
const ch = s[end];
if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
start = lastSeen.get(ch) + 1; // jump the window past the earlier duplicate
}
lastSeen.set(ch, end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")Python
def length_of_longest_substring(s: str) -> int:
last_seen = {}
start = 0
max_length = 0
for end, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1 # jump the window past the earlier duplicate
last_seen[ch] = end
max_length = max(max_length, end - start + 1)
return max_length
print(length_of_longest_substring("abcabcbb")) # 3 ("abc")
P117
Group Anagrams
["eat","tea","tan","ate","nat","bat"] → three groups.
Group Anagrams
["eat","tea","tan","ate","nat","bat"] → three groups.
Approach: every anagram of a word shares the same "signature" once its letters are sorted — group words by that signature (Module 7's groupBy, with the sorted letters as the key) and each resulting group is a full set of anagrams.
JavaScript
// Every anagram of a word shares the same sorted-letters "signature" -- group
// words by that signature and each group is a set of anagrams.
function groupAnagrams(words) {
const groups = new Map();
for (const word of words) {
const signature = word.split("").sort().join(""); // same letters -> same signature
if (!groups.has(signature)) groups.set(signature, []);
groups.get(signature).push(word);
}
return [...groups.values()];
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]Python
def group_anagrams(words: list) -> list:
groups = {}
for word in words:
signature = "".join(sorted(word)) # same letters -> same signature
if signature not in groups:
groups[signature] = []
groups[signature].append(word)
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
P118
Longest Common Prefix
["flower","flow","flight"] → "fl".
Longest Common Prefix
["flower","flow","flight"] → "fl".
Approach: start by assuming the whole first word is the prefix, then check it against every other word — the instant one doesn't start with the current prefix, shrink the prefix by one character from the end and check again.
JavaScript
// Compare the first string against every other, shrinking the candidate
// prefix character by character the moment a mismatch is found.
function longestCommonPrefix(words) {
if (words.length === 0) return "";
let prefix = words[0];
for (let i = 1; i < words.length; i++) {
while (!words[i].startsWith(prefix)) {
prefix = prefix.slice(0, -1); // shrink by one character and try again
if (prefix === "") return "";
}
}
return prefix;
}
console.log(longestCommonPrefix(["flower", "flow", "flight"])); // "fl"Python
def longest_common_prefix(words: list) -> str:
if len(words) == 0:
return ""
prefix = words[0]
for word in words[1:]:
while not word.startswith(prefix):
prefix = prefix[:-1] # shrink by one character and try again
if prefix == "":
return ""
return prefix
print(longest_common_prefix(["flower", "flow", "flight"])) # "fl"
P119
Container With Most Water
Which two walls trap the largest volume of water between them?
Container With Most Water
Which two walls trap the largest volume of water between them?
Approach: two pointers start at the widest possible container (both ends) and move inward. Always move the shorter wall — the taller one can never become the bottleneck for any wider container later, so keeping it in place never loses a better answer.
JavaScript
// Two pointers start at the widest possible container and move inward --
// always move the SHORTER wall, since the taller one can never be the
// bottleneck for a wider container later.
function maxArea(heights) {
let left = 0, right = heights.length - 1, best = 0;
while (left < right) {
const width = right - left;
const height = Math.min(heights[left], heights[right]);
best = Math.max(best, width * height);
if (heights[left] < heights[right]) left++; // the shorter wall is the bottleneck
else right--;
}
return best;
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49Python
def max_area(heights: list) -> int:
left, right = 0, len(heights) - 1
best = 0
while left < right:
width = right - left
height = min(heights[left], heights[right])
best = max(best, width * height)
if heights[left] < heights[right]: # the shorter wall is the bottleneck
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49
P120
Move All Zeroes to the End
[0,1,0,3,12] → [1,3,12,0,0], in place, preserving order.
Move All Zeroes to the End
[0,1,0,3,12] → [1,3,12,0,0], in place, preserving order.
Approach: the last technique of the series — a "write pointer" tracks where the next non-zero value belongs. Walk once with a "read pointer"; every time a non-zero value is found, swap it into the write pointer's slot and advance both. Zeroes naturally end up shuffled to the back.
JavaScript
// A "write pointer" tracks where the next non-zero value belongs; walk once
// with a "read pointer", and every zero found gets shuffled toward the end.
function moveZeroes(arr) {
let writeIndex = 0;
for (let readIndex = 0; readIndex < arr.length; readIndex++) {
if (arr[readIndex] !== 0) {
[arr[writeIndex], arr[readIndex]] = [arr[readIndex], arr[writeIndex]];
writeIndex++;
}
}
return arr;
}
console.log(moveZeroes([0, 1, 0, 3, 12])); // [1, 3, 12, 0, 0]Python
def move_zeroes(items: list) -> list:
write_index = 0
for read_index in range(len(items)):
if items[read_index] != 0:
items[write_index], items[read_index] = items[read_index], items[write_index]
write_index += 1
return items
print(move_zeroes([0, 1, 0, 3, 12])) # [1, 3, 12, 0, 0]2. Key Takeaways
- Three techniques cover almost this entire module: a hash map trading space for O(n) lookups (Two Sum, Group Anagrams), two pointers moving inward from both ends (Three Sum, Container With Most Water, Move Zeroes), and a sliding window for contiguous runs (Longest Substring, Maximum Subarray).
- Sorting first is often the setup step that makes a two-pointer or interval technique possible at all — Three Sum and Merge Intervals both start there.
- That's all 120 problems. Every technique here — frequency maps, two pointers, sliding windows, recursion, closures, async concurrency — first appeared in a simpler form somewhere back in Modules 1–11.