leet code : Two sum Problem solution – Java || CPP || JavaScript || Python

In this article, we will be discussing the two sum problem and how it can be solved using the programming languages C++, Java, and Python

Problem Statement

two sum java

​
This is another article in the series leetcode problem solutions and this article is a solution to leetcode 1 two sum problem.

There are many ways to solve this problem, but we will be focusing on three methods: a brute force approach, a sorting approach, and a hashtable approach. We will be discussing the time complexity and space complexity of each method as well as any trade-offs that need to be made.

Once you have a good understanding of two sum problem, it should help you solve advanced level problems like three sum which in some ways a continuation of the two sum problem.

Consider you are given an array of integers and a target sum, return indices of two numbers in the array such that they add up to the given target. You may assume that each input would have exactly one solution. Also, you cannot use the same element twice. You are allowed to return the answer in any order.

Example
​
Example 1:

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

Input: nums = [7,3,5], target = 8
Output: [1,2]

Solution:

First, let us attempt to comprehend the issue statement. We are provided an array of integer items as well as a goal total. Our task is to build an algorithm that returns the indices of two entries in this array so that when we combine these two elements, the total should equal the goal amount.

In example 1, the supplied array is [7,2,13,11], and the specified goal total is 9. Looking at the supplied array, the pair that adds to the goal total 9 is (7,2), i.e. 7+2 = 9. As a consequence, our method should return(0,1) as the result because they are the indices of items 7 and 2 in the supplied array, respectively.

Use of Force

A simple approach to this problem is to look for every possible pair in the supplied array.

We must do the following steps for a given input array nums:

Run two loops to test each combination in the supplied array.

To acquire all potential pairs, fix the outer loop at a given index and shift the inner loop. The outer loop extends from i=0 to i=n-2, whereas the inner loop extends from j=i+1 to j=n-1.

Check if the integers represented by the outside and inner loop indexes add up to the goal total in each iteration of the inner loop.

If nums[outerLoopIndex] + nums[innerLoopIndex] equals target, the outcome is outerLoopIndex, innerLoopIndex. Otherwise, keep iterating to ensure

2) Hashmap is the second solution.

This issue can be solved in linear time. The concept is to utilise a hashmap to record the indices of previously visited items. The “key” of a hashmap is the number in the specified input array (You add this to the hashmap as you visit each element). The index of the number in the array represented by the hashmap key is the hashmap “value.”

This method performs the following stages for a given input array:

• Make a hashmap with integer datatypes as keys and values.
• Iterate through each element in the specified array, beginning with the first.
• Check the hashmap for the presence of the needed number (required number = goal sum – current number) in each iteration.
• If present, return the result necessary number index, current number index.
• Otherwise, add the current iteration number as a key to the hashmap and its index as a value. Repeat until you discover the answer.

Simulation

Consider the following input array with goal = 24.

Let currIdx be the variable representing the currently processed element, and idxMap be our index map. Orange cells represent the array member that is presently being processed.

As indicated in the first figure below, currIdx = 0 and idxMap is empty at the start. Then we check to see if the needed number = target – current number exists in the idxMap.

Because the required number = 24 – 7 = 17 is not present in our hashmap, we add 7 as an idxMap key and 0 as an idxMap value.

JAVA

There are many ways to solve the two sum problem in Java. One way is to use a brute force approach, which is to try every possible combination of numbers until you find a pair that sums to the target number. Another way is to use a hash table, which can be used to store all the possible sums and their corresponding indices.

If you’re looking for a more efficient solution, you can use a sorting algorithm such as quicksort or heapsort. Once the array is sorted, you can iterate through it and find the pair that sums to the target number. This solution has a time complexity of O(n log n).

If you have any questions about solving two sum in Java, feel free to leave a comment below!

Map hm = new HashMap();
    for(int i=0;i {
         hm.put(nums[i],i);
}
for(int i=0;i {
   int k =nums[i];
   if(k == target && hm.containsKey(0) )
  {
         arr[0]= i;
         arr[1]=hm.get(0);
         break;
  }
else if(hm.containsKey(target-k) )
{
   if(hm.get(target-k)>i)
     {      arr[0]= i;
             arr[1]=hm.get(target-k);
              break;} 
  }
}
   return arr;
}

CPP:

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> visited;
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
            int n = nums[i];
            int complement = target - n;
            if (visited.count(complement)) {
                return {visited[complement], i};
            }
            visited[n] = i;  // assume that each input would have exactly one solution
        }
        return {};
    }
}; 

Python :

Python is a programming language with many features and libraries that can be used to solve a variety of problems. One such problem is the Two Sum problem, which can be solved using a variety of methods.

Time Complexity brute force search.

Finally, another approach that can be used to solve the Two Sum problem is to use a brute force search. This approach works by iterating through all pairs of numbers in the array and checking if their sum equals the target sum. The time complexity of this approach is O(n^2), which makes it less efficient than other methods.

Time Complexity hash table

The most common method for solving the Two Sum problem is to use a hash table. This approach works by iterating through the array of numbers and inserting each number into a hash table. If the number being inserted is already in the hash table, then it is considered a sum. The time complexity of this approach is O(n), where n is the size of the array.

Two pointers

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        int a[n];
        //3 2 4
    //sorted arr 2 3 4 //l=0,r=2 check value at l and r and match with the copy of given array element 
     for(int i=0;i<nums.size();i++){
         a[i]=nums[i];
     }
        vector<int>v;
        sort(nums.begin(),nums.end());
               int l=0,r=nums.size()-1;
        while(l<r){
            if(nums[l]+nums[r]==target){
              
             break;
            }
            else if(nums[l]+nums[r]>target){
                r--;
            }
            else{
                l++;
            }
        }
        for(int i=0;i<n;i++){
            if(nums[l]==a[i]){
                v.push_back(i);
            }
            else if(nums[r]==a[i]){
                v.push_back(i);
            }
        }
        
        return v;
    }

};

Another approach that can be used to solve the Two Sum problem,firtly make the copy of array and then sort the array and then use two pointers, one from each end of the array, to find the sum. This approach has a time complexity of O(n log n) due to the need to sort the array.

Algorithm Working

The program starts by creating a copy of the nums array called a. Then, it sorts the nums array in ascending order using the sort() function from the STL library.

Next, the program initializes two pointers l and r to the beginning and end of the sorted array, respectively. The program enters a while loop that continues until l is greater than or equal to r. At each iteration, the program checks whether the sum of the integers at l and r is equal to the target. If it is, the program exits the loop. If the sum is greater than the target, the program decrements r. If the sum is less than the target, the program increments l.

After the while loop, the program loops through the original nums array and checks whether each element is equal to either nums[l] or nums[r]. If an element is equal to either nums[l] or nums[r], its index is added to the vector v.

Finally, the program returns the vector v containing the indices of the two numbers that add up to the target.

class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       seen = {}
       for i, value in enumerate(nums):
           remaining = target - nums[i]
           
           if remaining in seen:
               return [i, seen[remaining]]
            
           seen[value] = i 

Python

def twoSum(nums, target):
    n = len(nums)
    a = nums.copy()

    nums.sort()

    l = 0
    r = n - 1

    while l < r:
        sum = nums[l] + nums[r]

        if sum == target:
            break
        elif sum > target:
            r -= 1
        else:
            l += 1

    v = []

    for i in range(n):
        if nums[l] == a[i]:
            v.append(i)
        elif nums[r] == a[i]:
            v.append(i)

    return v

JavaScript Solution :

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const n = nums.length;
  const a = [...nums];

  nums.sort((a, b) => a - b);

  let l = 0;
  let r = n - 1;

  while (l < r) {
    const sum = nums[l] + nums[r];

    if (sum === target) {
      break;
    } else if (sum > target) {
      r--;
    } else {
      l++;
    }
  }

  const v = [];

  for (let i = 0; i < n; i++) {
    if (nums[l] === a[i]) {
      v.push(i);
    } else if (nums[r] === a[i]) {
      v.push(i);
    }
  }

  return v;

};

Dart Solution :

List<int> twoSum(List<int> nums, int target) {
  final n = nums.length;
  final a = [...nums];

  nums.sort();

  var l = 0;
  var r = n - 1;

  while (l < r) {
    final sum = nums[l] + nums[r];

    if (sum == target) {
      break;
    } else if (sum > target) {
      r--;
    } else {
      l++;
    }
  }

  final v = [];

  for (var i = 0; i < n; i++) {
    if (nums[l] == a[i]) {
      v.add(i);
    } else if (nums[r] == a[i]) {
      v.add(i);
    }
  }

  return v;
}

In this article, you have learned how to solve the Two Sum problem using C++, Java, and Python. You have also seen how the ThreeSum problem can be solved as a special case of the TwoSum problem. I hope you have found this article helpful and that you now have a better understanding of how to solve these types of problems.