Two Pointers and Sliding Window in Java
Two friends looking for each other in a long corridor don't both start at the same end. One starts at each end and they walk towards each other. And when a teacher wants the best three-day attendance streak in a month, she doesn't add up every possible three days from scratch; she slides a three-day window along the calendar, adding the new day and dropping the old one. These two everyday tricks are the two pointers and sliding window patterns. They appear in a huge share of array and string interview problems, and they turn slow nested loops into a single pass. In this lesson, you will learn both patterns and apply them to classic problems in Java.
What Are These Patterns?
The two pointers pattern in Java is a technique that is used to solve array and string problems by moving two indexes through the data, usually from both ends towards the middle, or both forward at different speeds, instead of checking every pair.
The sliding window pattern is a technique that is used to work with contiguous runs of elements (subarrays or substrings) by keeping a window between two indexes and updating its result as it slides, instead of recomputing every window from scratch.
| Pattern | Typical clue in the problem | Typical gain |
|---|---|---|
| Two pointers (from both ends) | Sorted array; pairs; palindromes; reversing | O(n²) → O(n) |
| Two pointers (same direction) | Remove duplicates in place; fast and slow | O(n²) → O(n) |
| Fixed-size window | "every k consecutive elements" | O(n × k) → O(n) |
| Variable-size window | "longest/shortest run that satisfies..." | O(n²) → O(n) |
Two Pointers: Pair with a Given Sum
In a sorted array, find two numbers that add up to a target. Start one pointer at each end. If the sum is too big, move the right pointer left (to a smaller number). If it is too small, move the left pointer right.
public class PairSum {
static int[] pairWithSum(int[] sorted, int target) {
int left = 0;
int right = sorted.length - 1;
while (left < right) {
int sum = sorted[left] + sorted[right];
System.out.println(" " + sorted[left] + " + " + sorted[right]
+ " = " + sum);
if (sum == target) {
return new int[] {sorted[left], sorted[right]};
} else if (sum > target) {
right--; // need a smaller sum
} else {
left++; // need a bigger sum
}
}
return null;
}
public static void main(String[] args) {
int[] values = {1, 3, 4, 6, 8, 11};
int[] pair = pairWithSum(values, 10);
System.out.println("pair: " + pair[0] + " and " + pair[1]);
}
} 1 + 11 = 12
1 + 8 = 9
3 + 8 = 11
3 + 6 = 9
4 + 6 = 10
pair: 4 and 6Explanation: each step moves one pointer inward, so the loop runs at most n times: O(n). Checking every pair with two nested loops would be O(n²). The trick only works because the array is sorted: moving right left is guaranteed to make the sum smaller.
Two Pointers: Palindrome Check
A palindrome reads the same forwards and backwards. Compare the first and last characters, then move both pointers inward.
public class Palindrome {
static boolean isPalindrome(String text) {
int left = 0;
int right = text.length() - 1;
while (left < right) {
char a = Character.toLowerCase(text.charAt(left));
char b = Character.toLowerCase(text.charAt(right));
if (!Character.isLetter(a)) { left++; continue; }
if (!Character.isLetter(b)) { right--; continue; }
if (a != b) return false;
left++;
right--;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("Malayalam"));
System.out.println(isPalindrome("Step on no pets!"));
System.out.println(isPalindrome("Navika"));
}
}true
true
falseExplanation: the method skips anything that isn't a letter and ignores case, so "Step on no pets!" counts as a palindrome. It uses O(1) extra memory, unlike building a reversed copy of the string.
Fixed Sliding Window: Best Three-Day Total
Find the best total marks over any 3 consecutive days. Instead of adding 3 numbers for every position, add the day that enters the window and subtract the day that leaves.
public class BestStreak {
public static void main(String[] args) {
int[] marks = {4, 7, 2, 9, 6, 1};
int k = 3;
int window = 0;
for (int i = 0; i < k; i++) {
window += marks[i]; // first window
}
int best = window, bestStart = 0;
System.out.println("days 0-2: " + window);
for (int end = k; end < marks.length; end++) {
window += marks[end] - marks[end - k]; // slide by one
int start = end - k + 1;
System.out.println("days " + start + "-" + end + ": " + window);
if (window > best) {
best = window;
bestStart = end - k + 1;
}
}
System.out.println("best: " + best + " starting at day " + bestStart);
}
}days 0-2: 13
days 1-3: 18
days 2-4: 17
days 3-5: 16
best: 18 starting at day 1Explanation: the first window is added up once. After that, each slide costs two operations no matter how large k is, so the whole scan is O(n) instead of O(n × k). The output matches the picture: 13, 18, 17, 16, with the best window starting at day 1.
Variable Sliding Window: Longest Run Without Repeats
Some problems ask for the longest (or shortest) window that satisfies a rule. Grow the window from the right; when the rule breaks, shrink it from the left until the rule holds again. A classic example is the longest substring with no repeated characters.
import java.util.HashSet;
import java.util.Set;
public class LongestUnique {
static String longestUnique(String s) {
Set<Character> inWindow = new HashSet<>();
int left = 0, bestLeft = 0, bestLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
while (inWindow.contains(c)) { // rule broken: shrink
inWindow.remove(s.charAt(left));
left++;
}
inWindow.add(c); // grow
if (right - left + 1 > bestLength) {
bestLength = right - left + 1;
bestLeft = left;
}
}
return s.substring(bestLeft, bestLeft + bestLength);
}
public static void main(String[] args) {
System.out.println(longestUnique("srihitha"));
System.out.println(longestUnique("anamaneni"));
System.out.println(longestUnique("abcabcbb"));
}
}srih
mane
abcExplanation: right moves forward one step every iteration, and left only ever moves forward too, so each character enters and leaves the window at most once: O(n) in total, even though there is a loop inside a loop.
Interview Corner
When does the two-pointer pair-sum trick fail?
On unsorted data. Either sort first (O(n log n)) or use a HashSet of values seen so far (O(n) time, O(n) memory).
How do you tell a fixed window from a variable one?
If the problem gives the window size ("every 7 days"), it is fixed. If it asks for the longest or shortest run meeting a condition, it is variable.
How do you remove duplicates from a sorted array in place?
Use a slow pointer for the next write position and a fast pointer that scans; copy only when the fast pointer finds a new value.
Practice
- Easy: Change
BestStreakto find the worst 2-day total in{4, 7, 2, 9, 6, 1}. - Harder: Write
int removeDuplicates(int[] sorted)that moves the unique values of{2, 2, 3, 5, 5, 5, 8}to the front in place and returns how many there are (answer: 4).
Key Takeaways
Was this tutorial helpful?