Start learning free

LESSON 258 OF 410 · HASH TABLE

Two Sum IV in O(n) Time Complexity using Java

Practice O(n) Read the full explanation

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Note:

Your algorithm should run in O(n) time and use O(n) space.


Hints:

This the type of problem where we optimize the brute force approach to get the optimal one. The brute force approach took O(n^2) time because we had two nested for loops, one for i and another one j. In order to get O(n), we have to reduce this to only one for loop, so we should fix only one index, let it be j, the index of the second number. We will try out each possible j, and for each of them we should check if there is an index i < j such that nums[i] + nums[j] == target: 
for each j : 0 -> n - 1:
	// We know nums[j]. Find some index i < j such that nums[i] + nums[j] == target.
How can we find that index in O(1)?

nums[i] + nums[j] == target ⇔ nums[i] == target - nums[j]. So for each j, we should look for an element equal to target - nums[j] from the left of j. Is there a data structure that allows us to look for an element in a collection in constant time? How can we use it here?

That data structure is the Hash Map. We can have a Hash Map where we insert all the elements nums[j] we iterate on during the for loop. In this way, for each j, we can look in the Hash Map to see if there is some element of value target - nums[j] and if so, we found a solution: 
for each j : 0 -> n - 1:
	- Look for target - nums[j] in the Hash Map. If there exists, we found the solution.
	- Otherwise, insert nums[j] into the Hash Map and continue with the for loop.
I know the code above is not perfect. Hash Maps work with pairs (key => value), we cannot just insert a nums[j] into a Hash Map. What should we actually insert in this hash map? What are the keys and what are the values?

The problem with the code above is that we just check if there is an element equal to target - nums[j]. If so, we have a solution, but that's not enough. The problem asks us to return the indices of those elements and we only know of them: j. Can we adapt the solution such that if for some j there is an element equal to target - nums[j], we can also get its index?

The pairs in the Hash Map should be nums[j] => j so that for each element we insert, we can also get its index: 
for each j : 0 -> n - 1:
	if target - nums[j] in indexOfValue:
		return [indexOfValue[target - nums[j]], j]
	indexOfValue[nums[j]] = j
return [-1, -1]

STEP 1 OF 5
    Ctrl + Enter to check

    JAVA · HASH TABLE

    Two Sum in Java, explained

    Understanding the Problem

    The core challenge of this problem is to find two indices in an array such that the elements at these indices sum up to a given target. This problem is significant in various applications, such as financial transactions, where you need to find pairs of transactions that sum up to a specific amount.

    Potential pitfalls include not considering that the same index cannot be used twice and ensuring that the solution is efficient in terms of time complexity.

    Approach

    To solve this problem, we can start with a naive approach and then optimize it:

    Naive Solution

    The naive solution involves using two nested loops to check all possible pairs of indices. This approach has a time complexity of O(n^2), which is not efficient for large arrays.

    Optimized Solution

    To achieve an O(n) time complexity, we can use a HashMap to store the elements and their indices as we iterate through the array. For each element, we check if the complement (target - current element) exists in the HashMap. If it does, we have found our solution.

    Algorithm

    Here is a step-by-step breakdown of the optimized algorithm:

    1. Initialize an empty HashMap to store elements and their indices.
    2. Iterate through the array.
    3. For each element, calculate its complement (target - current element).
    4. Check if the complement exists in the HashMap.
    5. If it exists, return the indices of the current element and the complement.
    6. If it does not exist, add the current element and its index to the HashMap.
    7. If no solution is found, return [-1, -1].

    Code Implementation

    import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // Create a HashMap to store the value and its index
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // Iterate through the array
        for (int i = 0; i < nums.length; i++) {
            // Calculate the complement
            int complement = target - nums[i];
            
            // Check if the complement exists in the map
            if (map.containsKey(complement)) {
                // If it exists, return the indices
                return new int[] { map.get(complement), i };
            }
            
            // If it does not exist, add the current element and its index to the map
            map.put(nums[i], i);
        }
        
        // If no solution is found, return [-1, -1]
        return new int[] { -1, -1 };
    }
}

    Complexity Analysis

    The time complexity of this approach is O(n) because we only iterate through the array once. The space complexity is also O(n) due to the HashMap storing up to n elements.

    Edge Cases

    Potential edge cases include:

    • An empty array: The function should return [-1, -1].
    • An array with no valid pairs: The function should return [-1, -1].
    • Negative numbers and zero: The function should handle these correctly.

    Testing

    To test the solution comprehensively, consider the following test cases:

    public static void main(String[] args) {
    TwoSum ts = new TwoSum();
    
    // Test case 1: Normal case
    int[] result1 = ts.twoSum(new int[] {2, 7, 11, 15}, 9);
    System.out.println(Arrays.toString(result1)); // Expected: [0, 1]
    
    // Test case 2: No solution
    int[] result2 = ts.twoSum(new int[] {1, 2, 3}, 7);
    System.out.println(Arrays.toString(result2)); // Expected: [-1, -1]
    
    // Test case 3: Negative numbers
    int[] result3 = ts.twoSum(new int[] {-1, -2, -3, -4, -5}, -8);
    System.out.println(Arrays.toString(result3)); // Expected: [2, 4]
    
    // Test case 4: Zero and negative numbers
    int[] result4 = ts.twoSum(new int[] {0, 4, 3, 0}, 0);
    System.out.println(Arrays.toString(result4)); // Expected: [0, 3]
}

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the problem requirements and constraints thoroughly.
    • Start with a brute force solution to understand the basic logic.
    • Think about how to optimize the solution using data structures like HashMaps.
    • Consider edge cases and test your solution comprehensively.

    Conclusion

    In this blog post, we discussed the Two Sum problem and provided an optimized solution using a HashMap in Java. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free