Data Structures and Algorithms(DSA) Concept — Hashmaps — Part 2.

Topic : DSA Interview questions based on Hashmaps and Hashsets.

Q 1. Given an array A of size N . Check if there exists a pair ( i , j ) , such that A[ i ] + A[ j ] == k and i != j.

Eg : 

A = [ 3, 2, 6, 8, 4 ]

k= 10

for i = 1 and j= 3
A[1] + A[3] = 10. // True

for i = 2 and j= 4
A[2] + A[4] = 10. // True


Approach 1 : Iterate through the array and check if i,j pair is equal to k

In this approach the TC : O(N^2)

Approach 2 :

We have to find pairs such that 

A[i] + A[j] = k

it can also be writen as A[i]= k-A[j]

in this approach we will use Hashset to keep track of elements.

We will iterate through the array and check is k - A[i] is available in
the hashset .
  
if it is availabe we return true , else we add A[i] to the hashset .

DRY RUN :

lets see this approach with an example :

A = [ 3, 2, 6, 8, 4 ]   and k = 10

first we intialise an hashset which is empty .

set=()

lets iterate though the array
 i = 0 
        check if k-A[0] = 7 exists in the set .
        
        since it does not exist A[0] = 3 is added to the set .

set = ( 3 ) 

  i = 1 
       if k-A[1] = 8 is in set.
    
       else add A[i] in set

set = ( 3, 2 )
 
  i = 2

      if k-A[i] = 4 in set.

      else add A[i] in set.

 set = (3, 2, 6)

  i = 3
      
      if k-A[i] =2 is in set 

      return true;

TC : O(N)

Lets see this in code .
    

public boolean hasPair(int [] A, int k){

Hashset <Integer> set = new Hashset<>();

for (int i = 0 ; i < A.length ; i++){
     
    if (set.contains(k-A[i])){
        
        return true;
        
      }
    else{

      set.add(A[i]);
    
    } 
    
  }

  return false;



}

Q 2. Given an array A of size N . Count the number of pairs ( i , j ) such that

A[ i] + A[j] == k and i != j.

Approach :
 
We can use the same approach as the question above 
but instead of the hashset we will be using a hashmap.

public int CountPair(int[] A, int k){
  int N = A.length;
  int count= 0;

  Hashmap<Integer,Integer> map = new Hashmap<>();
  
  for( int i=0;i<N;i++){
      
      if (map.contains(k-A[i])==true){
          count=count + map.get(k-A[i]);
      }
      if( map.contains(A[i])==true){
        int val= map.get(A[i]);
        map.put(A[i] ,val++);
      }
      else{
        
          map.put(A[i],1);
      
      }
  }
  return count;
} 

TC : O ( N )

Q 3 . Given an array A of length N. Check if there exists a subarray with sum = k.

Eg : 

A = [ 2, 3, 9, -4, 1, 5, 6, 2, 5 ]

K = 11  is true for [ 5, 6 ] , [ 2, 3, 9, -4, 1] , [ 9, -4 , 1, 5]

k = 50 

Approach 1 : 

Using prefix sum .

Step 1 : Build prefix sum array.

Step 2 : Iterate over all the subarrays (start , end pairs )and get 
         the sum using Prefix sum.

         Sum [start, end] = PS[end] - PS[start-1]

TC : O ( N^2 )
SC : O ( N )

Approach 2 :

Using prefix sum and hashset .

Step 1 : Build a prefix sum of the array.
         and create a hashset.

Step 2 : We have to find is PS[end]-PS[start-1] =K 

         we can approach by iterating throught the prefix sum and 
         check is PS[i]-k exists in the hashset and add PS[i] to the 
         hashset.


Lets see this in code for better understanding.

Public boolean CheckSumSubarray(int[] A, int k){

int PS=0;

Hashset<Integer> set = new Hashset<>();

set.add(0);
// 0 is added to the set because the subarray from index 0 if equal to k will 
//give 0 when we check for PS[i]-k
for( int i =0 ;i<A.length;i++){

  PS = PS +A[i];
  if(set.contains(PS-k)){
      return true;
    }
  else{
    set.add(PS);
  }


  }

return false;


}

Hope this was helpful , please do like and follow.