How to solve Two Sum Problem | 2 Solutions

The Two Sum problem is one of the most popular algorithmic problems that is frequently asked in technical interviews. This problem tests your ability to think algorithmically and optimize for efficiency. In this article, we’ll break down the Two Sum problem, explore different approaches, and provide a complete Java solution. By the end, you’ll be confident in your understanding of how to solve this problem efficiently.

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]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Approach Overview

The problem seems simple, but its efficiency can vary greatly based on the approach you take. Let’s look at a few ways to solve it.

Brute Force Approach

The first and most intuitive approach is brute force. The idea here is to check each pair of numbers to see if they sum up to the target.

Code in Java:

public class TwoSum {
    public int[] twoSum(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");
    }

    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] result = ts.twoSum(new int[] {2, 7, 11, 15}, 9);
        System.out.println("Indices: " + result[0] + ", " + result[1]);
    }
}

Time Complexity:

• Time Complexity: O(n²), because for each element, you iterate over all other elements.
• Space Complexity: O(1), since you are not using any extra space.

This solution is easy to understand but inefficient for large arrays due to its O(n²) time complexity. It iterates through each possible pair of numbers, which becomes slow for large inputs.

Optimized Approach Using HashMap

A better approach to solve this problem involves using a HashMap. By keeping track of each number and its index as you iterate through the array, you can reduce the time complexity to O(n).

The idea is simple:

• As you iterate through the array, check if target - current number exists in the HashMap.
• If it does, return the indices of the current number and the number stored in the HashMap.
• If it doesn’t, store the current number and its index in the HashMap.

Code in Java:

import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        HashMap<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");
    }

    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] result = ts.twoSum(new int[] {2, 7, 11, 15}, 9);
        System.out.println("Indices: " + result[0] + ", " + result[1]);
    }
}

Time Complexity:

• Time Complexity: O(n), because you only iterate through the array once.
• Space Complexity: O(n), due to the HashMap storing elements.

This optimized solution runs in linear time, making it much more efficient for larger arrays. The trade-off is that it uses additional space to store elements in the HashMap, but this space complexity is still manageable.

Conclusion

The Two Sum problem is a classic coding problem that is important for both beginners and seasoned developers. We started by discussing the brute-force approach and then optimized the solution using a HashMap to achieve O(n) time complexity.

By understanding both the brute-force and optimized approaches, you can confidently solve the Two Sum problem in any coding interview or competitive programming scenario.

Also visit Sliding Window Maximum