Amazon — Two Sum and Variants (HashMap, Sorted, 3Sum, 4Sum)

Two Sum Family

All four variants test the same core insight from different angles.

Two Sum I — Unsorted Array

Python

def twoSum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

Two Sum II — Sorted Array (Two Pointers)

Python

def twoSum(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target: return [l+1, r+1]
        elif s < target: l += 1
        else: r -= 1
    return []

3Sum — Find All Unique Triplets

Python

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif s < 0: l += 1
            else: r -= 1
    return res

JavaScript

function threeSum(nums) {
    nums.sort((a,b)=>a-b); const res=[];
    for(let i=0;i<nums.length-2;i++){
        if(i>0&&nums[i]===nums[i-1])continue;
        let l=i+1,r=nums.length-1;
        while(l<r){const s=nums[i]+nums[l]+nums[r];
            if(s===0){res.push([nums[i],nums[l],nums[r]]);while(l<r&&nums[l]===nums[l+1])l++;while(l<r&&nums[r]===nums[r-1])r--;l++;r--;}
            else if(s<0)l++;else r--;
        }
    }
    return res;
}

Java

import java.util.*;
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums); List<List<Integer>> res=new ArrayList<>();
    for(int i=0;i<nums.length-2;i++){
        if(i>0&&nums[i]==nums[i-1])continue;
        int l=i+1,r=nums.length-1;
        while(l<r){int s=nums[i]+nums[l]+nums[r];
            if(s==0){res.add(Arrays.asList(nums[i],nums[l],nums[r]));while(l<r&&nums[l]==nums[l+1])l++;while(l<r&&nums[r]==nums[r-1])r--;l++;r--;}
            else if(s<0)l++;else r--;
        }
    }
    return res;
}

C++

#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end()); vector<vector<int>> res;
    for(int i=0;i<(int)nums.size()-2;i++){
        if(i>0&&nums[i]==nums[i-1])continue;
        int l=i+1,r=nums.size()-1;
        while(l<r){int s=nums[i]+nums[l]+nums[r];
            if(s==0){res.push_back({nums[i],nums[l],nums[r]});while(l<r&&nums[l]==nums[l+1])l++;while(l<r&&nums[r]==nums[r-1])r--;l++;r--;}
            else if(s<0)l++;else r--;
        }
    }
    return res;
}

C

/* C: sort + two pointers, same logic as C++ above */

4Sum

def fourSum(nums, target):
    nums.sort(); res = []
    for i in range(len(nums)-3):
        if i>0 and nums[i]==nums[i-1]: continue
        for j in range(i+1,len(nums)-2):
            if j>i+1 and nums[j]==nums[j-1]: continue
            l,r = j+1,len(nums)-1
            while l<r:
                s=nums[i]+nums[j]+nums[l]+nums[r]
                if s==target:
                    res.append([nums[i],nums[j],nums[l],nums[r]])
                    while l<r and nums[l]==nums[l+1]: l+=1
                    while l<r and nums[r]==nums[r-1]: r-=1
                    l+=1;r-=1
                elif s<target: l+=1
                else: r-=1
    return res