Two Sum in O(n^2) Time Complexity using Java

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

For this lesson, your algorithm should run in O(n^2) time and use O(1) extra space.
(There exist faster solutions which we will discuss in future lessons)

Understanding the Problem

The core challenge of the "Two Sum" problem is to find two distinct indices in an array such that the numbers at those indices add 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 assuming that there are multiple solutions or using the same index twice. It's crucial to ensure that the indices are distinct and that the solution is unique.

Approach

To solve this problem, we can start with a naive approach and then discuss more optimized solutions.

Naive Solution

The naive solution involves using two nested loops to check every possible pair of numbers in the array. This approach is straightforward but not optimal, as it has a time complexity of O(n^2).

Optimized Solution

We can optimize the solution using a hash map to store the indices of the numbers we have seen so far. This allows us to check in constant time if the complement of the current number (i.e., target - current number) exists in the hash map.

Algorithm

Naive Approach

public int[] twoSum(int[] nums, int target) {
    // Iterate through each element in the array
    for (int i = 0; i < nums.length - 1; i++) {
        // For each element, iterate through the remaining elements
        for (int j = i + 1; j < nums.length; j++) {
            // Check if the sum of the two elements equals the target
            if (nums[i] + nums[j] == target) {
                // Return the indices of the two elements
                return new int[] { i, j };
            }
        }
    }
    // If no solution is found, return [-1, -1]
    return new int[] { -1, -1 };
}

Optimized Approach

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

public int[] twoSumOptimized(int[] nums, int target) {
    // Create a hash map to store the indices of the numbers
    Map<Integer, Integer> map = new HashMap<>();
    // Iterate through each element in the array
    for (int i = 0; i < nums.length; i++) {
        // Calculate the complement of the current number
        int complement = target - nums[i];
        // Check if the complement exists in the hash map
        if (map.containsKey(complement)) {
            // Return the indices of the two elements
            return new int[] { map.get(complement), i };
        }
        // Add the current number and its index to the hash map
        map.put(nums[i], i);
    }
    // If no solution is found, return [-1, -1]
    return new int[] { -1, -1 };
}

Complexity Analysis

The naive approach has a time complexity of O(n^2) and a space complexity of O(1). The optimized approach has a time complexity of O(n) and a space complexity of O(n) due to the hash map.

Edge Cases

Potential edge cases include:

• An empty array: The function should return [-1, -1].
• An array with one element: The function should return [-1, -1].
• No solution exists: The function should return [-1, -1].

Testing

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

• Simple case: nums = [2, 7, 11, 15], target = 9 (Expected output: [0, 1])
• No solution: nums = [1, 2, 3], target = 6 (Expected output: [-1, -1])
• Multiple pairs: nums = [1, 3, 3, 4], target = 6 (Expected output: [1, 2])

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

• Understand the problem requirements and constraints.
• Start with a brute force solution to get a feel for the problem.
• Think about how to optimize the solution using data structures like hash maps.
• Consider edge cases and test your solution thoroughly.

Conclusion

The "Two Sum" problem is a classic example of using brute force and then optimizing the solution using a hash map. Understanding and solving such problems is crucial for developing problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice problems, consider the following resources:

• LeetCode Two Sum Problem
• GeeksforGeeks Two Sum Problem
• HackerRank 10 Days of JavaScript