Leetcode: Sum Series — Two Sum

Image Source

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

Example
Input: 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, if target < 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 of O(nlogn) . While the rest of the algorithm is linear, sorting the array makes the asymptotic computational complexity to be O(nlogn) .

Patterns + Conclusion

1. 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.
2. A counter/frequency hashmap is necessary when considering the possibility of two duplicate numbers that add up to the target.
3. 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

1. Two Sum I: Leetcode Link
2. Two Sum II — Input Array Is Sorted: Leetcode Link
3. Two Sum III — Data structure design: Leetcode Link
4. Two Sum Less Than K: Leetcode Link

Series

Next >> Leetcode: Sum Series — Three Sum