Open in app

Sign in

Write

Sign in

Two pointers coding pattern

Dilip Kumar
14 min readSep 21, 2024

--

If input is in sorted order then we can apply two pointers left and right to solve few problems. Let’s try few.

1. Two Sum

https://leetcode.com/problems/two-sum/description/

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Approach # Use hashmap

We can use hashmap to quick lookup target-num to find if second number exist or not. Follownig is code for reference.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            map[nums[i]] = i;
        }
        for (int i = 0; i < n; i++) {
            int remaining = target - nums[i];
            if (map.count(remaining) > 0 && map[remaining] != i) {
                return {i, map[remaining]};
            }
        }
        return {};
    }
};

167. Two Sum II — Input Array Is Sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Approach

  1. Take two pointers left and right
  2. If sum of both i.e. nums[left] + nums[right]=target then return answer.
  3. If nums[left] + nums[right] < target then it means left can’t be contribute to build the closest target , we need to try next left+1
  4. Similarly, nums[left] + nums[right] > target then it means we can let got current right

Following is code for reference.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int left = 0, right = n - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left+1, right+1}; // match 1 base index
            } else if (sum < target) {
                left++; // need to add bigger number to get closer to target
            } else {
                right--; // need to drop bigger number to get closer to target
            }
        }
        return {};
    }
};

15. 3Sum

https://leetcode.com/problems/3sum/description/

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Approach

  1. a+b+c=0 i.e. a+b=c it means if we fix c then problem is reduced to two sum problem.
  2. Since order doesn’t matter therefore we can first sort the array then apply two sum problem.
  3. Every time we scan new num, skip older same number already processed.

Following is code for reference.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = -nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                if (left > i + 1 && nums[left] == nums[left - 1]) {
                    left++;
                    continue;
                }
                if (right < n - 1 && nums[right] == nums[right + 1]) {
                    right--;
                    continue;
                }
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
};

18. 4Sum

https://leetcode.com/problems/4sum/

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Approach

  1. We can design a generic k level target sum problem.
  2. First we will sort the given input nums
  3. We will apply decrease and conquer approach.
  4. I.e. first we will apply outer loop to find out kth, k-1th….till 3rd.
  5. Then at the end will apply two sum

Following is code for reference.

class Solution {
private:
    // Find a & b for given target on sorted array
    vector<vector<int>> twoSum(vector<int>& nums, long target, int start) {
        vector<vector<int>> ans;
        int n = nums.size();
        int left = start;
        int right = n - 1;
        while (left < right) {
            if (left > start && nums[left] == nums[left - 1]) {
                left++;
                continue;
            }
            if (right < n - 1 && nums[right] == nums[right + 1]) {
                right--;
                continue;
            }
            long sum = nums[left] + nums[right];
            if (sum == target) {
                ans.push_back({nums[left], nums[right]});
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
    vector<vector<int>> kSum(vector<int>& nums, long target, int k, int start) {
        // Base case for two level sum
        if (k == 2) {
            return twoSum(nums, target, start);
        }
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = start; i < n; i++) {
            // skip duplicate
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            auto local = kSum(nums, target - nums[i], k - 1, i + 1);
            // As a manager, take output from worker and solve it
            for (auto tuple : local) {
                tuple.push_back(nums[i]);
                ans.push_back(tuple);
            }
        }
        return ans;
    }

public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end()); // Sort array
        return kSum(nums, target, 4, 0);
    }
};

1099. Two Sum Less Than K

https://leetcode.com/problems/two-sum-less-than-k/description/

Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.

Example 1:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

Approach #1: Use hashmap (not possible)

Since our sum can be any value smaller than the target, we cannot use a hashmap.

Approach #2: Use two pointers approach

To apply the two pointers approach, we will first need to sort it. Following is code for reference.

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int left = 0, right = n - 1;
        int ans = INT_MIN;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum >= k) {
                // move to left
                right--;
            } else {
                // move to right
                left++;
                // This is ans zone, capture it.
                ans = max(ans, sum);
            }
        }
        return ans == INT_MIN ? -1 : ans;
    }
};

Q. But hold on, doesn’t sorting break the problem statement of i<j ?

Ans. No. Let’s take example of [34,23,24] with k=60 . Here answer is 34+24=58 with i=0 and j=2 . If we sort then we get [23,24,34] with the original index mapping of [1,2,0] but above code will give answer with {24+34}i.e. compare to original index as i=2 and j=0 so we can say that hey i<j is not satisfied so answer is wrong. But the important concept is, addition is Commutative i.e. a+b==b+a therefore when we got answer for i=2 and j=0 therefore to satisfy i<j we can simply swap the orer i.e. i=0 and j=2 .

It means, i<j condition is irrelevant and distraction here due to the commutative properties of addition.

If problem is changed to find out the subtraction of i & j with i<j then we can’t apply sorting.

2 Sum Smaller

Given a nums array, find the number of index pairs i, j with 0≤i<j<n that satisfy the condition nums[i]+nums[j]<target.

Approach 1 # Use hashmap (not possible)

Approach #2 Use two pointers

First sort the nums array. For example, nums=[3,5,2,8,1] becomes [1,2,3,5,8].

Let us look at an example nums=[1,2,3,5,8], and target=7.

[1, 2, 3, 5, 8]
 ↑           ↑
left       right

Let us initialize two indices, left and right pointing to the first and last element respectively.

When we look at the sum of first and last element, it is 1+8=9, which is ≥target. That tells us no index pair will ever contain the index right.

So the next logical step is to move the right pointer one step to its left.

[1, 2, 3, 5, 8]
 ↑        ↑
left    right

Now the pair sum is 1+5=6, which is less than target.

Q. How many pairs with one of the index=left that satisfy the condition?

You can tell by the difference between right and left which is 3, namely (1,2),(1,3), and (1,5). Therefore, we move left one step to its right.

Following is code for reference.

    int twoSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int left=0, right = n-1;
        int count =0;
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum >= target) {
               // move right
                right--;
            } else {
                count += right - left;
                left++;
            }
        }
        return count;
    }

259. 3Sum Smaller

https://leetcode.com/problems/3sum-smaller/

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Approach # Extend two sum smaller logic

We can use the two sum smaller logic to solve this problem as below.

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n-2; i++) {
            int c = nums[i];
            int rest = target - c;
            // Run two sum
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum < rest) {
                    // Ans zone
                    ans += (right - left);
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
};

2 Sum Closest

Given an integer array nums of length n and an integer target, find two integers in nums such that the sum is closest to target.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (-1 + 1 = 0).

Approach# Two pointer approach

  1. We first need to sort nums to apply two pointers approach
  2. Now use left and right as two pointers to explore a=nums[left] and b=nums[right]
  3. We have sum = a + b
  4. Let’s find the diff = abs(sum — target)
  5. Let’s keep the global distance=Inf
  6. If diff < distance then update the diff
  7. If sum < target then explore right
  8. Otherwise explore left
  9. Return target — diff as an answer

Following is code for reference.

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int diff = INT_MAX;
        int ans = 0;
        int left = 0, right = n - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            // zone to updat the diff
            if (abs(target - sum) < diff) {
                diff = abs(target - sum);
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
};

16. 3Sum Closest

https://leetcode.com/problems/3sum-closest/description

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Approach: Use two pointer approach

  1. We first need to sort nums to apply two pointers approach
  2. First iterate nums to explore c=nums[i]
  3. Now use left and right as two pointers to explore a=nums[left] and b=nums[right]
  4. We have sum = a + b + c
  5. Let’s find the diff = abs(sum — target)
  6. Let’s keep the global distance=Inf and ans variable
  7. If diff < distance then update the diff and ans
  8. If sum < target then explore right
  9. Otherwise explore left

Following is code for reference.

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int diff = INT_MAX;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int c = nums[i];
            int rest = target - c;
            // 2 sum closest
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                // zone to updat the diff
                if (abs(rest - sum) < diff) {
                    diff = abs(rest - sum);
                    ans = sum + c; // update ans
                }
                if (sum < rest) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
};

658. Find K Closest Elements

https://leetcode.com/problems/find-k-closest-elements/description

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

  • |a - x| < |b - x|, or
  • |a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Approach #1: Apply custom sorting

We can apply custom sorting followed by slicing the first k numbers. Following is code for reference.

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        auto compare = [x](int a, int b) {
            if ((abs(a - x) == abs(b - x) && a < b) ||
                abs(a - x) < abs(b - x)) {
                return true;
            }
            return false;
        };
        sort(arr.begin(), arr.end(), compare);
        vector<int> ans(k);
        copy(arr.begin(), arr.begin() + k, ans.begin());
        sort(ans.begin(), ans.end());
        return ans;
    }
};

Time complexity: O(nlogn)

Approach#2: Binary Search + Two pointers

  1. Use binary search to locate the x in the array.
  2. Logically, the second closest number to x must be directly beside the first number, either to the left or right.
  3. Then, the third closest number to x must be either to the left of the first number or to the right of the second number.
  4. This pattern continues, and is true because the input is sorted.
  5. Using two pointers, we can maintain a sliding window that will expand to contain the k closest elements to x
  6. We should expand our window by moving the pointers either left or right depending on which number is closer to x.

Following is code for reference.

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function (arr, k, x) {
    const n = arr.length;
    // Base case
    if (n === k) {
        return arr;
    }
    // Binary search to find the closest element to left
    let left = 0;
    let right = n - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] >= x) {
            // Move left
            right = mid - 1;
        } else {
            // move right
            left = mid + 1;
        }
    }
// Apply two pointers
    let start = left - 1;
    let end = left;
    while (end - start - 1 < k) {
        // Handle out of bound
        if (start === -1) {
            end++;
            continue;
        }
        if (end === n) {
            start--;
            continue;
        }
        // Expand the window towards the side with the closer number
        if (Math.abs(arr[start] - x) <= Math.abs(arr[end] - x)) {
            start--;
        } else {
            end++;
        }
    }
    // return the window
    return arr.slice(start + 1, end);
};

42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/description

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Approach #1 (TLE): Min of max bar on left and right scanning of each elevation

A elevation can trap the water as per below.

f(i) = min (
    max(0,...i-1), // max height seen in left
    max(i+1,....n-1) // max height seen on right
  ) - height[i]

Following is code for reference.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    const n = height.length;
    let ans = 0;
    for (let i = 1; i < n - 1; i++) {
        // find out max on left
        let leftMax = 0;
        for (let left = 0; left < i; left++) {
            leftMax = Math.max(leftMax, height[left]);
        }
        // Find out max on right
        let rightMax = 0;
        for (let right = i + 1; right < n; right++) {
            rightMax = Math.max(rightMax, height[right]);
        }
        const water = Math.min(leftMax, rightMax) - height[i];
        if (water > 0) {
            ans += water;
        }
    }
    return ans;
};

Approach #2: Precalculate the left and right max for each elevation

Instead of calculating left max and right max every time, we can pre-calculate and reuse it.

Following is code for reference.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    const n = height.length;
    let ans = 0;
    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);
    // Build left max
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i - 1])
    }
    // Build right max
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
    }
    for (let i = 1; i < n - 1; i++) {
        const water = Math.min(leftMax[i], rightMax[i]) - height[i];
        if (water > 0) {
            ans += water;
        }
    }
    return ans;
};

Approach#3: Use two pointers to update max left/right at runtime

Instead of pre-calculate, we can also use the two pointers to keep track of max seen in left and right so far. Following are key points.

  1. As long as right_max[i] > left_max[i], the water trapped depends upon the left max.
  2. Similarly when left_max[i] > right_max[i], the water trapped depends on right max.
  3. If there is a larger bar at one end (say right), we are assured that the water trapped would be depends on height of bar in current direction.
  4. As soon as we find that bar at the other end (right) is smaller, we start iterating in opposite direction.

Following is code for reference.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int ans = 0;
        int leftmax = 0, rightmax = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftmax = max(leftmax, height[left]);
                ans += (leftmax - height[left]);
                left++;
            } else {
                rightmax = max(rightmax, height[right]);
                ans += (rightmax - height[right]);
                right--;
            }
        }
        return ans;
    }
};

407. Trapping Rain Water II

https://leetcode.com/problems/trapping-rain-water-ii/description/

TBD

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Approach: Two pointers

Following is code for reference.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int ans = 0;
        while (left < right) {
            int l = height[left];
            int r = height[right];
            int h = min(l, r);
            ans = max(ans, h * (right - left));
            if (l < r) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
};

Happy coding :-)

Data Structure Algorithm

--

--

Dilip Kumar
Dilip Kumar

Written by Dilip Kumar

492 Followers
29 Following

With 18+ years of experience as a software engineer. Enjoy teaching, writing, leading team. Last 4+ years, working at Google as a backend Software Engineer.

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams