As "Hello, World!" is to programming, so is Two Sum to LeetCode. Any blog series on solving LeetCode problems has to first pay deference to this problem.
Problem Statement
Given an array of integers, return indices of the two numbers such that they add up to a specific target. Each input has exactly one solution; you may not use the same element twice.
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (because nums[0] + nums[1] = 2 + 7 = 9)
Two things to note: we return indices, and the array is not sorted.
Solutions
1. Brute Force — O(N²) time, O(1) space
Iterate over each element; for each, iterate over the rest to check if they sum to the target.
def two_sum(array, target):
n = len(array)
for i in range(n):
for j in range(i+1, n):
if array[i] + array[j] == target:
return [i, j]
return []
2. Hash Table — O(N) time, O(N) space
Store elements and their indices in a hash table. While iterating, check if target - element is
already present.
def two_sum(array, target):
htable = {}
for i, val in enumerate(array):
residual = target - val
if residual in htable:
return [htable[residual], i]
htable[val] = i
return []
We sacrifice O(N) space to achieve linear time. Space is cheap; time invaluable.
3. Two Pointer (when returning elements, not indices) — O(N log N) time, O(1) space
Sort the array. Use two pointers from either end — if the sum exceeds the target, decrement the right pointer; if it falls short, increment the left.
def two_sum(array, target):
array.sort()
i, j = 0, len(array) - 1
while i < j:
curr_sum = array[i] + array[j]
if curr_sum == target:
return [array[i], array[j]]
if curr_sum < target:
i += 1
else:
j -= 1
return []
Developing intuition for LeetCode problems takes time. Over time you'll learn there are a handful of approaches to try first for any given problem. Two pointers is one pattern worth internalizing.
Later.