Two Pointer Technique

Two-pointer is a common technique used to solve array problems. This method removes many redundant potential solutions thus giving efficient output compared to the brute-force solution. To demonstrate the two-pointer technique let’s try to solve the below question on leetcode i.e Container with most water and Trapping rainwater using two pointer technique.

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Constraints: Walls between given two walls doesnt restrict container formation 

Examples 
Input: height = [1,2,1] Output: 2
Input: height = [4,3,2,1,4] Output: 16

You can run above example here.

Solution : Javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    
    let maxArea = 0;
    let leftPointer = 0;
    let rightPointer = height.length -1;
    // area = min[p1,p2]*(p2-p1)
    
    while(leftPointer<rightPointer){
         if(height[leftPointer] <= height[rightPointer]){
            maxArea = Math.max(Math.min(height[leftPointer], height[rightPointer])*(rightPointer-leftPointer), maxArea)
            leftPointer++;
            }
         else{
              maxArea = Math.max(Math.min(height[leftPointer], height[rightPointer])*(rightPointer-leftPointer), maxArea)
             rightPointer--;
         }
          }
    return maxArea;
};

Time Complexity : Linear Time O(n)

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Input: height = [4,2,0,3,2,5]
Output: 9

You can run the code here.

Solution : Javascipt

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    
   let totalWater = 0;
    // area = min[p1,p2]*(p2-p1)
    let left = 0;
    let right = height.length -1;
    let maxLeft =0;
    let maxRight = 0;

    while(left<right){
         if(height[left] <= height[right]){
             if(height[left]>= maxLeft){
                maxLeft = height[left];
                }
             else{
                 totalWater += maxLeft - height[left]
             }
            left++;
            }
         else{
             if(height[right]>= maxRight){
                 maxRight = height[right]
             }
             else{
                 totalWater += maxRight - height[right]

             }
             right--;
         }
          }
    
    return totalWater;
    
};

Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a##c", t = "#a#c"
Output: true
Explanation: Both s and t become "c".

Example 4:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

var backspaceCompare = function (s, t) {
    let p1 = s.length - 1;
    let p2 = t.length - 1;

    while(p1 >= 0 || p2 >= 0){
      if(s[p1] === "#" || t[p2] === "#"){

       if(s[p1]==="#"){
        let backtrack = 2;
        while(backtrack > 0) {
          p1--;
          backtrack--;
          if(s[p1]==="#"){
            backtrack += 2;
          }
        }
       }
       if(t[p2]==="#"){
        let backtrack = 2;
        while(backtrack > 0) {
          p2--;
          backtrack--;
          if(t[p2]==="#"){
            backtrack += 2;
          }
        }
       }
      }
      else{
        if(s[p1] != t[p2]){
          return false;
        }
        p1--;
        p2--;
      }

    }
   return true;
};