Two Pointers

Reverse a String

The simplest example of using two pointers to solve a problem is often found in the task of reversing an array or string. Here’s how you can use two pointers to achieve this:

Description: Given an array or a string, reverse its elements.

Solution:

Initialize two pointers: one at the beginning of the array and the other at the end.
Swap the elements at the two pointers.
Move the pointers towards each other: increment the first pointer and decrement the second.
Repeat steps 2 and 3 until the pointers meet or cross each other.

Here’s how you can implement this logic in Java, C++, and Python:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void reverse(int[] arr) {
  int left = 0;
  int right = arr.length - 1;
  while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
}

C++:

1
2
3
4
5
6
7
8
9
void reverse(vector<int>& arr) {
  int left = 0;
  int right = arr.size() - 1;
  while (left < right) {
    swap(arr[left], arr[right]);
    left++;
    right--;
  }
}

Python:

1
2
3
4
5
6
7
def reverse(arr):
  left = 0
  right = len(arr) - 1
  while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1

Using two pointers, you can reverse the array in-place with O(n) time complexity and O(1) space complexity, where n is the length of the array.

Target Sum

A more complicated problem where two pointers can be applied is finding a pair of numbers in a sorted array that sum to a given target value.

Description: Given a sorted array of integers, find two numbers in the array that sum up to a specific target number.

Solution:

Initialize two pointers: one at the beginning of the array (left) and the other at the end (right).
Calculate the sum of the elements at the left and right pointers.
If the sum equals the target, return the indices (or values).
If the sum is less than the target, increment the left pointer to move towards higher values.
If the sum is greater than the target, decrement the right pointer to move towards lower values.
Repeat steps 2 to 5 until the pointers meet or cross each other.

Here’s how you can implement this logic in Java, C++, and Python:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int[] twoSum(int[] numbers, int target) {
  int left = 0, right = numbers.length - 1;
  while (left < right) {
    int sum = numbers[left] + numbers[right];
    if (sum == target) return new int[]{left + 1, right + 1};
    if (sum < target) left++;
    else right--;
  }
  return new int[]{-1, -1}; // Return an error value if not found
}

C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
vector<int> twoSum(vector<int>& numbers, int target) {
  int left = 0, right = numbers.size() - 1;
  while (left < right) {
    int sum = numbers[left] + numbers[right];
    if (sum == target) return {left + 1, right + 1};
    if (sum < target) left++;
    else right--;
  }
  return {-1, -1}; // Return an error value if not found
}

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def twoSum(numbers, target):
  left, right = 0, len(numbers) - 1
  while left < right:
    sum = numbers[left] + numbers[right]
    if sum == target:
      return [left + 1, right + 1]
    if sum < target:
      left += 1
    else:
      right -= 1
  return [-1, -1] # Return an error value if not found

This problem is more complex than simply reversing an array, as it requires careful handling of the pointers based on the sum and target. The time complexity is still O(n), where n is the length of the array, and the space complexity remains O(1).

Trapping Rain Water

A tricky problem where two pointers can be used, but it might not be immediately obvious, is the “Trapping Rain Water” problem.

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

Solution:

Initialize two pointers, left and right, and two variables to keep track of the maximum height from both sides, left_max and right_max.
Move the pointers towards each other, updating left_max and right_max as needed.
The trapped water at any position depends on the minimum of left_max and right_max. Add this amount to the total, and then move the pointer inward from the side with the lower height.
Repeat until the pointers meet.

Here’s an example of how you can implement this logic:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int left_max = 0, right_max = 0;
    int trapped = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > left_max) left_max = height[left];
            else trapped += left_max - height[left];
            left++;
        } else {
            if (height[right] > right_max) right_max = height[right];
            else trapped += right_max - height[right];
            right--;
        }
    }

    return trapped;
}

C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int left_max = 0, right_max = 0;
    int trapped = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > left_max) left_max = height[left];
            else trapped += left_max - height[left];
            left++;
        } else {
            if (height[right] > right_max) right_max = height[right];
            else trapped += right_max - height[right];
            right--;
        }
    }

    return trapped;
}

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    trapped = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] > left_max:
                left_max = height[left]
            else:
                trapped += left_max - height[left]
            left += 1
        else:
            if height[right] > right_max:
                right_max = height[right]
            else:
                trapped += right_max - height[right]
            right -= 1

    return trapped

This problem might not initially seem solvable using two pointers because it’s not about searching, sorting, or manipulating the array in an obvious way. However, by recognizing the relationship between the heights and trapped water, you can create an elegant two-pointer solution with O(n) time complexity and O(1) space complexity.

Exhaustive List

Trapping Rain Water
3Sum
Container With Most Water
Next Permutation
Merge Sorted Array
Palindrome Linked List
Remove Duplicates from Sorted Array
Rotate Array
Boats to Save People
Move Zeroes
Meeting Rooms II
String Compression
Merge Strings Alternately
Number of Subsequences That Satisfy the Given Sum Condition
4Sum
Middle of the Linked List
Happy Number
Find the Duplicate Number
Reverse String
Valid Palindrome
Sort Colors
Intersection of Two Arrays
Reorder List
Find the Index of the First Occurrence in a String
Permutation in String
Find Median from Data Stream
One Edit Distance
Valid Palindrome II
Squares of a Sorted Array
Partition Array Into Two Arrays to Minimize Sum Difference
Remove Element
Find K Closest Elements
3Sum Closest
Linked List Cycle II
Remove Nth Node From End of List
Linked List Cycle
Dot Product of Two Sparse Vectors
Sort List
Swapping Nodes in a Linked List
Successful Pairs of Spells and Potions
Heaters
Reverse Words in a String
Minimum Number of Moves to Make Palindrome
Rotate List
Find the Celebrity
Valid Triangle Number
Candy Crush
Reverse Only Letters
Sum of Square Numbers
Longest Mountain in Array
Find the Maximum Number of Marked Indices
Count Binary Substrings
Intersection of Two Arrays II
Next Greater Element III
Intersection of Two Linked Lists
Partition Labels
Total Cost to Hire K Workers
Maximize Greatness of an Array
Two Sum II - Input Array Is Sorted
Is Subsequence
Find K-th Smallest Pair Distance
Reverse Words in a String III
K-diff Pairs in an Array
Reverse String II
Rotating the Box
Divide Intervals Into Minimum Number of Groups
Reverse Vowels of a String
Swap Adjacent in LR String
Minimum Number of Swaps to Make the String Balanced
Moving Stones Until Consecutive II
Next Palindrome Using Same Digits
Product of Two Run-Length Encoded Arrays
Maximum Twin Sum of a Linked List
Remove Duplicates from Sorted List II
Interval List Intersections
Remove Duplicates from Sorted Array II
Advantage Shuffle
Ways to Split Array Into Three Subarrays
Maximum Total Beauty of the Gardens
Rearrange Array Elements by Sign
Compare Version Numbers
Find the Distance Value Between Two Arrays
Number of Arithmetic Triplets
Count the Number of Fair Pairs
Move Pieces to Obtain a String
Backspace String Compare
Shortest Subarray to be Removed to Make Array Sorted
The Latest Time to Catch a Bus
Longest Uncommon Subsequence II
Get the Maximum Score
Most Profit Assigning Work
Pancake Sorting
Number of Subarrays with Bounded Maximum
Minimum Common Value
Flatten 2D Vector
Sort Transformed Array
Number of Ways Where Square of Number Is Equal to Product of Two Numbers
Shortest Unsorted Continuous Subarray
Split Two Strings to Make Palindrome
Check If N and Its Double Exist
Find First Palindromic String in the Array
Flipping an Image
Magical String
The k Strongest Values in an Array
Longest String Chain
Minimum Adjacent Swaps to Reach the Kth Smallest Number
Sort Array By Parity
Assign Cookies
Expressive Words
Longest Word in Dictionary through Deleting
Shortest Word Distance II
Subsequence With the Minimum Score
Shortest Way to Form String
Max Number of K-Sum Pairs
Sort Linked List Already Sorted Using Absolute Values
Maximum Enemy Forts That Can Be Captured
Minimize Maximum Pair Sum in Array
Valid Word Abbreviation
Maximum Score of a Good Subarray
Remove Palindromic Subsequences
3Sum With Multiplicity
Meeting Scheduler
Two Sum Less Than K
Lexicographically Smallest Palindrome
Strictly Palindromic Number
Delete the Middle Node of a Linked List
Camelcase Matching
Find the Array Concatenation Value
Strobogrammatic Number
Duplicate Zeros
DI String Match
Bag of Tokens
Minimum Length of String After Deleting Similar Ends
Two Sum III - Data structure design
Print Immutable Linked List in Reverse
Sentence Similarity III
Maximum Distance Between a Pair of Values
Friends Of Appropriate Ages
Two Sum IV - Input is a BST
Long Pressed Name
Reverse Prefix of Word
Largest Positive Integer That Exists With Its Negative
Reverse Words in a String II
Closest Subsequence Sum
Divide Players Into Teams of Equal Skill
Find Positive Integer Solution for a Given Equation
Circular Array Loop
Shortest Distance to a Character
Push Dominoes
3Sum Smaller
Append Characters to String to Make Subsequence
Merge Two 2D Arrays by Summing Values
Sort Array By Parity II
Number of Distinct Averages
Partition Array According to Given Pivot
Partition List
Closest Binary Search Tree Value II
Last Substring in Lexicographical Order
Two Sum BSTs
Longest Chunked Palindrome Decomposition
Range Sum of Sorted Subarray Sums
Add Two Polynomials Represented as Linked Lists
Largest Merge Of Two Strings
Count Pairs Of Nodes
Faulty Sensor
Watering Plants II
Valid Palindrome IV
Maximum Matching of Players With Trainers
Merge Operations to Turn Array Into a Palindrome

Two Pointers

Reverse a String

Target Sum

Trapping Rain Water

Similar Problems

Exhaustive List