Master the Two Pointers Pattern in Python (Part 1): Two Sum, Squares of Sorted Array & Remove Duplicates
A beginner-friendly guide to understanding, recognizing, and applying the Two Pointers pattern in coding interviews.
Introduction
If you've spent time solving coding interview problems, you've probably noticed a common pattern: many array problems seem to invite a nested loop solution. While that approach works, it often results in O(n²) time complexity, which becomes inefficient as the input size grows.
This is where the Two Pointers pattern shines.
Instead of comparing every possible combination, the Two Pointers technique strategically moves one or two indices through the array to eliminate unnecessary work. With the right observation, problems that initially appear quadratic can often be solved in O(n) time while using O(1) extra space.
The Two Pointers pattern is one of the most frequently tested concepts in technical interviews. Whether you're preparing for coding assessments or improving your problem-solving skills, recognizing this pattern can help you arrive at cleaner, more efficient solutions.
In this first part of the series, we'll explore three classic problems that demonstrate different applications of the Two Pointers technique:
Two Sum II – Using pointers from opposite ends to find a target pair in a sorted array.
Squares of a Sorted Array – Building a sorted result by comparing values from both ends of the array.
Remove Duplicates from Sorted Array – Using fast and slow pointers for efficient in-place array modification.
For each problem, we'll start with the intuitive approach, identify its limitations, and then develop an optimized solution step by step. Along the way, we'll analyze time and space complexity, walk through examples, and focus on the reasoning behind each decision rather than simply presenting the final code.
By the end of this article, you'll not only know how to solve these problems but also understand when to recognize the Two Pointers pattern and why it leads to more efficient solutions.
What Is the Two Pointers Pattern?
The Two Pointers pattern is an algorithmic technique that uses two indices or references to traverse a data structure—such as an array, string, or linked list—in a coordinated way to solve problems more efficiently.
Instead of repeatedly scanning the same elements with nested loops, the two pointers move according to the problem's constraints, allowing us to eliminate unnecessary comparisons and reduce the overall time complexity.
In many cases, a brute-force solution requires checking every possible combination, resulting in O(n²) time complexity. By using two pointers intelligently, the same problem can often be solved in O(n) time with O(1) extra space.
How Does It Work?
The idea is simple:
Initialize two pointers at meaningful positions.
Compare the elements they reference.
Move one or both pointers based on the current condition.
Continue until the required result is found or the pointers meet.
The exact movement of the pointers depends on the problem. Sometimes they move toward each other, while in other cases they move in the same direction.
For example, in a sorted array, one pointer may start at the beginning and the other at the end.
Left Right
↓ ↓
[1] [3] [5] [7] [9] [11] [15]
If the current pair doesn't satisfy the condition:
Move the left pointer forward to increase the value.
Move the right pointer backward to decrease the value.
This simple observation helps avoid exploring combinations that cannot produce the desired result.
Why Is It Efficient?
Consider finding a pair of numbers that adds up to a target value.
A straightforward approach compares every pair:
Array: [1, 3, 5, 7]
| Compare | Checked? |
|---|---|
| 1 & 3 | ✅ |
| 1 & 5 | ✅ |
| 1 & 7 | ✅ |
| 3 & 5 | ✅ |
| 3 & 7 | ✅ |
| 5 & 7 | ✅ |
This performs approximately n² comparisons.
With the Two Pointers approach, each pointer moves at most n times, so the total number of operations grows linearly with the input size.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Two Pointers | O(n) | O(1) |
Why Is This Pattern Important?
The Two Pointers technique appears frequently in coding interviews because it tests more than coding ability—it evaluates your ability to identify patterns and optimize algorithms.
You'll commonly encounter it in problems involving:
Sorted arrays
Pair or triplet searching
Duplicate removal
In-place array modifications
String and palindrome validation
Merging sorted sequences
Learning when to apply this pattern is just as important as learning how to implement it.
When Should You Use the Two Pointers Pattern?
One of the biggest challenges in coding interviews isn't implementing the Two Pointers technique—it's recognizing when it's the right tool for the problem.
While there isn't a fixed rule, certain patterns in the problem statement are strong indicators that Two Pointers might lead to an efficient solution.
1. The Input is Sorted
A sorted array is one of the strongest signals.
Because the elements are already ordered, moving a pointer in one direction has a predictable effect:
Moving the left pointer to the right generally increases the value.
Moving the right pointer to the left generally decreases the value.
This property allows us to eliminate many unnecessary comparisons that a brute-force solution would otherwise perform.
Whenever you see a sorted array, pause for a moment and ask yourself: "Can I solve this using two pointers instead of nested loops?"
2. You Need to Find a Pair or Triplet
Many interview problems ask you to:
Find two numbers whose sum equals a target.
Find three numbers that satisfy a condition.
Determine whether a valid pair exists.
These problems often become much simpler when two pointers work together instead of checking every possible combination.
Examples include:
Two Sum II
3Sum
3Sum Closest
3. You Need to Compare Elements from Both Ends
Some problems require information from the beginning and the end of a sequence at the same time.
In these cases, placing one pointer at each end and moving them toward each other is often the most efficient strategy.
Examples include:
Valid Palindrome
Container With Most Water
Squares of a Sorted Array
4. The Problem Requires In-Place Modification
Sometimes the goal isn't to find an answer but to modify the existing array without using additional space.
A common approach is to use:
A fast pointer to scan the array.
A slow pointer to keep track of where the next valid element should be placed.
Examples include:
Remove Duplicates from Sorted Array
Remove Element
Move Zeroes
5. The Problem Emphasizes Constant Extra Space
If the problem explicitly asks for an O(1) extra space solution, Two Pointers is often worth considering.
Since it only maintains a few variables, the technique naturally satisfies this constraint while remaining efficient.
Quick Recognition Checklist
Before jumping into the implementation, ask yourself these questions:
✅ Is the array or string sorted?
✅ Am I searching for a pair or a triplet?
✅ Do I need to compare elements from both ends?
✅ Can I process the data in a single pass?
✅ Does the problem require modifying the input in place?
✅ Is an O(1) extra space solution preferred?
If you answer "Yes" to one or more of these questions, the Two Pointers pattern is likely worth exploring.
The Two Pointers pattern is not about memorizing algorithms—it's about recognizing opportunities to eliminate unnecessary work by moving two pointers intelligently.
Types of Two Pointers Techniques
The term Two Pointers describes a family of techniques rather than a single algorithm. The way the pointers are initialized and moved depends entirely on the problem being solved.
Among the many variations, two are used most frequently in coding interviews and competitive programming.
1. Opposite Direction Pointers
In this approach, one pointer starts at the beginning of the array while the other starts at the end. During each iteration, one or both pointers move toward the center until they meet or the required condition is satisfied.
Left Right
↓ ↓
[1] [3] [5] [7] [9] [11] [15]
When to Use
This technique works particularly well when:
The input is sorted.
You need to find a pair of elements.
The decision to move a pointer depends on comparing the current result with a target value.
Common Problems
Two Sum II
Squares of a Sorted Array
Valid Palindrome
Container With Most Water
Opposite Direction Pointers usually rely on the sorted order of the input. Moving either pointer has a predictable effect, allowing you to eliminate unnecessary comparisons.
2. Same Direction (Fast & Slow) Pointers
In this variation, both pointers start from the beginning of the data structure but move at different times or at different speeds.
Typically:
The fast pointer explores every element.
The slow pointer tracks the position where the next valid element should be placed or processed.
Slow
↓
[1] [2] [2] [3] [4] [4] [5]
↑
Fast
Unlike the previous technique, the pointers do not move toward each other. Instead, they move in the same direction, each serving a different purpose.
When to Use
This approach is useful when:
Removing duplicates.
Modifying an array in place.
Partitioning or filtering elements.
Maintaining a compact valid portion of the array.
Common Problems
Remove Duplicates from Sorted Array
Remove Element
Move Zeroes
Think of the fast pointer as the reader and the slow pointer as the writer. The fast pointer scans the input, while the slow pointer builds the desired result in place.
Which Technique Will We Use?
In this article, we'll apply both variations:
| Problem | Technique |
|---|---|
| Two Sum II | Opposite Direction Pointers |
| Squares of a Sorted Array | Opposite Direction Pointers |
| Remove Duplicates from Sorted Array | Fast & Slow Pointers |
By understanding these two techniques, you'll be able to solve a wide range of interview questions efficiently.
Problem 1: Two Sum II – Input Array Is Sorted
Problem Overview
Let's begin with one of the most classic applications of the Opposite Direction Pointers technique.
In this problem, you're given a sorted array of integers and a target value. Your task is to find the two numbers whose sum equals the target and return their 1-based indices.
Since the array is already sorted, we can take advantage of its ordering to avoid checking every possible pair.
Example:
Input:
numbers = [2, 7, 11, 15]
target = 9
Output:
[1, 2]
Explanation:
numbers[0] + numbers[1] = 2 + 7 = 9
The required 1-based indices are [1, 2].
How Would You Solve It?
Before jumping into the optimized solution, let's think about the most natural approach.
If you were solving this problem for the first time, you would probably compare every pair of numbers until you found one whose sum equals the target.
This approach is simple and correct, but is it efficient?
Brute Force Approach
When solving this problem for the first time, the most straightforward idea is to check every possible pair of numbers and see whether their sum equals the target.
This approach doesn't require any special observations about the array. We simply iterate through all possible combinations using two nested loops.
For each element, we compare it with every element that comes after it:
Array: [2, 7, 11, 15]
2 → 7 ✓
2 → 11
2 → 15
7 → 11
7 → 15
11 → 15
As soon as we find a pair whose sum equals the target, we return their 1-based indices.
Algorithm
Iterate through each element using the first loop.
For every element, iterate through the remaining elements using a second loop.
Check whether the sum of the current pair equals the target.
If it does, return the corresponding 1-based indices.
Python Implementation
class Solution:
def twoSum(self, numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
Complexity Analysis
| Complexity | Value |
|---|---|
| Time Complexity | O(n²) |
| Space Complexity | O(1) |
The nested loops force us to compare nearly every pair of elements in the worst case. If the array contains n elements, the total number of comparisons grows quadratically, making this solution inefficient for large inputs.
Although this approach is correct, it completely ignores the most important clue in the problem statement—the array is already sorted. Whenever a problem provides a sorted array, it's often an indication that a more efficient solution exists.
Key Observation
The brute-force solution checks every possible pair of numbers, even though many of those comparisons can never lead to the correct answer.
The most important clue in this problem is that the input array is already sorted.
[2] [7] [11] [15]
↑ ↑
Left Right
Since the elements are in increasing order, we know that:
Moving the left pointer one step to the right increases the current sum.
Moving the right pointer one step to the left decreases the current sum.
This simple observation allows us to make informed decisions instead of blindly checking every pair.
How Do We Decide Which Pointer to Move?
Suppose we calculate the current sum:
current_sum = numbers[left] + numbers[right]
There are only three possible cases.
Case 1: Current Sum Equals the Target
If the sum matches the target, we've found the required pair.
current_sum == target
Return the 1-based indices immediately.
Case 2: Current Sum Is Less Than the Target
current_sum < target
The current sum is too small.
Since the array is sorted, moving the right pointer to the left would only make the sum even smaller.
The only way to increase the sum is to move the left pointer to the right.
Left Right
↓ ↓
[2] [7] [11] [15]
2 + 15 = 17
If the sum were too small,
move Left →
Case 3: Current Sum Is Greater Than the Target
current_sum > target
The current sum is too large.
Moving the left pointer to the right would increase the sum even further.
Instead, we move the right pointer to the left, which decreases the sum.
Left Right
↓ ↓
[2] [7] [11] [15]
2 + 15 = 17
Move ← Right
The Key Insight
At every step, we eliminate one impossible set of combinations without ever revisiting them.
Instead of checking every possible pair, each pointer moves in only one direction, and each element is visited at most once.
The sorted order of the array tells us exactly which pointer to move. That's why the Two Pointers approach works here. Without a sorted array, moving a pointer would not give us any guarantee about whether the sum increases or decreases.
Optimized Approach: Opposite Direction Two Pointers
Instead of comparing every possible pair, we maintain two pointers:
Left Pointer starts at the beginning of the array.
Right Pointer starts at the end of the array.
During each iteration, we calculate the sum of the two elements and decide which pointer to move based on the result.
Algorithm
Initialize two pointers:
left = 0right = len(numbers) - 1
While
left < right:Calculate the current sum.
If the sum equals the target, return the 1-based indices.
If the sum is smaller than the target, move the left pointer one step to the right.
Otherwise, move the right pointer one step to the left.
Continue until the required pair is found.
Dry Run
Let's walk through an example to see how the pointers move.
Input
numbers = [2, 7, 11, 15]
target = 9
| Step | Left | Right | Current Pair | Sum | Action |
|---|---|---|---|---|---|
| 1 | 2 | 15 | (2, 15) | 17 | Sum > Target → Move Right |
| 2 | 2 | 11 | (2, 11) | 13 | Sum > Target → Move Right |
| 3 | 2 | 7 | (2, 7) | 9 | ✅ Target Found |
Notice how we never compare unnecessary pairs such as (7, 11) or (11, 15). The sorted order allows us to eliminate them without checking.
Python Implementation
class Solution:
def twoSum(self, numbers, target):
left = 0
right = len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right -= 1
Complexity Analysis
| Complexity | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Why is the Time Complexity O(n)?
Although there are two pointers, each pointer moves in only one direction:
The left pointer only moves forward.
The right pointer only moves backward.
Since each pointer can move at most n times, the total number of operations is proportional to the size of the array.
Having two pointers does not mean the algorithm is O(2n). In Big-O notation, constant factors are ignored, so O(2n) simplifies to O(n).
Key Takeaway
The power of this solution comes from the sorted array. At every step, we can confidently discard one set of impossible pairs by moving the appropriate pointer. This allows us to reduce the time complexity from O(n²) to O(n) without using any extra space.
Problem 2: Squares of a Sorted Array
Problem Overview
At first glance, this problem appears straightforward. You're given a sorted array of integers, and your task is to return a new array containing the square of each number, with the result also sorted in non-decreasing order.
The challenge lies in the presence of negative numbers.
When negative values are squared, they become positive, which can disrupt the original sorted order.
For example:
Input:
[-7, -3, 2, 3, 11]
After Squaring:
[49, 9, 4, 9, 121]
Although the input array is sorted, the squared values are not.
Our goal is to produce the correctly sorted result without performing an additional sort, since sorting would increase the overall time complexity.
Example
Input:
nums = [-4, -1, 0, 3, 10]
Output:
[0, 1, 9, 16, 100]
Explanation:
After squaring:
[16, 1, 0, 9, 100]
Reordering them gives:
[0, 1, 9, 16, 100]
Constraints
The important observations for solving the problem are:
The input array is already sorted.
The array may contain negative, zero, and positive numbers.
The output must also be sorted in non-decreasing order.
Simply squaring each element does not preserve the sorted order because negative numbers become positive after squaring.
How Would You Solve It?
A natural first approach is:
Square every element in the array.
Sort the resulting array.
This solution is easy to implement, but can we avoid the extra sorting step?
Since the original array is already sorted, there might be a way to use that property to achieve a more efficient O(n) solution.
Brute Force Approach
The most straightforward solution is to square every element in the array and then sort the resulting array.
This approach is simple because we don't need to worry about the ordering of negative and positive numbers. Once every value is squared, sorting automatically arranges the elements in non-decreasing order.
Algorithm
Traverse the array and square each element.
Store the squared values in a new array.
Sort the new array.
Return the sorted array.
Python Implementation
class Solution:
def sortedSquares(self, nums):
result = []
for num in nums:
result.append(num * num)
result.sort()
return result
Complexity Analysis
| Complexity | Value |
|---|---|
| Time Complexity | O(n log n) |
| Space Complexity | O(n) |
The algorithm performs two operations:
Squaring every element takes O(n) time.
Sorting the squared values takes O(n log n) time.
Since O(n log n) dominates O(n), the overall time complexity is:
O(n) + O(n log n) = O(n log n)
While this solution is correct, it doesn't take advantage of the fact that the input array is already sorted. The additional sorting step becomes unnecessary if we can intelligently use the original ordering of the array.
Can We Do Better?
The answer is yes.
Instead of sorting the squared values after computing them, we can use a simple observation about the original sorted array to build the final answer in O(n) time.
But before writing any code, let's understand why the largest squared value is always located at one of the two ends of the array.
Key Observation
The brute-force solution works, but it performs an unnecessary sorting step.
The important question is:
Can we determine the largest squared value without sorting?
The answer is yes, and the key lies in understanding how squaring affects negative numbers.
Consider the following sorted array:
[-7, -3, -1, 2, 4, 6]
After squaring each element:
[49, 9, 1, 4, 16, 36]
Notice that the largest squared value comes from either:
the leftmost element (largest negative number in terms of absolute value), or
the rightmost element (largest positive number).
This happens because squaring depends on the absolute value of a number, not its sign.
For example:
|-7| = 7
|6| = 6
7² > 6²
Similarly,
|-3| = 3
|4| = 4
4² > 3²
At any point in the array, the element with the greater absolute value will produce the larger square.
The largest squared value is always found at one of the two ends of the sorted array.
How Does This Help?
Since we can identify the largest square by comparing the absolute values at both ends, we no longer need to sort the squared values.
Instead:
Compare the absolute values of the leftmost and rightmost elements.
Place the larger square at the end of the result array.
Move the corresponding pointer inward.
Repeat until all positions in the result array are filled.
For example:
nums = [-7, -3, -1, 2, 4, 6]
Compare:
|-7| = 7
|6| = 6
49 is larger.
Place 49 at the last position.
Result:
[_, _, _, _, _, 49]
Next iteration:
[-3, -1, 2, 4, 6]
Compare:
|-3| = 3
|6| = 6
36 is larger.
Result:
[_, _, _, _, 36, 49]
We continue this process until every position is filled.
The Key Insight
Instead of sorting after squaring, we build the answer in reverse order.
By always placing the largest remaining square at the end of the result array, we naturally produce a sorted output in a single pass.
Don't compare the values themselves—compare their absolute values. The number with the greater absolute value always produces the larger square.
Optimized Approach: Opposite Direction Two Pointers
Instead of squaring every element and sorting the result, we use two pointers to identify the largest remaining square at each step.
The left pointer starts at the beginning of the array.
The right pointer starts at the end of the array.
A third index,
position, starts at the last index of the result array.
At each iteration:
Compare the absolute values of
nums[left]andnums[right].Place the larger square at
result[position].Move the corresponding pointer inward.
Decrement
position.
By filling the result array from right to left, we ensure that the largest squares are placed first, resulting in a sorted array without an additional sorting step.
Algorithm
Create a result array of the same size as the input.
Initialize:
left = 0right = len(nums) - 1position = len(nums) - 1
While
left <= right:Compare
abs(nums[left])andabs(nums[right]).Place the larger square at
result[position].Move the corresponding pointer.
Decrement
position.
Return the result array.
Dry Run
Input
nums = [-4, -1, 0, 3, 10]
| Step | Left | Right | Compare | Place At | Result |
|---|---|---|---|---|---|
| 1 | -4 | 10 | 10 | > | |
| 2 | -4 | 3 | -4 | > | |
| 3 | -1 | 3 | 3 | > | |
| 4 | -1 | 0 | -1 | > 0 | |
| 5 | 0 | 0 | Equal | result[0] = 0 | [0, 1, 9, 16, 100] |
Notice that we never sort the array. We simply fill it from the back with the largest remaining square.
Python Implementation
class Solution:
def sortedSquares(self, nums):
n = len(nums)
result = [0] * n
left = 0
right = n - 1
position = n - 1
while left <= right:
if abs(nums[left]) > abs(nums[right]):
result[position] = nums[left] * nums[left]
left += 1
else:
result[position] = nums[right] * nums[right]
right -= 1
position -= 1
return result
Complexity Analysis
| Complexity | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(n) |
Why is the Time Complexity O(n)?
Each iteration places exactly one value into the result array, and either the left or right pointer moves inward.
Since every element is processed only once, the algorithm performs a single linear pass through the array.
The trick isn't squaring the numbers—it's recognizing that the largest absolute value is always at one of the two ends. Once you spot that observation, the two-pointer solution becomes almost automatic.
What We Learned from Squares of a Sorted Array
Although this problem is very different from Two Sum II, it uses the same Opposite Direction Two Pointers technique.
The difference lies in how we use the pointers.
In Two Sum II, the pointers helped us search for a pair whose sum matched the target.
In Squares of a Sorted Array, the pointers help us identify the largest remaining square and place it in its correct position.
The underlying idea remains the same: use the sorted property of the input to eliminate unnecessary work.
Key Takeaways
Squaring a sorted array does not preserve the sorted order.
The largest squared value always comes from one of the two ends of the array.
Comparing absolute values is the key observation.
By filling the result array from right to left, we avoid the need for an additional sorting step.
Each element is processed exactly once, resulting in an O(n) solution.
Whenever a problem involves absolute values or asks you to compare the largest and smallest elements in a sorted array, consider whether Opposite Direction Two Pointers can help simplify the solution.
Pattern Recognition
| Clue in the Problem | Think... |
|---|---|
| Sorted array | Two Pointers |
| Largest value after transformation | Compare both ends |
| Absolute values matter | Check leftmost and rightmost elements |
| Need a sorted output | Build the result from the end |
From Searching to Building
So far, we've seen two different applications of the Opposite Direction Two Pointers technique:
| Problem | Purpose |
|---|---|
| Two Sum II | Find the correct pair |
| Squares of a Sorted Array | Build a sorted result |
This highlights an important lesson:
The Two Pointers pattern isn't tied to a specific type of problem. The same technique can be used for searching, building, partitioning, or transforming data, depending on the problem's requirements.
Problem 3: Remove Duplicates from Sorted Array
Problem Overview
So far, we've solved problems where the pointers started at opposite ends of the array and moved toward each other.
In this problem, we'll explore a different variation of the Two Pointers pattern.
Instead of searching for a pair or building a new array, our goal is to modify the existing array in place by removing duplicate elements.
You're given a sorted array of integers. Your task is to remove the duplicates such that each unique element appears only once. The relative order of the elements must remain unchanged.
Unlike the previous problem, we're not allowed to use an additional array. Instead, we must update the original array using O(1) extra space.
Example
Input:
nums = [1, 1, 2]
Output:
k = 2
nums = [1, 2, _]
Explanation:
The first k elements contain the unique values.
The remaining elements are ignored.
Constraints
The important constraints for this problem are:
The array is sorted in non-decreasing order.
The array must be modified in place.
Only O(1) extra space is allowed.
Return the number of unique elements (
k).
The sorted order ensures that all duplicate values appear next to each other. This observation is the foundation of the Fast & Slow Pointer solution.
How Would You Solve It?
A straightforward idea is to create a new array, iterate through the input, and append an element only if it hasn't been added before.
Although this approach is easy to implement, it violates one of the problem's constraints:
It requires O(n) additional space.
The problem explicitly asks us to modify the array in place.
So the real challenge isn't identifying duplicate values—it's removing them without using extra memory.
Naïve Approach
A straightforward way to solve this problem is to create a new array that stores only the unique elements.
Since the input array is sorted, duplicate values always appear next to each other. We can simply compare the current element with the last unique element that we've already added to the new array.
If the values are different, we append the current element to the result.
Algorithm
Create an empty array called
result.Traverse the input array from left to right.
If the current element is different from the last element in
result, append it.Return the length of
result.
Python Implementation
class Solution:
def removeDuplicates(self, nums):
if not nums:
return 0
result = [nums[0]]
for i in range(1, len(nums)):
if nums[i] != result[-1]:
result.append(nums[i])
return len(result)
Complexity Analysis
| Complexity | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(n) |
The algorithm traverses the array only once, giving it a linear time complexity.
However, it requires another array to store the unique elements, resulting in O(n) additional space.
Although this solution is efficient in terms of time, it does not satisfy the problem constraints because it uses additional memory. The problem specifically requires us to modify the original array in place while using only O(1) extra space.
Can We Do Better?
Instead of creating a separate array, what if we could reuse the original array itself?
Since the array is already sorted, every unique element appears before its duplicates.
This means we don't need extra storage—we only need to keep track of:
where the next unique element should be written, and
which element we're currently reading.
This observation naturally leads us to the Fast & Slow Pointers technique.
Key Observation
The biggest clue in this problem is that the array is already sorted.
This means that all duplicate elements are adjacent to each other.
Consider the following example:
[1, 1, 2, 2, 3, 3, 4]
Instead of asking:
"How do I remove duplicates?"
Think about a different question:
"How do I keep only the unique elements?"
Once we look at the problem this way, the solution becomes much simpler.
A Better Idea
Imagine dividing the array into two parts:
The left side contains only the unique elements we've already processed.
The right side contains the elements we haven't processed yet.
Unique Elements Unprocessed Elements
↓ ↓
[1, 1, 2, 2, 3, 3, 4]
^
Slow
Now introduce two pointers:
Slow Pointer → Marks the position where the next unique element should be placed.
Fast Pointer → Scans the array one element at a time.
Slow
↓
[1, 1, 2, 2, 3, 3, 4]
↑
Fast
How Do the Pointers Move?
For every element visited by the fast pointer, we compare it with the last unique element.
Case 1: Duplicate Element
Slow
↓
[1, 1, 2, 2, 3, 3, 4]
↑
Fast
Both values are 1.
Since we've already stored this value, there's nothing to do.
Simply move the fast pointer forward.
Case 2: New Unique Element
Slow
↓
[1, 1, 2, 2, 3, 3, 4]
↑
Fast
Now the values are different.
This means we've discovered a new unique element.
We move the slow pointer forward and copy the value from the fast pointer.
Before
[1, 1, 2, 2, 3, 3, 4]
↑ ↑
Slow Fast
↓
After
[1, 2, 2, 2, 3, 3, 4]
↑
Slow
The section before the slow pointer now contains only unique elements.
We continue this process until the fast pointer reaches the end of the array.
The Key Insight
The fast pointer explores every element.
The slow pointer builds the final answer inside the original array.
Instead of creating a new array, we simply overwrite duplicate values with the next unique element.
The slow pointer always marks the end of the unique portion of the array. Every time the fast pointer finds a new unique value, we extend that portion by one element.
Optimized Approach: Fast & Slow Pointers
Instead of using an additional array, we can modify the original array in place by maintaining two pointers.
The fast pointer scans every element in the array.
The slow pointer marks the position where the next unique element should be placed.
Whenever the fast pointer encounters a new unique value, we copy that value to the position indicated by the slow pointer and then move the slow pointer forward.
This ensures that the first k elements of the array always contain the unique values in their original order.
Algorithm
If the array is empty, return
0.Initialize the slow pointer at index
0.Traverse the array using the fast pointer, starting from index
1.For each element:
If
nums[fast]is different fromnums[slow]:Move the slow pointer one step forward.
Copy
nums[fast]tonums[slow].
After the traversal, return
slow + 1, which represents the number of unique elements.
Dry Run
Input
nums = [0, 0, 1, 1, 2, 2, 3]
| Step | Slow | Fast | Action | Array |
|---|---|---|---|---|
| Initial | 0 | 1 | Initialize pointers | [0, 0, 1, 1, 2, 2, 3] |
| 1 | 0 | 1 | Duplicate → Move Fast | [0, 0, 1, 1, 2, 2, 3] |
| 2 | 1 | 2 | New value → Copy 1 |
[0, 1, 1, 1, 2, 2, 3] |
| 3 | 1 | 3 | Duplicate → Move Fast | [0, 1, 1, 1, 2, 2, 3] |
| 4 | 2 | 4 | New value → Copy 2 |
[0, 1, 2, 1, 2, 2, 3] |
| 5 | 2 | 5 | Duplicate → Move Fast | [0, 1, 2, 1, 2, 2, 3] |
| 6 | 3 | 6 | New value → Copy 3 |
[0, 1, 2, 3, 2, 2, 3] |
Final Result
Unique Elements = 4
Array = [0, 1, 2, 3, _, _, _]
Only the first 4 elements are considered valid. The values beyond index k - 1 are irrelevant.
Python Implementation
class Solution:
def removeDuplicates(self, nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
Complexity Analysis
| Complexity | Value |
|---|---|
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Why is the Time Complexity O(n)?
The fast pointer visits each element exactly once, while the slow pointer moves forward only when a new unique element is found.
Since each element is processed at most one time, the algorithm runs in linear time.
The slow pointer doesn't visit every index. It only advances when a unique value is discovered, making it an efficient way to build the result in place.
What We Learned
This problem introduced a different variation of the Two Pointers pattern.
Unlike the previous problems, where the pointers moved toward each other, here both pointers move in the same direction, but each has a distinct responsibility:
The fast pointer reads every element.
The slow pointer writes only the unique elements.
This separation of responsibilities allows us to modify the array in place, satisfy the O(1) extra space constraint, and preserve the relative order of the unique elements.
Whenever a problem asks you to modify a sorted array in place while using constant extra space, the Fast & Slow Pointers technique should be one of the first patterns you consider.
Pattern Recognition Cheat Sheet
By now, we've solved three different problems using the Two Pointers pattern. Although the problems were different, they all shared common characteristics that hinted toward an efficient two-pointer solution.
The next time you encounter a new problem, use the following checklist to determine whether the Two Pointers pattern is applicable.
| If you see... | Consider... | Example Problems |
|---|---|---|
| A sorted array | Opposite Direction Pointers | Two Sum II |
| Need to find a pair | Opposite Direction Pointers | Two Sum II |
| Compare values from both ends | Opposite Direction Pointers | Squares of a Sorted Array |
| Absolute values determine the answer | Opposite Direction Pointers | Squares of a Sorted Array |
| Modify a sorted array in place | Fast & Slow Pointers | Remove Duplicates |
| Remove duplicates or filter elements | Fast & Slow Pointers | Remove Duplicates |
| O(1) extra space is required | Fast & Slow Pointers | Remove Duplicates |
A Pattern, Not an Algorithm
One important lesson from these three problems is that Two Pointers is a problem-solving pattern, not a fixed algorithm.
The pointer movement changes depending on the problem.
| Problem | Pointer Movement | Goal |
|---|---|---|
| Two Sum II | Opposite Ends | Find a target pair |
| Squares of a Sorted Array | Opposite Ends | Build a sorted result |
| Remove Duplicates | Same Direction (Fast & Slow) | Modify the array in place |
Even though the implementations are different, the underlying idea remains the same:
Use two coordinated pointers to eliminate unnecessary work and achieve a more efficient solution.
Common Interview Mistakes
Understanding the Two Pointers pattern is only half the battle. During interviews, small implementation mistakes can lead to incorrect results or inefficient solutions.
Here are some of the most common pitfalls to watch out for.
1. Ignoring the Sorted Property
Many candidates immediately reach for nested loops or hash maps without noticing that the input array is already sorted.
A sorted array is often the strongest hint that a Two Pointers solution may exist.
Before writing any code, ask yourself: "Can the sorted order help me eliminate unnecessary comparisons?"
2. Moving the Wrong Pointer
In problems like Two Sum II, moving the wrong pointer can skip the correct answer.
Remember the rule:
If the current sum is too small, move the left pointer.
If the current sum is too large, move the right pointer.
Moving the wrong pointer breaks the logic of the algorithm.
3. Confusing the Two Variations
Not every Two Pointers problem uses pointers moving toward each other.
Choose the technique based on the problem:
| Problem Type | Technique |
|---|---|
| Find a pair in a sorted array | Opposite Direction Pointers |
| Modify a sorted array in place | Fast & Slow Pointers |
Using the wrong variation often leads to unnecessary complexity.
4. Forgetting Edge Cases
Always consider special inputs before finalizing your solution.
Examples include:
Empty array
Array with a single element
All elements are identical
No duplicate elements
Negative values (where applicable)
Thinking through these cases helps prevent bugs and demonstrates attention to detail.
5. Misunderstanding Space Complexity
Using an additional array or set may simplify the implementation, but it increases the space complexity.
If the problem explicitly requires O(1) extra space, your solution should modify the input in place whenever possible.
A correct solution isn't always an accepted solution. Pay close attention to the constraints, especially those related to time and space complexity.
6. Focusing on the Code Instead of the Pattern
Many learners memorize the implementation of a specific problem but struggle when the same idea appears in a different context.
Instead of memorizing code, focus on recognizing the clues:
Is the input sorted?
Do I need to compare both ends?
Can I process the array in a single pass?
Does the problem require an in-place solution?
These questions will help you identify the appropriate Two Pointers technique more consistently.
In interviews, the ability to recognize the underlying pattern is often more valuable than memorizing a particular solution.
Key Takeaways
Throughout this article, we've explored the Two Pointers pattern from its fundamentals to its practical applications in solving interview problems.
Rather than memorizing individual solutions, the goal is to understand why the pattern works and when to apply it.
Here are the most important lessons to remember:
Two Pointers is a problem-solving pattern, not a fixed algorithm.
Recognizing the pattern is more important than memorizing the implementation.
A sorted array is often the strongest clue that a Two Pointers solution may exist.
Opposite Direction Pointers are ideal for searching or comparing elements from both ends of a sorted array.
Fast & Slow Pointers are best suited for modifying data structures in place while using constant extra space.
Always analyze the problem constraints before choosing an approach. Time and space complexity requirements often point toward the most appropriate solution.
Great problem solvers don't memorize hundreds of solutions—they recognize recurring patterns and adapt them to new problems.
What's Next?
In Part 2 of this series, we'll build on the concepts introduced here and tackle more advanced applications of the Two Pointers pattern.
We'll cover:
🎨 Sort Colors – Learn the Dutch National Flag Algorithm for in-place partitioning.
🔺 3Sum – Extend the Two Pointers technique to efficiently find unique triplets.
🎯 3Sum Closest – Adapt the same strategy to search for the closest possible sum.
These problems introduce new ideas while reinforcing the same core pattern you've learned in this article.
Final Thoughts
The Two Pointers pattern is one of the most versatile techniques in algorithm design. Whether you're searching for pairs, transforming arrays, or modifying data in place, understanding how and why two pointers move can dramatically simplify your solutions.
The three problems covered in this article demonstrate that the same pattern can be applied in different ways:
| Problem | Technique | Main Idea |
|---|---|---|
| Two Sum II | Opposite Direction | Search for a target pair |
| Squares of a Sorted Array | Opposite Direction | Build a sorted result |
| Remove Duplicates from Sorted Array | Fast & Slow | Modify the array in place |
Master these foundational applications, and you'll be well prepared to tackle more challenging Two Pointers problems in coding interviews.
Call to Action
If you found this article helpful, consider following this publication for more DSA pattern-based tutorials, AI engineering projects, and technical deep dives. See you in Part 2, where we'll explore more advanced applications of the Two Pointers pattern with Sort Colors, 3Sum, and 3Sum Closest.