Two sum problem solution in easy way [Day-03]

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.