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:


C++:


Python:


Using two pointers, you can reverse the array inplace 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
andright
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:


C++:


Python:


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 nonnegative 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
andright
, and two variables to keep track of the maximum height from both sides,left_max
andright_max
.  Move the pointers towards each other, updating
left_max
andright_max
as needed.  The trapped water at any position depends on the minimum of
left_max
andright_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:


C++:


Python:


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 twopointer solution with O(n)
time complexity and O(1)
space complexity.
Similar Problems
 Is subsequence
 Merge strings alternately
The twopointers technique can be applied to a wide range of problems. Here’s a list of some common problems that can be tackled using this strategy:
Two Sum: Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
.Three Sum: Find all unique triplets in the array which give the sum of zero.
Remove Duplicates from Sorted Array: Given a sorted array, remove the duplicates inplace and return the new length.
Palindrome String: Check if a given string is a palindrome by comparing characters from both ends.
Container with Most Water: Given
n
nonnegative integers representing an elevation map where the width of each bar is 1, find two lines, which together with the xaxis forms a container, such that the container contains the most water.Trapping Rain Water: As explained previously.
Minimum Size Subarray Sum: Given an array of positive integers
nums
and a positive integertarget
, find the minimal length of a contiguous subarray of which the sum is greater than or equal totarget
.Find the Duplicate Number: Given an array of integers containing
n + 1
integers where each integer is between 1 andn
inclusive, find the duplicate number in linear runtime complexity.Longest Substring Without Repeating Characters: Given a string, find the length of the longest substring without repeating characters using a sliding window approach.
Valid Triangle Number: Given an array consists of nonnegative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Number of Longest Increasing Subsequence: Find the number of longest increasing subsequences in an unsorted array of integers.
Reverse String: Write a function that reverses a string by swapping characters from both ends.
Squares of a Sorted Array: Given an array of integers sorted in nondecreasing order, return an array of the squares of each number, also in sorted nondecreasing order, without using extra space.
Merge Sorted Array: Given two sorted integer arrays
nums1
andnums2
, mergenums2
intonums1
as one sorted array without using extra space.Linked List Cycle II: Given a linked list, return the node where the cycle begins. If there is no cycle, return
null
.
Two pointers can be an efficient technique, especially when dealing with sorted arrays or linked lists. It’s often used to simplify code and reduce time complexity, making it a powerful tool to have in your programming toolkit.
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 Kth Smallest Pair Distance
 Reverse Words in a String III
 Kdiff 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 RunLength 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 KSum 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