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

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:

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 will always be a solution or using the same index twice, which is not allowed.

Approach

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

Naive Solution

The naive solution involves checking all possible pairs of numbers to see if they add up to the target. This can be achieved using two nested loops:

for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] === target) {
            return [i, j];
        }
    }
}
return [-1, -1];

This approach has a time complexity of O(n^2) because it involves two nested loops, each iterating through the array.

Optimized Solution

While the naive solution works, it is not efficient for large arrays. A more optimized solution involves 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

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

Initialize an empty hash map.
Iterate through the array.
For each number, calculate its complement (target - current number).
Check if the complement exists in the hash map.
If it exists, return the indices of the current number and its complement.
If it does not exist, add the current number and its index to the hash map.
If no solution is found by the end of the loop, return [-1, -1].

Code Implementation

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
    // Initialize an empty hash map
    const map = new Map();
    
    // Iterate through the array
    for (let i = 0; i < nums.length; i++) {
        // Calculate the complement
        const complement = target - nums[i];
        
        // Check if the complement exists in the hash map
        if (map.has(complement)) {
            // Return the indices of the current number and its complement
            return [map.get(complement), i];
        }
        
        // Add the current number and its index to the hash map
        map.set(nums[i], i);
    }
    
    // If no solution is found, return [-1, -1]
    return [-1, -1];
}

// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // Output: [0, 1]

Complexity Analysis

The time complexity of the optimized solution is O(n) because we only iterate through the array once. The space complexity is also O(n) because we store the indices in a 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 two numbers add up to the target: The function should return [-1, -1].

Testing

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

console.log(twoSum([], 9)); // Output: [-1, -1]
console.log(twoSum([1], 9)); // Output: [-1, -1]
console.log(twoSum([2, 7, 11, 15], 9)); // Output: [0, 1]
console.log(twoSum([3, 2, 4], 6)); // Output: [1, 2]
console.log(twoSum([3, 3], 6)); // Output: [0, 1]

Thinking and Problem-Solving Tips

When approaching such problems, it is 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 by reducing time and space complexity.
Consider using data structures like hash maps to achieve constant time lookups.

Conclusion

In this blog post, we discussed the "Two Sum" problem, explored a naive solution, and then optimized it 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 related to the topic, consider the following resources: