Imagine checking whether a word reads the same forwards and backwards. You could make a reversed copy and compare it with the original. Or you could put one finger on the first letter and another on the last, compare them, and move both fingers towards the middle.
Those fingers are the idea behind two pointers.
The important part is not having two variables. It is giving those variables a job, then explaining why each movement is safe. Once that becomes clear, many array, string, and linked-list questions become easier to reason about.
You only need basic loops, array indexes, and comparisons to start. The linked-list examples later also introduce the small amount of node terminology they need.
1. What is a pointer here?
A pointer is a variable that tells us which position we are currently looking at.
For an array or a string, it is usually an integer index:
index: 0 1 2 3 4
values: [ 1, 2, 6, 9, 12 ]
↑ ↑
left rightIn a Java linked list, it is a reference to a node. It is not a raw memory address that we need to calculate ourselves.
Two pointers means coordinating two positions to avoid work we do not need to repeat. They might move one at a time, together, or at different speeds. They can belong to one input or two different inputs.
The main movement patterns
| Movement | What the pointers mean | Typical use |
|---|---|---|
| Towards each other | Left and right boundaries of what remains | Palindrome checking, pair sum in a sorted array |
| In the same direction | A position to read and a position to write | Removing duplicates, moving zeroes |
| Through two inputs | The next unused position in each input | Merging two sorted arrays |
| Fast and slow | Two node references moving at different speeds | Middle of a linked list, cycle detection |
| Away from a center | The boundaries of a growing candidate | Expanding a palindromic substring |
We will build each idea using small examples. The picture is a summary; the reasoning and code below explain the details.
2. How do I recognize a two-pointer question?
Look for a useful relationship between two positions, not just a keyword in the question.
Common clues include:
- Comparison: compare the beginning with the end, or compare the next item from two sequences.
- Searching: find a pair in sorted input, where increasing or decreasing a position changes the result predictably.
- Partitioning or filtering: keep some values at the front of an array while reading the original values in order.
- Different speeds: find a middle node or detect a loop without storing every visited node.
- Expansion: grow a candidate outwards from a starting center.
Comparison, searching, and partitioning are useful reminders. They are not proof that two pointers will work.
Before writing code, answer four questions:
- What does each pointer represent?
- What do we already know about the positions we have passed?
- Which pointer should move, and why can that move not lose the answer?
- When should we stop?
The fact that stays true as we move is called an invariant. Think of it as a promise we protect throughout the loop.
3. Example: is a string a palindrome?
A palindrome reads the same forwards and backwards. "level" is a palindrome; "apple" is not.
For now, compare characters exactly. Spaces, punctuation, and letter case count. These examples use ordinary English characters; they do not attempt full Unicode normalization or the separate “ignore punctuation and case” variation.
Start with a simple approach
Reverse a copy of the string and compare it with the original. This takes O(n) time and O(n) extra memory.
Can we compare the mirrored positions without making the copy?
level ↑ ↑ left = 0, right = 4: l == l; move both inward level ↑ ↑ left = 1, right = 3: e == e; move both inward level ↑ left = right = 2: only the middle remains; finished
Why do both pointers move?
If the first and last characters match, we have finished checking that pair. The next unchecked pair is one position further in on each side.
If any pair does not match, the whole string cannot be a palindrome. We can return immediately.
Invariant: every pair outside left..right has already matched. We only need to check what remains inside.
public static boolean isPalindrome(String text) {
int left = 0; // First unchecked character.
int right = text.length() - 1; // Last unchecked character.
while (left < right) { // A distinct mirrored pair remains.
if (text.charAt(left) != text.charAt(right)) {
return false; // One mismatch disproves the palindrome.
}
left++; // This left character is now checked.
right--; // Its mirrored partner is checked too.
}
return true; // All required pairs matched.
}Why left < right, not left <= right? The middle character would only be compared with itself, so it needs no extra check.
An empty string or one-character string returns true: neither contains a mismatching pair. The method expects a non-null string.
Cost: O(n) time, O(1) extra memory. The improvement over reversing a copy is primarily memory, not a change from quadratic to linear time. Early stopping can also help when a mismatch appears quickly.
4. Example: find a pair with a target sum in a sorted array
Given a sorted array, find two different indexes whose values add up to the target.
values = [1, 2, 6, 9, 12, 15, 17] target = 24
The straightforward solution tries every pair. There are roughly n × (n - 1) / 2 pairs, so this takes O(n²) time.
Sorted order gives us a better way. Start with the smallest and largest remaining values.
| Left value | Right value | Sum | What we do |
|---|---|---|---|
| 1 | 17 | 18 | Too small: move left forward |
| 2 | 17 | 19 | Too small: move left forward |
| 6 | 17 | 23 | Too small: move left forward |
| 9 | 17 | 26 | Too large: move right backward |
| 9 | 15 | 24 | Found the pair |
The result is indexes [3, 5], containing 9 and 15. Indexes in this article are zero-based.
Why is moving left safe when the sum is too small?
Suppose 1 + 17 < 24. The value 17 is the largest remaining partner for 1.
If even that partner is too small, pairing 1 with 15, 12, or anything smaller will also be too small. No remaining pair using this 1 can work. We can discard that left position and try a larger value.
Why is moving right safe when the sum is too large?
Suppose 9 + 17 > 24. The value 9 is the smallest remaining partner for 17.
Pairing 17 with a larger remaining value would make the sum even bigger. No remaining pair using this 17 can work. We can discard that right position and try a smaller value.
Invariant: if a solution remains, both of its indexes are inside the current left..right range.
public static int[] findPair(int[] values, long target) {
int left = 0;
int right = values.length - 1;
while (left < right) { // Never reuse the same index.
long sum = (long) values[left] + values[right]; // Add without int overflow.
if (sum == target) {
return new int[] {left, right}; // Return one valid pair of indexes.
}
if (sum < target) {
left++; // This smallest value cannot work.
} else {
right--; // This largest value cannot work.
}
}
return new int[] {-1, -1}; // No pair of different indexes exists.
}Cost: O(n) time, O(1) extra memory, including the fixed-size result. Each failed comparison removes a position, so there are at most n - 1 comparisons.
What if the input is not sorted?
The movement rule is not safe. Consider [3, 2, 4] with target 6. Starting at 3 and 4 gives 7; moving right discards 4, even though 2 + 4 is the answer.
You could sort first, but sorting costs O(n log n) with a usual comparison sort and changes the positions. If the question asks for original indexes, you must preserve them separately or use another method, such as a hash map.
Negative values are not a problem for this pair-sum method, provided the array is sorted. Duplicates are allowed too: [3, 3] can supply two different indexes for target 6. A single [3] cannot.
This version finds one pair. Returning all pairs or counting every index pair needs additional duplicate-handling rules.
5. Example: remove duplicates from a sorted array
Now both pointers move forwards, but they have different jobs.
Baseline: collect unique values in a new list and copy them back. Sorted input makes this O(n) time, but the list takes O(n) extra space. Shifting the suffix after every duplicate avoids the list but can take O(n²) time. A read/write prefix keeps the linear scan without that extra collection or repeated shifting.
values = [1, 1, 2, 2, 3] wanted = [1, 2, 3] at the front of the same array return = 3
readexamines the next value.writeidentifies the next free position in the unique prefix.
Sorted order places equal values next to each other. The first value is already unique, so the next free position begins at 1.
| Read index | Value | Decision | Valid prefix after the decision | Next write index |
|---|---|---|---|---|
| 1 | 1 | Same as the last kept value: skip | [1] |
1 |
| 2 | 2 | Different: keep | [1, 2] |
2 |
| 3 | 2 | Same: skip | [1, 2] |
2 |
| 4 | 3 | Different: keep | [1, 2, 3] |
3 |
Invariant: positions before write contain exactly the unique values encountered so far, in order.
public static int removeDuplicates(int[] values) {
if (values.length == 0) {
return 0; // There is no first value to keep.
}
int write = 1; // values[0] is already kept.
for (int read = 1; read < values.length; read++) {
if (values[read] != values[write - 1]) { // Compare with the last kept value.
values[write] = values[read]; // Put the new value in the valid prefix.
write++; // Advance only when we keep a value.
}
}
return write; // Next free index equals kept length.
}Why does overwriting not destroy something we still need? write never moves ahead of read. We write at or behind the value we have just examined, not into the unread part.
Why compare with values[write - 1]? It is the last value we kept. A different value should become the next member of the unique prefix.
Java arrays do not shrink. After the method returns 3, only the first three positions are meaningful. The leftover tail is not part of the answer.
Cost: O(n) time, O(1) extra memory. On unsorted [1, 2, 1], this method would keep all three values; it cannot remove non-adjacent duplicates without a different strategy.
Continue with the complete Remove Duplicates from a Sorted Array explanation, then compare Move Zeroes to the End. Moving zeroes also uses read/write positions, but keeps every non-zero value rather than one copy of each value.
6. Example: merge two sorted arrays
Two pointers do not have to belong to the same array.
Baseline: concatenate both arrays and sort the combined result. A usual comparison sort costs O((n+m) log(n+m)) time, and the required new result takes O(n+m) space, plus the sort’s workspace. The two-pointer merge uses the existing order to reach O(n+m) time. Its result allocation is still required; the improvement is work, not eliminating the output array.
first = [1, 4, 6, 9, 10] second = [9, 10, 16, 22, 30]
Use i for the next unused value in first and j for the next unused value in second. Compare those values and copy the smaller one to the result.
Why only compare those two? Each input is sorted, so its next unused value is the smallest value it has left. The smaller of those two candidates is therefore the smallest remaining value overall.
compare 1 and 9 → take 1 from first compare 4 and 9 → take 4 from first compare 6 and 9 → take 6 from first compare 9 and 9 → take 9 from first compare 10 and 9 → take 9 from second compare 10 and 10 → take 10 from first first is exhausted → copy the rest of second result = [1, 4, 6, 9, 9, 10, 10, 16, 22, 30]
Invariant: the written part of the result contains the smallest consumed values in sorted order. i and j point to the next unused values.
public static int[] mergeSorted(int[] first, int[] second) {
int[] result = new int[first.length + second.length];
int i = 0; // Next unused value in first.
int j = 0; // Next unused value in second.
int write = 0; // Next output position.
while (i < first.length && j < second.length) { // Both values must exist.
if (first[i] <= second[j]) { // Prefer first on a tie.
result[write++] = first[i++]; // Copy, then advance source and output.
} else {
result[write++] = second[j++];
}
}
while (i < first.length) { // second may have run out first.
result[write++] = first[i++];
}
while (j < second.length) { // first may have run out first.
result[write++] = second[j++];
}
return result;
}index++ uses the old index for the current access, then increases it. For example, result[write++] = first[i++] means copy first[i] into result[write], then increase both indexes.
Why use && in the comparison loop? We access both arrays there. If either input is exhausted, its current value does not exist. The two later loops safely copy whichever values remain.
There is also an output index, write. That does not stop this being a two-pointer technique: the two coordinated input positions make the choice; the output index only records where to place it.
Cost: O(n + m) time and O(n + m) memory for the new result. Apart from that output, the working state is O(1). This implementation is not in-place.
Merging keeps duplicates. A union keeps only distinct values. Read Union of Two Sorted Arrays to see the extra duplicate check.
7. Example: find the middle of a linked list
A linked list is a chain of nodes. Each node holds a value and a reference named next. null means there is no next node.
Unlike an array, a singly linked list does not let us jump directly to the middle index. The baseline counts all nodes, then walks halfway: O(n) time and O(1) space, with two traversals. Fast/slow pointers find the middle in one pass with the same asymptotic bounds. This is a simpler single-pass invariant, not a claim that two passes are quadratic.
Start both at the head. Each round, move slow one link and fast two links.
list: 1 → 2 → 3 → 4 → 5 → null start: slow = 1, fast = 1 round 1: slow = 2, fast = 3 round 2: slow = 3, fast = 5 stop: fast has no next node; middle = 3
After t rounds, slow has moved t links and fast has moved 2t links. When fast reaches the end, slow is halfway through.
Here is the node type shared by this example and cycle detection:
public static final class ListNode {
public final int value;
public ListNode next;
public ListNode(int value) {
this.value = value;
}
}public static ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) { // A two-link move is safe.
slow = slow.next; // One link per round.
fast = fast.next.next; // Two links per round.
}
return slow; // null for an empty list.
}Why check both fast and fast.next? We cannot access .next on null. Java evaluates && left to right and stops when the first condition is false, so the guard safely checks the links before moving.
For 1 → 2 → 3 → 4, this version returns 3, the second middle. A problem asking for the first middle needs a different stopping rule.
Cost: O(n) time, O(1) extra memory. This middle-finding method assumes the list has no cycle; otherwise there is no end to reach.
8. Example: detect a cycle in a linked list
A cycle exists when following next eventually returns to a node we have already visited.
1 → 2 → 3 → 4
↑ │
└───────┘The baseline stores visited node references in a set and returns true at the first repeated reference. It takes expected O(n) time and O(n) memory. Floyd’s fast/slow technique keeps O(n) time while reducing the working memory to O(1). Repeated node values do not count as repeated node objects in either method.
public static boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) { // Stop if the list has an end.
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // Same node object, not equal values.
return true;
}
}
return false; // fast reached the end.
}For the pictured list:
| Round | Slow node | Fast node |
|---|---|---|
| Start | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 2 |
| 3 | 4 | 4: they meet |
Why must they meet in a cycle?
Once both are inside the cycle, fast gains one node on slow per round. If the cycle contains c nodes, their relative positions change by one, wrapping around after c. Within at most c more rounds, the gap becomes zero.
Two details prevent common bugs:
- Move before comparing. They start at the same head even in a list without a cycle. The initial equality proves nothing.
- Compare node identity, not values. Two separate nodes can both contain
7. That does not create a cycle.slow == fastasks whether both references point to the same node object.
Cost: O(n) time, O(1) extra memory, where n is the number of distinct reachable nodes. This method detects whether a cycle exists; locating its entry is a separate extension.
9. Example: expand outwards from a center
Inward palindrome checking answers: “Is this whole string a palindrome?”
Outward expansion asks: “How large a palindrome can I grow around this center?” It is useful when searching for palindromic substrings.
Baseline for finding the longest palindromic substring: try all O(n²) start/end pairs and scan each candidate from both ends. That costs O(n³) time and O(1) working space if boundaries are stored instead of copying each candidate. Each center expansion reuses the fact that its inner substring is already palindromic, reducing the overall search to O(n²). Faster specialized methods exist, but center expansion is the clear general improvement taught here.
There are two kinds of centers:
Odd length:
level
↑ start with left = right = 2, at v
expand to e/e, then l/l
Even length:
abba
↑↑ start with left = 1, right = 2, at b/b
expand to a/aInvariant: the characters strictly between left and right already form a palindrome. If the next boundary pair also matches, we can extend it.
public static int expandLength(String text, int left, int right) {
while (left >= 0 && right < text.length() // Both boundary characters exist.
&& text.charAt(left) == text.charAt(right)) {
left--; // Try the next outer pair.
right++;
}
return right - left - 1; // Last valid range: left+1..right-1.
}Call this helper with an actual center: (center, center) for odd length, or (center, center + 1) for even length. For example, expandLength("level", 2, 2) returns 5; expandLength("abba", 1, 2) returns 4.
Why subtract one? On stopping, the pointers are just outside the last valid palindrome. Its boundaries are left + 1 and right - 1, so its length is (right - 1) - (left + 1) + 1.
One expansion takes O(n) time in the worst case and O(1) extra memory. Trying odd and even centers at every position takes O(n²) time overall. Having two pointers does not automatically make an algorithm linear.
10. Why is two pointers often efficient?
The efficiency comes from not revisiting work unnecessarily.
- A sorted pair-sum search discards one impossible boundary each round.
- A palindrome check settles a mirrored pair each round.
- Read/write compaction examines each original value once.
- A merge consumes each value from each input once.
The loops do not have to look identical. To reason about time, count how many times the pointers can move and how much work each move does.
The technique can reduce extra memory too, but only when the particular solution avoids additional storage. The merge above still allocates its output.
| Example | Time | Additional memory |
|---|---|---|
| Whole-string palindrome | O(n) | O(1) |
| One target pair in sorted input | O(n) | O(1) |
| Remove duplicates in place | O(n) | O(1) |
| Merge sorted arrays of lengths n and m | O(n + m) | O(n + m), including the result |
| Linked-list middle or cycle detection | O(n) | O(1) |
| Expand around every string center | O(n²) | O(1), excluding any returned substring |
11. Two pointers, sliding window, or prefix sum?
These ideas can overlap, but they keep different information.
Two pointers is the broad technique of coordinating positions. Sliding window is a common form where two boundaries maintain a contiguous range and its state, such as a sum or a frequency table.
For a subarray-sum problem with non-negative values, growing a window cannot decrease its sum, and shrinking it cannot increase its sum. That predictable change can justify a window. The exact rules still depend on whether you are finding, counting, or maximizing something, particularly when zeroes are present.
With negative values, those directions are no longer reliable. A range can grow yet its sum decrease. Prefix sums and stored earlier totals are often more useful for questions such as Subarray Sum Equals K.
Do not confuse this with the sorted pair problem above: its two selected values need not form a contiguous range. Sorted pair-sum reasoning remains valid with negative values.
12. Common mistakes and how to avoid them
- Moving a pointer because a template says so. Explain the value or candidate you are discarding first.
- Using sorted pair-sum moves on unsorted input. The elimination proof depends on order.
- Reusing one element twice. For a pair of distinct indexes, stop when
leftmeetsright. - Advancing
writefor a rejected value.writecounts what you kept, not what you inspected. - Returning the last filled index instead of the length. With a next-free write pointer, the pointer itself is the length.
- Not advancing after a decision. A loop that repeats the same state can run forever.
- Using
||while reading two current array values. Both indexes must be valid for a comparison; copy leftovers separately. - Comparing linked-list values to detect a cycle. Compare node objects, and compare after moving.
- Forgetting overflow in a pair sum. Convert to
longbefore adding twointvalues. - Assuming O(n) time or O(1) space just because there are two pointers. Count the actual work and storage.
13. A short checklist before you code
Write down these five lines for your question:
Input guarantee: What makes the movement rule valid? Pointer meanings: What position or boundary does each variable represent? Invariant: What remains true after every round? Movement: Why can this move not lose a valid answer? Stop and result: When are we done, and what exactly do we return?
For sorted pair sum, the answers are: sorted input; smallest/largest remaining candidates; any unfound solution is still inside the range; discard a boundary that cannot make the target; stop on a match or when two different indexes no longer remain.
For duplicate removal, they are: sorted input; next value to inspect/next free output position; unique prefix before write; keep only a value different from the last kept one; stop after reading all values and return the prefix length.
That reasoning is more reusable than memorizing one loop.
14. Practice and runnable examples
Start with palindrome checking and sorted pair sum from this article. Then try these published explanations:
- Remove Duplicates from a Sorted Array — separate reading from writing.
- Move Zeroes to the End — keep relative order while transforming an array in place.
- Union of Two Sorted Arrays — coordinate two inputs and handle duplicates.
You can also browse the Two Pointers pattern page or the DSA Master Sheet for more practice.
All Java snippets above are methods or a nested node class belonging to the same example class. Download the complete runnable Java file, which includes a main method and sample calls. Array and string methods expect non-null inputs; the sorted-array methods assume ascending order. Linked-list methods accept an empty list.
The idea to remember is simple: give each pointer a meaning, then move it only when you can explain why that move is safe.
Practice next
Next lessonRemove Duplicates from a Sorted ArrayApply the read/write invariant to a complete problem.