Leetcode: Sum Series — Two Sum
Two sum is not only the fundamental but also the introductory data structures and algorithms problem. I can remember the very first attempting the problem and couldn’t relate how a hashmap comes into the picture.
tl;dr — This article dissects a series of the sum problems while unravelling the common patterns and striving to optimise as much as possible.
Two Sum I
Problem Statement: Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
.
Leetcode Link
ExampleInput: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] == 9, we return [0, 1]
Intuition
- Loop each element and check all others elements ahead to find a compliment
- Maintain a record of numbers encountered to find existing complement
- Sort it?(to be handled in a subsequent question)
Solution 1: Loop each element and check all others if there’s a complement
def twoSum(nums: list[int], target: int) -> list[int] | None:
N = len(nums)
for i in range(N):
for j in range(i + 1, N):
if nums[i] + nums[j] == target:
return [i, j]
Review *
- The time complexity —
O(N²)
, space complexity —O(1)
. For each element, it loops the array a second time to find a compliment apart from itself 😡.
Solution 2: Maintain a record of numbers encountered to find existing complement
def twoSum(nums: list[int], target: int) -> list[int] | None:
seen = dict()
for i, num in enumerate(nums):
compliment = target - num
if compliment in seen:
return [i, seen[compliment]]
seen[num] = i
Review *
- The time complexity —
O(N)
, space complexity —O(N)
. It calculates the corresponding compliment and checks if it exists in the seen record. If not, add it and repeat 😲.
Two Sum II — Input Array Is Sorted
Problem Statement: Given a 1-indexed array of integers nums
that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target
number. Let these two numbers be nums[index1]
and nums[index2]
where 1 <= index1 < index2 <= nums.length
.
Return the indices of the two numbers, index1
and index2
, added by one as an integer array [index1, index2]
of length 2.
Catch — Your solution must use only constant extra space.
Example:Input: nums = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. hence return [1, 2]
Intuition
- Two Sum I Solution 2: Maintain a record of numbers encountered to find existing complement(Failing test — constant extra space)
- Two pointer iteration, starting from both ends squeezing in.
Solution: Two pointer iteration, starting from both ends squeezing in
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
left, right = 0, len(nums) - 1
# It cannot be left <= right because we'll be adding
# the value against itself at the end
while left < right:
curr_sum = nums[left] + nums[right]
if curr_sum == target:
return [left + 1, right + 1]
elif curr_sum < target:
left += 1
else:
right -= 1
return [-1, -1]
Review *
- The time complexity —
O(N)
, space complexity —O(1)
. The key intuition is that, iftarget < curr_sum
, we need to find a bigger value. Therefore, increasing left value makes sense than decreasing right value(since it will reduce the sum even further) and vice versa. - No need to worry about adjusting both pointers at the same time because the traversal condition will calibrate them automatically based on the current sum.
- Highlight — “Do not add a number with itself at the same index to get target”.
Two Sum III —Data structure design
Problem Statement: Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum()
— Initializes the TwoSum object, with an empty array initially.void add(int number)
— Adds number to the data structure.boolean find(int value)
— Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.
Intuition
Counter Hashmap
— Keep a record of the numbers encountered, it can either be a hashset or a hashmap. However, since we want to keep a record of duplicate numbers that can add to the target, we need to keep a occurrence counter of the every number hence a Counter Hashmap
🤓.
Solution: Counter Hashmap
from collections import Counter
class TwoSum:
def __init__(self) -> None:
# self.num_freqs = {}
self.num_freqs = Counter()
def add(self, number: int) -> None:
# self.num_freqs[number] = self.num_freqs.get(number, 0) + 1
self.num_freqs[number] += 1
def find(self, value: int) -> bool:
for num, count in self.num_freqs.items():
complement = value - num
if complement in self.num_freqs:
# If the number and complement are the same,
# ensure there are at least two occurrences
if num != complement or count > 1:
return True
return False
Review *
add Method
: Time Complexity:O(1)
, Space Complexity:O(n)
find Method
: Time Complexity:O(n)
, Space Complexity:O(1)
- Highlight — Maintain occurrence frequency to check for possible summation of a number against itself to the get the target value.
Two Sum Less Than K
Problem Statement: Given an array nums
of integers and integer k
, return the maximum sum such that there exists i < j
with nums[i] + nums[j] = sum
and sum < k
. If no i, j
exist satisfying this equation, return -1
.
Example:Input: nums = [34, 23, 1, 24, 75, 33, 54, 8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.
Intuition
Since there’s no exact value to check against, a hashmap of seen elements is not very useful. With the patterns we have encountered so far, we can take advantage of two pointer logic used in Two Sum II on a sorted array.
Solution: Sorting + Two Sum II(Two pointer)
def twoSumLessThanK(nums: list[int], target: int) -> int:
nums.sort()
ans = -1
left, right= 0, len(nums) - 1
while left < right:
curr_sum = nums[left] + nums[right]
if curr_sum < target:
ans = max(ans, curr_sum)
left+= 1
else:
right-= 1
return ans
Review *
- The time complexity —
O(nlogn)
, space complexity —O(1)
. The best sorting algorithm has a time complexity ofO(nlogn)
. While the rest of the algorithm is linear, sorting the array makes theasymptotic computational complexity
to beO(nlogn)
.
Patterns + Conclusion
- A hashmap(key: number, value: index) keeping a record of seen numbers is handy when finding a compliment number. The value is mainly used to return the index otherwise a hashset would suffice.
- A counter/frequency hashmap is necessary when considering the possibility of two duplicate numbers that add up to the target.
- Two pointer technique is very useful when finding two numbers whose summation adjusts as one value increases or decreases. It works with a sorted array.
Note: The article cover image has not correlation to the problem and solutions provided.
References
- Two Sum I: Leetcode Link
- Two Sum II — Input Array Is Sorted: Leetcode Link
- Two Sum III — Data structure design: Leetcode Link
- Two Sum Less Than K: Leetcode Link
Series
Next >> Leetcode: Sum Series — Three Sum