Two Sum and Its Variants

Date : December 18, 2021
Categories :
Tags : Two pointers ,Hash table ,Algorithms ,Data structures ,Coding interview

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.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Brute Force Solution

A straightforward approach is to try all pairs of indices (i, j) and check if nums[i] + nums[j] == target. This approacha has quadratic running time and uses constant extra space (not counting the space used by output).

Hash Map Solution

An optimized approach is to store the numbers in a Hash Table which enables constant lookup time:

def twoSum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(nums):
        if (complement := target - num) in seen:
            return [i, seen[complement]]
        seen[num] = i
    return []

The time and space complexity is both O(n). Obviously the linear running time is optimal as a linear scan of nums is inevitable.

Variant I: Data Structure Design

from collections import Counter

class TwoSum:
    def __init__(self):
        self.counts = Counter()

    def add(self, number: int) -> None:
        self.counts[number] += 1
        
    def find(self, value: int) -> bool:
        return any(
            (complement := value - num) in self.counts and
            (complement != num or count > 1)
            for num, count in self.counts.items()
        )

Variant II: Input is sorted.

When nums is sorted we can use two-pointers technique:

def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    while left < right:
        if numbers[left] + numbers[right] < target:
            left += 1
        elif numbers[left] + numbers[right] > target:
            right -= 1
        else:
            return [left + 1, right + 1]

Time complexity: O(n)

Space complexity: O(1)

Variant III: Less Than K

def twoSumLessThanK(nums: List[int], k: int) -> int:
    nums.sort()
    i, j = 0, len(nums) - 1
    ans = -1
    while i < j:
        if (two_sum := nums[i] + nums[j]) >= k:
            j -= 1
        else:
            ans = max(ans, two_sum)
            i += 1
    return ans

Time complexity: O(nlogn)

Space complexity: O(n) – Python uses timsort which has worst case linear space complexity.

Variant IV: Three Sum

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    for i, a in enumerate(nums):
        if a > 0:
            break
        if i > 0 and a == nums[i-1]:
            continue
        for b, c in two_sum(nums, i+1, -a):
            result.append([a, b, c])
    return result
    
def two_sum(nums, start_index, target):
    i, j = start_index, len(nums) - 1
    while i < j:
        x, y = nums[i], nums[j]
        if i > start_index and nums[i-1] == x:
            i += 1
            continue
        if x + y == target:
            yield x, y
            i += 1
            j -= 1
        elif x + y < target:
            i += 1
        else:
            j -= 1

Time Complexity: O(n^2)

Space Complexity: O(n)