Two Pointers

Question 1

Pair with given difference.

Given a 1D unsorted array A and an integer b, find if there exists a pair with difference b

Answer 1

Firstly check for the case when b is 0. Simply maintain a map of frequency of occurrences of elements and if it gets greater than 1 then there exists 2 or more elements of same value and hence of difference 0. So return 1

Now for other values, insert them in a map. Now traverse again through the array and now search for arr[i] +b in the map. If it exists return 1.
Else return 0.

Question 2

3 sum

Find 3 interferes in s such that their sum is closest to the given no.

Answer 2

Firstly sort the array so that we can perform binary search.
Now starting from i=0, fixing the first element at arr[i], we perform bs on the other two.
Low =i+1, high is n
While(lowb high–
Else low++

Question 3

Triplets with sum zero

Find all unique triplets in the given array with sum 0

Answer 3

Since we want unique triplets, we maintain a set of vectors, so that the triplets won’t repeat.
Starting from i=0 and fixing the first element at arr[i], we again perform binary search for the other two.
Low=i+1 high = n-1
While (low0 high–
Else low++

Question 4

Counting triangles

Given a array of integers find the number of possible triangles which can be formed

Answer 4

a+b>c
b+c>a 
c+a> b
Now if a<b>c
So again we sort the array. Traversing from right we fix the last element and perform binary search on the other two.
a=0 and b=c-1 
While (a<=b) 
If( condition satisfied)
 Ans+= (b-a) because for every value of a in between a and b also the condition will be satisfied.
b--
Else a++</b>

Question 5

Intersection of 2 sorted arrays
1 2 3 3 4 5
3 3 5
Op 3 3 5 
1 2 3 4 5
3 3 5 
Op 3 5

Answer 5

Firstly traverse through the smaller array and insert the elements in a map.
Now traverse through the second array and if the element is already present in the map, then insert it in the answer and aslo decrease the count in the map. Important. So that we get the exact number of repetitions in the intersection.

Question 6

Maximum ones after modification

Given a binary array a we need to find the length of the longest subsegment of 1s possible by changing almost b

Answer 6

How is this problem different from flip array where we used Kadanes algorithm to find maximum sum

int i=0 j=0
While ib
{( If arr[j]==0)
   Flip--
 J++}
Ans=max(ans, i-j+1)
I++

Return ans

Question 7

Counting subarrays

Given an array a of n integers, find the number of subarrays in a having sum less than b

Answer 7

I=0, j=0 ans=0
While (currsum>b)
 {  Currsum-= arr[j]
   J++}
Ans+= i-j +1
No. If all possible new subarrays in this new window = length. Since sum can be less than b as well.
I++

Return ans

Question 8

Subarrays with distinct integers
Given an array a of positive integers, call a subarray good if the number of distinct elements in that subarray is exactly b. Return the number of good subarrays in a.

Answer 8

Almost b distinct no.
I,j =0
While (ib)
   { It= m.find a(j)
    It. Second--
    If( it. Second)==0 
      M.erase(a(j))
    J++}
  Ans+= i-j+1
I++

Question 9

Container with most water

Given an array of integers find the container with most water

Answer 9

Start=0 end= n-1
Maxarea=0
While( start

Question 10

Remove duplicates from sorted array

Answer 10

While (i