2 Pointers

Question 1

What is 2 pointer technique

Answer 1

1. The main idea is to have a left and a right pointer both starting at some indexes of the array
   They don’t always have to be start and beginning of the array
2. Increment the left pointer and decrement the right pointer based on constraint until the left and right pointer meet

Question 2

Check if string is a palindrome with removing special characters and spaces

Answer 2

1 a palindrome is one which is same reads same in forward and backward direction
2 start l and r pointer at 0 and len-1
3 run while loop on left and increment if left is has alpha by c.isalpha
4 repeat the same for right pointer and decrement
5 compare left and right if they are not same return false
6 return true in the end

Question 3

Two sum (using 2 pointer)

Answer 3

1 sort the array
2 start from left and right 0 to len -1
3 if we now add a left and right value and see that target is greater or less then the value
4 if less then move the left pointer
5 if more then move the right pointer
6 return indices left and right

Question 4

3 sum using 2 pointer you need to return all triplets in an array which adds up to b 0

Answer 4

1 3 sum is n2 problem
2 iterate the array get the 1st value and subtract from 0
3 have a nested loop left with index I+1 and end with len - 1
4. Now use the same concept of two pointer technique to see if a matching nagative value is found and append to result
5 here catch is that you don’t want to get duplicate pairs that we will only get if same array in first iteration is checked again so check that condition first and continue if the value is same as previous iteration
6 the similar needs to be followed after. First match if left and right index is same as previous iteration we will see duplicate
7 another way to get rid of duplicate is to have a tuppled set and return by converting it

Question 5

Container with most water

Answer 5

1 this problem becomes challenging because it is difficult to think about the condition to move left or right pointer
2 but when we look at the area which is min( h[l],h[r]) *r-l the r-l part will only decrease to maximise the area we need to increase or maximise left or right value
3 so if height of left is < height of right move the left pointer else move the right pointer

Question 6

Trapping rain water
You are given an array of non negative heights which represent an elevation map return the maximum area of water that can be trapped in the bars

Answer 6

1 again trick is to figure out constraint of moving left and right pointer technique
2 if you see clearly unless there is a left height less then previous left pointer the water will spill over
3 similar for right pointer
4 if you look at the trap area from left it will be left max - the height of left
5 same for right pointer
6 so if left max is less then right max increment the left pointer and calculate max area every iteration
7 repeat same for right pointer
8 we will determine min(l,r) -h[i]
9 remember the water can only be trapped at any index if there is a max left and max right pointer