Two Sum Solution for Amazon

Company: Amazon · Difficulty: Easy · Topics: Array, Hash Table, Two Pointers, Sorting

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.

Examples

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]

Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 6, we return [0, 1].

Example 4:

Input: nums = [1,5,8,10,13,18,21,25,30], target = 23

Output: [3,4]

Explanation: Because nums[3] + nums[4] == 23, we return [3, 4].

Intuition

The key insight is that for each number, we need to find its complement (target - current_number) in the array. If we can find this complement efficiently, we've solved the problem.

Approach

Approach 1: Hash Table (Optimal)

1. Create a hash table to store numbers and their indices

2. Iterate through the array

3. For each number, calculate its complement (target - current_number)

4. If complement exists in hash table, return [complement_index, current_index]

5. Otherwise, add current number and its index to hash table

Approach 2: Two Pointer (Requires Sorting)

1. Sort the array with their original indices

2. Use two pointers: left at start, right at end

3. If sum of elements at pointers equals target, return their original indices

4. If sum is less than target, move left pointer right

5. If sum is greater than target, move right pointer left

Approach 3: Brute Force

1. Use nested loops to check all pairs

2. For each pair, check if their sum equals target

3. Return indices when found

Dry Run

Let's trace through Example 1: nums = [2,7,11,15], target = 9

Hash Table Approach:

i=0, num=2: complement = 9-2 = 7, not in hash table, add {2:0}
i=1, num=7: complement = 9-7 = 2, found in hash table at index 0
Return [0,1]

Two Pointer Approach:

After sorting with indices: [(2,0), (7,1), (11,2), (15,3)]
left=0, right=3: 2+15=17 > 9, move right to 2
left=0, right=2: 2+11=13 > 9, move right to 1
left=0, right=1: 2+7=9 == target, return [0,1]

Brute Force Approach:

Check pairs: (2,7), (2,11), (2,15), (7,11), (7,15), (11,15)
Found: 2+7=9, return [0,1]

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Hash Table (Optimal)

Time Complexity: O(n) - We traverse the array only once

Space Complexity: O(n) - We store at most n elements in the hash table

Solution 2: Two Pointer (Requires Sorting)

Time Complexity: O(n log n) due to sorting

Space Complexity: O(n) to store original indices

Solution 3: Brute Force

Time Complexity: O(n²) - We check n(n-1)/2 pairs

Space Complexity: O(1) - No extra space needed