Two Sum III - O(n log n) Time Complexity in 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:

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

Understanding the Problem

The core challenge of this problem is to find two distinct indices in the array such that the sum of the elements at these indices equals the target value. 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 using the same index twice or not considering that there might be no solution.

Approach

To solve this problem, we can use a hash map to store the difference between the target and each element as we iterate through the array. This allows us to check in constant time if the complement of the current element exists in the hash map.

Naive Solution

A naive solution would involve using two nested loops to check all possible pairs of elements. This approach has a time complexity of O(n^2), which is not optimal for large arrays.

Optimized Solution

An optimized solution involves using a hash map to store the indices of the elements as we iterate through the array. This allows us to find the complement of the current element in constant time, resulting in an overall time complexity of O(n).

Algorithm

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

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

Code Implementation

/**
 * Function to find two indices such that their values add up to the target.
 * @param {number[]} nums - Array of integers.
 * @param {number} target - Target sum.
 * @return {number[]} - Indices of the two numbers.
 */
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 element and its complement
            return [map.get(complement), i];
        }
        
        // Add the current element 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 this solution is O(n) because we iterate through the array once. The space complexity is also O(n) due to the hash map storing up to n elements.

Edge Cases

Potential edge cases include:

An empty array: The function should return [-1, -1].
An array with no solution: 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:

// Test case 1: Normal case
console.log(twoSum([2, 7, 11, 15], 9)); // Output: [0, 1]

// Test case 2: No solution
console.log(twoSum([1, 2, 3], 7)); // Output: [-1, -1]

// Test case 3: Negative numbers
console.log(twoSum([-1, -2, -3, -4, -5], -8)); // Output: [2, 4]

// Test case 4: Zero and negative numbers
console.log(twoSum([0, 4, 3, 0], 0)); // Output: [0, 3]

// Test case 5: Empty array
console.log(twoSum([], 0)); // Output: [-1, -1]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Think about different data structures that can help optimize the solution.
Break down the problem into smaller, manageable parts.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the Two Sum problem, explored a naive and an optimized solution, and provided a detailed explanation of the algorithm and its implementation in JavaScript. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: