Two Sum - LeetCode (DSA-01)

Hey, this is a series of blogs about me learning and solving all the major DSA (Data Structures and Algorithms) problems. With no BS* .

Problem --> Two Sum [ addition of two integers and checking that if the sum of two integers is similar to our target ].

Sounds pretty easy I know and it is not that taxing on our minds, believe me.

There are multiple ways to solve any problem and this one also has multiple ways to get the desired result.

Discription :

Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the 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.

Example 1. 
Input: nums = [1,9,2,8,3,7,4], target = 12
Output: [1,4]
Explanation: Because nums[1] + nums[4] == 12, we return [1,4].

Example 2.
Input: nums = [3,5,7,9,1], target = 4
Output: [0,4]
Explanation: Because nums[1] + nums[4] == 4, we return [0,4].

Getting the gist from this you must be clear with the requirement of what we want to achieve.

Solution 1. Brute Force

Let's use FORCE to get the solution, from example-1 we have 7 integers to check our solution with our target. Adding every integer in that array, in our case, it's 7.

public static int[] twoSum(int[] nums, int targetSum) {
    for (int n1 = 0; n1 < nums.length; n1++) {
      for (int n2 = n1 + 1; n2 < nums.length; n2++) {
        if (nums[n2] == target - nums[n1]) {
          return new int[]{n1, n2};
        }
      }
    }
}

We have a small array of 7 what if the size of an array is 47 or even greater than that. This method is not efficient for us. But works.

Time Complexity --> let's there is n number of elements in the array. So this algorithm will take n times n so the worst time complexity is O(n^2).

Space Complexity --> we're not creating any variable so the space complexity is O(1)

Solution 2. Hash Map

Here let's use Hash Map, for this we need the index of each element - using again example-1. with values and index.

In beginning, the hashMap will be empty. The general thumb rule is: by subtracting the target from the element and checking if that element exists in our hashmap if not store the element with its index and proceed with another element. for e.g

target = 12 
nums = [1,9,2,8,3,7,4]
target - element  
12 - 1 = 11 « does 11 exist in our hashmap or not if not (then continue) if yes (Hashmap [value,Index] ) in this case it will be [1,0]
12 - 9 = 3 « does 3 exist in our hashmap or not if not (then continue) if yes (add to Hashmap [value,Index] ) in this case it will be [9,1]
....
....
12-3 = 9 « does 9 exist in our hashmap **YES**  then return the saved index. 

RESULT --> [ 1 , 4 ]

Let's write the algorithm

class Solution {
    public static int[] twoSum(int[] nums, int targetSum) {
   HashMap<Integer, Integer> hm = new HashMap<>();
     for(int i=0 ; i< nums.length; i++){
         if( hm.containsKey(nums[i])){
             return new int[]{ hm.get(nums[i]), i };
         }
         hm.put(targetSum - nums[i] , i);
     }
     return new int [0];

    }
}

Time complexity --> In this algorithm, we're iterating over an array once and we know the given array is sorted if not, we need to sort [ Arrays.sort(array); ] So, O(n) is the time complexity where n is the number of elements in our array.

Space complexity --> here we're creating a hashmap so it will take some space. So, O(n) is the space complexity.

It is a pretty simple problem to solve. We just need to think differently to get to the solution which just does not pass but passes effectively.*