Discover the beauty of the algorithm-the collision of double pointers

Posted Jun 5, 20206 min read

Collision pointer.png

  • What is a collision pointer?

    • First acquaintance
    • Algorithm diagram
    • Collision process diagram
  • Array and collision pointer in JavaScript

    • How to define collision pointer in js?
    • Implement a minimalist collision pointer
  • Leetcode collision pointer solution problem

      1. Integer inversion(easy)
      1. Palindrome(easy)
      1. Remove elements(easy)
      1. Verify the palindrome string(easy)
      1. Two-number II-input ordered array(easy)
      1. Reverse binary bits(easy)
      1. Reverse string(easy)
      1. Reverse vowels in strings(easy)
      1. The container with the most water(medium)

What is a collision pointer?

First acquaintance

  • Collision pointer is one of the double pointer algorithm.
  • The collision pointer iterates the array from both ends to the middle. One pointer starts at the beginning and the other starts at the end.
  • The termination condition of the colliding pointer is that the two pointers meet.
  • Collision pointers are often used to sort arrays.

Algorithm diagram

image

Collision process diagram

  1. Two-number II-input ordered array(easy) collision process diagram.
    Blue pointer:head pointer Red pointer:tail pointer Termination condition:collision between head and tail pointer

Array and collision pointer in JavaScript

How to define collision pointer in js?

Naming

The head and tail pointers can be named:

  • i, j
  • head, tail
  • start, end
Initial value
  • Head pointer:0

  • Tail pointer:Array length minus one

    let arr = [1, 7, 5, 2];
    let head = 0;
    let tail = arr.length -1;

Implement a simple collision pointer

image

var arr = new Array(10).fill(0).map((num,i)=>num+i);
var i =0;
var j = arr.length-1;
while(i<j){
  i++;
  j--;
}
var collision = [i-1, j + 1]
var tip = `Array's head and tail had a collision between ${collision[0]} and ${collision[1]}`;
console.log(tip); //Array's head and tail had a collision between 4 and 5

leetcode collision pointer solution problem

    1. Integer inversion(easy)
    1. Palindrome(easy)
    1. Remove elements(easy)
    1. Verify the palindrome string(easy)
    1. Two-number II-input ordered array(easy)
    1. Reverse binary bits(easy)
    1. Reverse string(easy)
    1. Reverse vowels in strings(easy)
    1. The container with the most water(medium)

7. Integer inversion(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var reverse = function(x) {
  /**
   * Solution 2. Pointer collision method
   * Performance:96 ms 35.38%35.9 MB 77.35%
   */
  var sign = Math.sign(x);
  var arr = x.toString().split("");
  //
  if(sign === -1) {
    arr.shift();
  }
  //pointer collision starts
  var i = 0;
  var j = arr.length-1;
  while(i <j) {
    swap(arr, i, j);
    i++;
    j--;
  }
  function swap(arr, i, j) {
    var temp = arr[i];
    arr[i]= arr[j];
    arr[j]= temp;
  }
  //pointer collision ends
  var rX = parseInt(arr.join(""));
  var result = sign * rX;
  var min = -Math.pow(2, 31);
  var max = Math.pow(2, 31)-1;
  if(rX <min || rX> max) return 0;
  return result;
};

9. Palindrome(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var isPalindrome = function(x) {
  /**
   * Solution 3:Collision pointer method
   * Performance:244ms 45.5MB
   */
  var strArr = `${x}`.split("");
  var i = 0;
  var j = strArr.length-1;
  while(i <j) {
    if(strArr[i]!== strArr[j]) {
      return false;
    }
    i++;
    j--;
  }
  return true;
};

27. Remove elements(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var removeElement = function(nums, val) {
  /**
   * Solution 2:Collision with the pointer
   * Performance:64ms 33.9MB
   */
  var i = 0;
  var j = nums.length-1;
  while(i <= j) {
    if(nums[i]=== val) {
      nums.splice(i, 1);
      j--;
    } else if(nums[j]=== val) {
      nums.splice(j, 1);
      j--;
    } else {
      i++;
    }
  }
  return nums.length;
};

125. Verify the palindrome string(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var isPalindrome = function(s) {
  /**
   * Solution 1:Regular + collision pointer
   * Performance:76ms 89.76%37.5MB 70.83%
   */
  var parlinDrome = s.replace(/[^\w]/g, "").replace(/_/g, "").toLowerCase();
  var strArr = parlinDrome.split("");
  var i = 0;
  var j = strArr.length-1;
  while(i <j) {
    if(strArr[i]!== strArr[j]) {
      return false;
    }
    i++;
    j--;
  }
  return true;
};

167. Two-number II-input ordered array(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var twoSum = function(numbers, target) {
  /**
   * Solution 2:Collision with the pointer
   * Performance:68ms 71.18%35.2MB 76.60%
   * Time complexity:O(n^2)
   */
  var left = 0;
  var right = numbers.length-1;
  while(left <right) {
    if(numbers[left]+ numbers[right]=== target) {
      return [left + 1, right + 1];
    } else if(numbers[left]+ numbers[right]> target) {
      right--;
    } else {
      left++;
    }
  }
};

190. Reverse Binary Bits(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

/**
 * @param {number} n-a positive integer
 * @return {number}-a positive integer
 */
var reverseBits = function(n) {
  /**
   * Solution 1:Collision exchange position after turning array
   * Performance:76ms 35.8MB
   * Ideas:
   * Decimal to binary:toString(2)
   * 32-bit vacancy fill 0:padStart(32,0)
   * Reverse algorithm:Collision pointer method
   * Binary to decimal:parseInt(,2)
   */
  let arr = n.toString(2).padStart(32, 0).split("");
  let head = 0;
  let tail = arr.length-1;
  while(head <tail) {
    swap(arr, head, tail);
    head++;
    tail--;
  }
  function swap(arr, i, j) {
    let temp = arr[i];
    arr[i]= arr[j];
    arr[j]= temp;
  }
  let result = parseInt(arr.join(""), 2);
  return result;
};

344. Reverse string(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var reverseString = function(s) {
  /**
   * Solution 2:Collision with the pointer
   */
  var headIdx = 0;
  var tailIdx = s.length-1;
  while(headIdx <tailIdx) {
    swap(s, headIdx, tailIdx);
    headIdx++;
    tailIdx--;
  }
  function swap(arr, i, j) {
    var temp = arr[i];
    arr[i]= arr[j];
    arr[j]= temp;
  }
  return s;
};

345. Reverse vowels in strings(easy)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function(s) {
  /**
   * Solution 1:Collision with the pointer
   * Performance:108 ms 31.59%38.4 MB 66.67%
   */
  var univocalic = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"];
  var sArr = s.split("");
  var head = 0;
  var tail = sArr.length-1;
  while(head <tail) {
    if(univocalic.includes(sArr[head]) && univocalic.includes(sArr[tail])) {
      swap(sArr, head, tail);
      head++;
      tail--;
    } else if(!univocalic.includes(sArr[head])) {
      head++;
    } else if(!univocalic.includes(sArr[tail])) {
      tail--;
    }
  }
  function swap(arr, i, j) {
    var temp = arr[i];
    arr[i]= arr[j];
    arr[j]= temp;
  }
  return sArr.join("");
};

11. The container with the most water(medium)

Title: https://leetcode-cn.com/probl...
Solution: https://github.com/FrankKai/l...

var maxArea = function(height) {
  /**
   * Solution 1:Collision pointer method
   * Performance:64ms 35.6MB
   * */
  var head = 0;
  var tail = height.length-1;
  var maxCapacity = 0;
  while(head <tail) {
      maxCapacity = Math.max(Math.min(height[head], height[tail]) *(tail-head), maxCapacity)
      if(height[head]<height[tail]) {
          head++
      } else {
          tail--;
      }
  }
  return maxCapacity;
};

Looking forward to communicating with you and making progress together, welcome everyone to join the technical discussion group I created that is closely related to front-end development

Strive to become an excellent front-end engineer!