Two Sum Solution

In this tutorial, we will solve the Two Sum problem using three different approaches :brute force, hash table, and two-pointer technique. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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

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

You can return the answer in any order.

Examples

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

• $2 \leq \text{nums.length} \leq 10^4$
• $-10^9 \leq \text{nums[i]} \leq 10^9$
• $-10^9 \leq \text{target} \leq 10^9$
• Only one valid answer exists.

Follow up: Can you come up with an algorithm that is less than $O(n^2)$ time complexity?

---

Solution for Two Sum Problem

Intuition and Approach

The problem can be solved using a brute force approach, a hash table, or the two-pointer technique. The brute force approach has a time complexity of $O(n^2)$, while the hash table and two-pointer techniques have a time complexity of $O(n)$. The hash table approach is the most efficient and is recommended for large inputs.

• Brute Force
• Hash Table
• Two Pointer

Approach 1: Brute Force (Naive)

The brute force approach is simple. We iterate through each element nums[i] and check if there is another element nums[j] such that nums[i] + nums[j] == target. If we find such a pair, we return the indices [i, j].

Implementation

Live Editor

function twoSumProblem() {
  const nums = [2, 7, 11, 15];
  const target = 9;
  const twoSum = function (nums, target) {
    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 [];
  };

  const result = twoSum(nums, target);
  return (
    <div>
      <p>
        <b>Input:</b> nums = {"[" + nums.join(", ") + "]"}, target = {target}
      </p>
      <p>
        <b>Output:</b> {"[" + result.join(", ") + "]"}
      </p>
    </div>
  );
}

Result

Loading...

Codes in Different Languages

JavaScript

Written by @ajay-dhangar

 function twoSum(nums, target) {
   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 [];
 }

TypeScript

Written by @ajay-dhangar

 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];
       }
     }
   }

   return [];
 }

Python

Written by @ajay-dhangar

 class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
     for i in range(len(nums)):
         for j in range(i + 1, len(nums)):
             if nums[i] + nums[j] == target:
                return [i, j]

     return []

Java

Written by @ajay-dhangar

 class Solution {
     public int[] twoSum(int[] nums, int target) {
         for (int i = 0; i < nums.length; i++) {
             for (int j = i + 1; j < nums.length; j++) {
                 if (nums[i] + nums[j] == target) {
                     return new int[] {i, j};
                 }
             }
         }

         return new int[0];
     }
 }

C++

Written by @ajay-dhangar

 class Solution {
 public:
     vector<int> twoSum(vector<int>& nums, int target) {
         for (int i = 0; i < nums.size(); i++) {
             for (int j = i + 1; j < nums.size(); j++) {
                 if (nums[i] + nums[j] == target) {
                     return {i, j};
                 }
             }
         }

         return {};
     }
 };

Complexity Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$
• Where n is the length of the input array nums.
• The time complexity is $O(n^2)$ because we are iterating through the array twice.
• The space complexity is $O(1)$ because we are not using any extra space.
• This approach is not efficient and is not recommended for large inputs.

Note

Which is the best approach? and why?

The hash table approach is the most efficient and is recommended for large inputs. The hash table lookup has an average time complexity of $O(1)$, which makes this approach efficient. The time complexity of the hash table approach is $O(n)$, which is better than the brute force approach with a time complexity of $O(n^2)$ and the two-pointer approach with a time complexity of $O(n \log n)$. The space complexity of the hash table approach is $O(n)$, which is the same as the two-pointer approach. Therefore, the hash table approach is the best approach for this problem.

---

Video Explanation of Two Sum Problem

English

---

JavaScript

Python

Java

Hindi

---

Authors:

Loading...