Two sum problem solution in easy way [Day-03]
Tags: dsa, datastructures, leetcode, twosum
Published: 2024-05-09 09:24:26

Today is day 3 for our dsa series. Today we discussed about two sum problem which is very important to understand the use of hashmap and how to optimes the time complexity of solution.

**Problem**
you give an array num of length n and a target value k. you find out all the no of pair which sum is equal to k.

**Input**  
num = [1,2,3,-1,4] , n = 5 , k = 5
**Output**
4

**Expiation **
1 + 2 + 3 + (-1) = 5
2 + 3 = 5
1 + 4 = 5
2 + (-1) + 4 = 5

**Brute Approch**
we point the two pointer i , j at index 0 of array. and move in complete in array and find out pair which sum of (num[i] + num[j) is equal to target value k if yes then increase the counter;

**Code**
```
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      System.out.println("Enter the size of an array");
      
      Scanner sc = new Scanner(System.in) ;
      
      int n = sc.nextInt();
      
      int a[] = new int[n] ;
      
      
      // 1,2,3,-1,4 
      
      
      // take the input from user for array's element
      for(int i = 0; i < n; i++) a[i] = sc.nextInt() ;
      
      System.out.println("Enter the value of k");
      int k = sc.nextInt() ;
      
      System.out.println("total no of pair is : " + totalPair(a , n , k));
      
  }
  
  
  public static int totalPair(int a[] , int n , int k) {
    int counter = 0;
    
    for(int i = 0; i < n ; i++) {
      for(int j = 0; j < n; j++) {
        if(a[i] + a[j] == k) counter++;
      }
    }
    
    return counter ;
  } 
  
}


```
Time complexity of above algorithm is O(N*N) or O(N^2) because we travel every time in loop for every iteration.


**If we optimes the above algorithm so we can use hashmap data structure which store the value and its frequency ** 

**Approch**

When we move in array then ele = a[i] we find out the a element which have value is (target - ele) in hashmap if yes then increase the counter ;


**Code**
```

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array");
        int n = sc.nextInt();

        int[] arr = new int[n];
        System.out.println("Enter the elements of the array");
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println("Enter the value of k");
        int k = sc.nextInt();

        System.out.println("Total number of pairs is: " + totalPair(arr, k));
    }

    public static int totalPair(int[] arr, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;

        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int num : arr) {
            int complement = k - num;
            if (map.containsKey(complement)) {
                count++;
                
            }
        }

        return count ;
    }
}

```

Time complexity is O(n) and space Complexity is also O(n) because we use extra space.

if you any doubt related to this article please comment us.