WittCode💻

Optimizing Code with the Two Pointer Technique

By

Learn how to optimize code using the two pointer technique, including reducing time complexity from O(n^2) to O(n). This is a common technique used in coding interviews.

Table of Contents 📖

Optimizing Code with the Two Pointer Technique

Optimizing code is a cornerstone of software development, especially in coding interviews. One way to reduce the complexity of code is to use the two pointer technique. The two pointer technique is a method to solve problems involving iterating through a linear data structure (like arrays) using two distinct pointers. These pointers typically start at the beginning and end of the array and move toward each other (but can start anywhere in the array).

INFO: The two pointer technique often reduces the time complexity from O(n^2) to O(n) by avoiding nested loops. The Big O notation mentioned here refers to time complexity because it describes how the number of operations grows as the input size increases.

When to Use It

  • Problems involving sorted arrays.
  • Finding pairs or subarrays that match a certain criteria.

To demonstrate, lets use the two pointer technique and the brute force solution to find two numbers in a sorted array that sum to a target value. This problem is typically called Two Sum.

Brute Force Code Approach

This approach uses a nested loop where the outer loop iterates over the elements and the inner loop processes the remaining elements. This leads to a time complexity of O(n^2).

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [nums[i], nums[j]];
      }
    }
  }
  return null;
}

// Input and Output Example
const nums = [1, 2, 3, 4, 5];
const target = 6;
console.log(twoSumBruteForce(nums, target));
// Output: [1, 5]

Optimized Solution

In the optimized solution we reduce the time complexity from O(n^2) to O(n) by using the two pointer technique.

  • Initialize the two pointers: one starts at the left and the other starts at the right of the array.
  • Depending on the problem, move the left pointer, right pointer, or both.
  • Stop when the pointers meet or cross each other.
function twoSumOptimized(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];

    if (sum === target) {
      return [nums[left], nums[right]];
    } else if (sum < target) {
      left++; // Increase the sum by moving the left pointer to the right.
    } else {
      right--; // Decrease the sum by moving the right pointer to the left.
    }
  }

  return null;
}

// Input and Output Example
const numsSorted = [1, 2, 3, 4, 5];
const targetValue = 6;
console.log(twoSumOptimized(numsSorted, targetValue));
// Output: [1, 5]

WARNING: The two pointer technique would not work if the array in this problem was not sorted. This is because we would not know which pointer should move.