LeetCode: Two Sum

The "Two Sum" problem is a classic coding interview question that involves finding two numbers in an array that add up to a specific target sum. This problem tests your ability to use data structures and algorithms effectively to solve real-world challenges. In this article, we'll explore how to solve the Two Sum problem using TypeScript and discuss different approaches.

Problem Statement

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

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

Approach 1: Brute Force

The brute force approach involves checking every pair of numbers in the array to see if their sum equals the target. This approach has a time complexity of O(n^2) and is not very efficient.

function twoSumBruteForce(nums: number[], target: number): number[] | undefined {
  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]
      }
    }
  }
  return undefined
}

Approach 2: Using a Hash Map

A more efficient approach involves using a hash map to store each number and its corresponding index as we iterate through the array. For each number, we can check if the difference between the target and the current number exists in the hash map. If it does, we've found a valid pair.

function twoSumHashMap(nums: number[], target: number): number[] | undefined {
  const numToIndex = new Map<number, number>()

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (numToIndex.has(complement)) {
      return [numToIndex.get(complement)!, i]
    }
    numToIndex.set(nums[i], i)
  }

  return undefined
}

Conclusion

Solving the "Two Sum" problem on LeetCode requires a careful consideration of data structures and algorithms. In this article, we discussed two approaches to solve the problem using TypeScript: the brute force approach and the hash map approach. The hash map approach is more efficient and has a time complexity of O(n).

Resources

To learn more about algorithms and problem-solving, you can explore the following resources:

By practicing and understanding different problem-solving techniques, you'll be better equipped to tackle similar challenges in coding interviews and real-world scenarios.

Happy coding!