Two Sum Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: Array, Hash Table
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 to use a hash table to store the complement of each number. For each number, we check if its complement (target - current_number) exists in the hash table.
This works because:
- For each number, we need to find its complement (target - current_number)
- If we can find this complement efficiently, we've solved the problem
- Hash table provides O(1) average lookup time
Approach
Approach 1: Hash Table (Optimal)
1. Initialize an empty hash table
2. For each number in the array:
- Calculate the complement: target - current_number
- If complement exists in hash table, return the indices
- Otherwise, store the current number and its index in hash table
3. If no solution is found, return empty array
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]
Key Insights
1. Complement Strategy: For each number, find its complement (target - num)
2. Hash Table Efficiency: O(1) average lookup time for complements
3. Single Pass: We can solve in one pass through the array
4. Unique Solution: Problem guarantees exactly one solution exists
Edge Cases
1. Two identical numbers: nums = [3,3], target = 6
2. Negative numbers: nums = [-1,-2,-3,-4], target = -7
3. Large numbers: nums = [1000000, 2000000], target = 3000000
4. Minimum array: nums = [1,2], target = 3
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) - Single pass through the array
Space Complexity: O(n) - Space for 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