The Two Sum problem is a popular coding challenge used in many technical interviews. It involves finding two numbers in an array that add up to a given target. This problem helps developers demonstrate their ability to use algorithms efficiently and manipulate data structures like arrays and hashmaps. In this post, we’ll walk through how to solve the Two Sum problem in TypeScript, explaining both the brute-force approach and an optimized solution using a hashmap.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Constraints:

  1. You can assume there is exactly one solution.
  2. You cannot use the same element twice.

Example:

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

Step-by-Step Solution

Step 1: Brute-Force Approach

The brute-force method is the most straightforward way to solve this problem. You can iterate over each element of the array and check every other element to find two numbers that add up to the target.

Approach:

  1. Iterate through each number in the array.
  2. For each number, iterate through the rest of the array to check if any pair of numbers adds up to the target.
  3. Return the indices of the two numbers if found.

TypeScript Code (Brute Force):

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    throw new Error("No two sum solution");
}

Explanation:

  • The outer loop goes through each number in the array.
  • The inner loop checks if any subsequent number adds up to the target when combined with the current number.
  • If a match is found, the function returns the indices of the two numbers.

Time Complexity:

  • Time Complexity: O(n^2) — This approach involves nested loops, so its performance degrades with larger input sizes.

Example:

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

Step 2: Optimized Approach Using a Hashmap

The brute-force solution works but is inefficient for large datasets. To improve this, we can use a hashmap (or dictionary) to store the numbers we've seen as we iterate through the array, allowing for a much faster lookup.

Optimized Approach:

  1. Initialize an empty hashmap (or dictionary) to store the number and its index as key-value pairs.
  2. As you iterate through the array, compute the difference between the target and the current number.
  3. Check if this difference is already in the hashmap.
    • If it is, return the current index and the index from the hashmap.
    • If it isn’t, add the current number and its index to the hashmap for future reference.

TypeScript Code (Optimized Solution):

function twoSum(nums: number[], target: number): number[] {
    const numMap: { [key: number]: number } = {};  // Create a hashmap
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];  // Calculate the difference
        
        if (complement in numMap) {
            return [numMap[complement], i];  // Return indices if complement exists
        }
        
        numMap[nums[i]] = i;  // Store the number and its index in the hashmap
    }
    
    throw new Error("No two sum solution");
}

Explanation:

  • numMap is used to store each number and its index as we iterate through nums.
  • For each number, calculate the complement (i.e., target - currentNumber). If this complement exists in the map, we’ve found our solution.
  • If not, store the current number and its index in the map for future checks.

Example:

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

How It Works:

  1. For nums[0] = 2, complement = 9 - 2 = 7. The hashmap is empty, so store 2 in the map.
  2. For nums[1] = 7, complement = 9 - 7 = 2. Since 2 is already in the hashmap, return the indices of 2 and 7.

Time Complexity:

  • Time Complexity: O(n) — We only pass through the array once, and each lookup or insertion into the hashmap takes constant time.
  • Space Complexity: O(n) — The hashmap can store up to n elements in the worst case.

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    const nums = [-3, 4, 3, 90];
const target = 0;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 2]

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    const nums = [3, 3];
const target = 6;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 1]

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    const nums = [1, 4];
const target = 5;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 1]

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    const nums = [0, 4, 3, 0];
const target = 0;
const result = twoSum(nums, target);
console.log(result);  // Output: [0, 3]

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    const nums = Array.from({ length: 100000 }, (_, i) => i);
const target = 199999;
const result = twoSum(nums, target);
console.log(result);  // Output: [99998, 99999]

Conclusion

The Two Sum problem demonstrates the power of using a hashmap (or dictionary) to optimize algorithms. By carefully analyzing the problem and leveraging efficient data structures, you can significantly reduce time complexity from O(n^2) to O(n). This problem is not only common in coding interviews but also a great example of how understanding the right tools can drastically improve performance in real-world applications.

By mastering the Two Sum problem in TypeScript, you’ll build a stronger understanding of algorithmic problem-solving, which will help you tackle more complex coding challenges in the future.