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

10 / 100

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.

Solution 1: 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.

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.

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

Another approach that can be used to solve the Two Sum problem is to 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.

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 

JavaScript Solution :

 function twoSum(nums: number[], target: number): number[] {
    const map = {}
    for (let index = 0; index < nums.length; index++) {
      const element = nums[index]
      const complement = target - element
      if (map[complement] !== undefined) {
        return [map[complement], index]
      } else {
        map[element] = index
      }
    }
    return []
  }

Dart Solution :

  List<int> twoSum(List<int> nums, int target) {
    List<int> result = <int>[];
    for (var i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      var index = nums.indexOf(complement, i + 1);
      if (nums[index] + nums[i] == target) {
        return result = [i, index];
      }
      break;
    }
    return result;
  }

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.

11 thoughts on “leet code : Two sum Problem solution – Java || CPP || JavaScript || Python”

  1. bro you solved it by class method and python code for this problem is simpler but i cant understand why we use class and all so please refer me article so that i can understand is use.
    Thankyou.

  2. Itís nearly impossible to find well-informed people for this subject, however, you seem like you know what youíre talking about! Thanks

  3. Wһat’s up to every one, it’s truly a good for me to рay a
    quick visit this site, it contains preci᧐us Information.

  4. Your python hash table solution is not n… it’s n^2.
    Checking if an element is in a dict is amortized worst case O(n). You perform this check n times. Therefore n^2…
    https://wiki.python.org/moin/TimeComplexity

    Mine as well just brute force it

Leave a Comment