Definition
- Two pointers – a technique using two index variables that traverse a data structure together to solve problems efficiently.
- Opposite-end – pointers start at both ends and move inward; works on sorted data for pair-search problems.
- Same-direction – a slow write pointer and a fast read pointer both move forward; used for in-place compaction.
- Fast/slow – one pointer moves twice as fast; detects cycles and finds midpoints in linked lists.
- Benefit – reduces O(n squared) brute-force scans to O(n) with O(1) extra space.
Imagine Rajesh is checking a long printed ledger at the National Bank of India. Instead of scanning every pair of rows, he places one finger at the top and one at the bottom and moves them toward each other for pair searches. Or he keeps one finger on the last good row while another finger scans ahead for compaction. Two fingers, one pass, no copying the whole ledger.
Understanding the Concepts
What is the Two Pointers technique?
The two pointers technique uses two index variables that walk through a data structure, usually a sorted array or a linked list, to solve a problem in O(n) time and O(1) extra space. Instead of a nested loop that checks every pair (O(n squared)), two pointers reduce the work by making a single coordinated sweep.
package com.bank.dsa;
public class TwoPointerDemo {
// Base pattern: two variables walking a structure
// Variant 1: opposite ends moving inward
// Variant 2: same direction, different speeds
// Variant 3: fast/slow for cycle detection
}
How does the opposite-end variant work?
Start with left at the beginning and right at the end of a sorted array. Based on a comparison, move one pointer inward. For a pair sum, if the sum is too small move left up, if too large move right down.
package com.bank.dsa;
import java.math.BigDecimal;
public class PairSumFinder {
public static int[] findPair(BigDecimal[] sorted, BigDecimal target) {
int left = 0, right = sorted.length - 1;
while (left < right) {
BigDecimal sum = sorted[left].add(sorted[right]);
int cmp = sum.compareTo(target);
if (cmp == 0) return new int[]{left, right};
else if (cmp < 0) left++;
else right--;
}
return new int[]{}; // no pair found
}
public static void main(String[] args) {
BigDecimal[] settlements = {
new BigDecimal("1000"), new BigDecimal("3000"),
new BigDecimal("5000"), new BigDecimal("7000")
};
BigDecimal target = new BigDecimal("8000");
int[] pair = findPair(settlements, target);
System.out.println("Pair: [" + pair[0] + ", " + pair[1] + "]");
}
}
Pair: [0, 3]
How does the same-direction variant work?
A slow write pointer marks the boundary of the processed region, and a fast read pointer scans every element. When the fast pointer finds an element that meets a condition, it is copied to the write position and the write pointer advances. This does in-place compaction.
package com.bank.dsa;
public class LedgerCompactor {
// Remove zero-balance entries in place
public static int removeZeros(int[] balances) {
int write = 0;
for (int read = 0; read < balances.length; read++) {
if (balances[read] != 0) {
balances[write] = balances[read];
write++;
}
}
return write; // new logical length
}
public static void main(String[] args) {
int[] balances = {500, 0, 300, 0, 0, 200};
int newLen = removeZeros(balances);
for (int i = 0; i < newLen; i++) {
System.out.print(balances[i] + " ");
}
}
}
500 300 200
How does the fast/slow variant work?
One pointer advances one step at a time, the other advances two steps. In a linked list, if there is a cycle the fast pointer eventually laps the slow pointer and they meet. If there is no cycle, the fast pointer reaches the end. This also finds the midpoint: when fast reaches the end, slow is at the middle.
package com.bank.dsa;
public class LinkedListCycleDetector {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public static boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
public static ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // midpoint
}
}
What are the preconditions for each variant?
Each variant has a precondition that must hold for the approach to be correct.
| Variant | Precondition | Violation Consequence |
|---|---|---|
| Opposite-end | Sorted input | Silently wrong answers |
| Same-direction | Forward-only processing | Missed elements |
| Fast/slow | Deterministic advancement | Infinite loop or wrong midpoint |
// Wrong: opposite-end on unsorted data
int[] unsorted = {7, 2, 5, 1};
// Pair sum search would give wrong results
// because moving left/right relies on ordering
When should you use each variant?
The choice depends on the problem structure.
- Opposite-end: pair sum, 3Sum, container with most water, palindrome check.
- Same-direction: remove duplicates, remove element, merge sorted arrays, partition.
- Fast/slow: linked list cycle, middle of linked list, happy number detection.
// Decision guide:
// Q: Is data sorted and looking for pairs?
// YES --> opposite-end
// Q: Need in-place compaction or partitioning?
// YES --> same-direction
// Q: Linked list cycle or midpoint?
// YES --> fast/slow
What are common mistakes?
The most common mistake is applying opposite-end pointers to unsorted data, which silently gives wrong answers. Another is confusing same-direction with fast/slow: same-direction has both pointers under different rules, while fast/slow has a fixed 2:1 speed ratio.
// Wrong: opposite-end on unsorted data for pair sum
int[] unsorted = {5, 1, 3, 7};
int left = 0, right = 3;
// Moving based on sum comparison is meaningless without order
// Correct: sort first, then apply opposite-end
Arrays.sort(unsorted); // [1, 3, 5, 7]
// Now opposite-end works correctly
What should a senior engineer know?
A senior engineer knows all three variants and their preconditions, can pick the right one for a given problem in seconds, and explains why the chosen variant is correct. They know that opposite-end requires sorting, same-direction requires forward-only logic, and fast/slow requires a structure that supports deterministic traversal. They also know that two pointers can combine with other techniques (e.g., 3Sum combines opposite-end with a fixed-element outer loop).
Visual Overview
Three Two-Pointer Variants:
1. Opposite-End (sorted data):
[1, 3, 5, 7, 9]
L R
L--> <--R
Move based on sum comparison
2. Same-Direction (compaction):
[5, 0, 3, 0, 2]
W
R
R scans all; W advances only for non-zero
Result: [5, 3, 2, -, -]
3. Fast/Slow (cycle detection):
A -> B -> C -> D -> E
^ |
|_________|
slow: A -> B -> C -> D
fast: A -> C -> E -> D -> C
Meet at C: cycle detected
Decision Tree:
┌──────────────────────┐
│ Problem type? │
├──────────┬───────────┤
│ Pair sum │ Compact │ Cycle/Mid
│ (sorted) │ (forward) │ (linked list)
├──────────┼───────────┼───────────┤
│Opposite │Same-dir │Fast/slow │
│end │ │ │
└──────────┴───────────┴───────────┘
Key Takeaway
The two pointers technique uses two index variables that traverse a data structure together to reduce a quadratic brute-force solution to a single linear pass with constant extra space. There are three variants I reach for. The opposite-end variant starts one pointer at each end of sorted data and moves them inward based on a comparison, ideal for pair sum and container problems. The same-direction variant uses a slow write pointer and a fast read pointer for in-place compaction and removal. The fast/slow variant advances one pointer twice as fast to detect cycles or find the midpoint of a linked list.
The most important thing I keep in mind is the precondition for each variant. Opposite-end almost always assumes sorted data; applying it to unsorted data gives silently wrong answers. Same-direction requires forward-only processing logic. Fast/slow requires a structure that supports deterministic step-by-step advancement.
In my banking project at the National Bank of India, I used all three in the reconciliation service. Opposite-end pointers found matching settlement amounts in a sorted ledger. Same-direction pointers compacted a ledger array by dropping cancelled zero entries in place. Fast/slow pointers jumped to the middle transaction of a linked list for a quick audit sample.
The reason this matters in banking is scale and memory. When a reconciliation batch has millions of rows, turning a nested comparison into one sweep is the difference between a job finishing in seconds and timing out, and doing it in place avoids doubling memory.
Remember one sentence: two pointers reduce O(n squared) to O(n) by making a coordinated sweep; opposite-end for sorted pair search, same-direction for in-place compaction, fast/slow for cycle detection and midpoints.
---