Two Sum Problem

The Array Two Sum Problem is a classic problem in computer science and programming. It is often asked in coding interviews and serves as a good exercise for beginners to learn about arrays, loops, and hash maps. In this blog, we will explore the problem statement, understand different approaches to solve it, and analyze the time and space complexity of each solution.

Problem Statement

Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to the target.

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

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 = [5, 3, 1, 7, 8], target = 10
Output: [1, 3]
Explanation: Because nums[1] + nums[3] == 10, we return [1, 3].

Practice: Leetcode Link

Brute Force Solution

The brute force approach is the simplest and involves checking all pairs of numbers to see if they add up to the target. This approach has a time complexity of O(n²).

Algorithm

1. Initialize two nested loops.
2. For each pair of elements in the array, check if they add up to the target.
3. If they do, return their indices.
4. If no such pair is found, return an empty array.

Java Code

package codeKatha;

public class TwoSum {

    public int[] twoSumBruteForce(int[] nums, int target) {
    
        for (int i = 0; i < nums.length; i++) {
        
            for (int j = i + 1; j < nums.length; j++) {
            
                if (nums[i] + nums[j] == target) {
                
                    return new int[] { i, j };
                    
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Dry Run for Brute Force Solution

Consider the input array [2, 7, 11, 15] with target 9:

Step-by-step Execution:
1. i = 0, j = 1:
   - nums[0] = 2
   - nums[1] = 7
   - Check: 2 + 7 = 9 (matches target)
   - Solution found: return [0, 1]
2. Since we found a solution, the loop stops and we return the indices [0, 1].

Explanation:

We start with the first element (index 0) and check it against all other elements in the array. When we reach the second element (index 1), we find that their sum is equal to the target (9). Therefore, we return the indices [0, 1].

Time and Space Complexity

Time Complexity: O(n²) because we have two nested loops. Space Complexity: O(1) since we are not using any extra space except for the variables.

Optimal Solution Using Hash Map

A more efficient solution uses a hash map to store the indices of the elements. This approach reduces the time complexity to O(n).

Algorithm

1. Initialize an empty hash map.
2. Loop through the array.
3. For each element, check if the complement (target - element) exists in the hash map.
4. If it does, return the indices.
5. If it doesn't, add the element and its index to the hash map.

Java Code

package codeKatha;

import java.util.HashMap;
import java.util.Map;

public class TwoSum {

    public int[] twoSumOptimal(int[] nums, int target) {
    
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
        
            int complement = target - nums[i];
            
            if (map.containsKey(complement)) {
            
                return new int[] { map.get(complement), i };
                
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Dry Run for Optimal Solution Using Hash Map

Consider the input array [2, 7, 11, 15] with target 9:

Step-by-step Execution:
1. i = 0:
   - nums[0] = 2
   - Complement = target - nums[0] = 9 - 2 = 7
   - Check if 7 is in the map: No
   - Add 2 to the map with index 0: map = {2: 0}
2. i = 1:
   - nums[1] = 7
   - Complement = target - nums[1] = 9 - 7 = 2
   - Check if 2 is in the map: Yes, map[2] = 0
   - Solution found: return [map[2], 1] -> return [0, 1]

Explanation:

We traverse the array while maintaining a hash map to store the values and their indices. For each element, we calculate its complement (the number that, when added to the current element, equals the target). If this complement is already in the map, we have found our solution. Otherwise, we add the current element to the map and continue. In this case, at index 1, we find that the complement of 7 is 2, which is already in the map with index 0. Hence, we return the indices [0, 1].

Time and Space Complexity

Time Complexity: O(n) because we traverse the array once. Space Complexity: O(n) because we store elements in the hash map.

Edge Cases

• Array contains negative numbers: Ensure the solution works with negative numbers.
• No solution: Ensure the function throws an appropriate exception or returns an empty array if no solution exists.
• Multiple solutions: As per the problem statement, assume there is exactly one solution.

Example:

Input: nums = [-2, 1, 4, 3], target = 2
Output: [0, 3]
Explanation: Because nums[0] + nums[3] == 2, we return [0, 3].

With this explanation, we have covered both brute force and optimal solutions to the Array Two Sum Problem. The brute force method is simple to understand but inefficient, while the hash map approach provides a much more efficient solution. Understanding both methods helps in grasping fundamental concepts of problem-solving and algorithm optimization.