Problem Intution Cheatsheet

Two Pointer

1. Container With Most Water - This is a two pointer problem. put the pointers at extreme ends, calculate the current area (min(a[l], a[r]) * (r -l)). and move the pointer whose height is less.

Binary Search

1. Search Element in Rotated Sorted Array - At some index the array is rotated. The intuition is to check which half of the array [a[l] , a[mid]] or [a[mid], a[r]] and then check which half the target will lie by a[l] <= target < a[mid] or a[mid] < target <= a[r]

2. Search Element in Rotated Sorted Array II - Same as above one, just now it will have duplicates. to handle that condition or say to handle the edge case when the mid ele, left ele and right ele are same then what? Simply until a[l] == a[mid] == a[r], increment and decrement indexes and continue. This would fix that issue.

Reference

#interview #dsa