Two-Pointer & Sliding Window — Use two-pointer and sliding window patterns with arrays/strings (intro) - Java

SECTION 1

Historical Context & Motivation

Imagine you need to find two numbers in a sorted list that add up to a target. The obvious approach is to check every possible pair, but that gets painfully slow as the list grows. Computer scientists faced exactly this kind of problem in the early days of algorithm design. The two-pointer technique and the sliding window pattern evolved as clever strategies to avoid wasteful repeated work when processing arrays and strings.

1960s • Sorting & Searching Foundations

Early computer scientists like Donald Knuth formalized efficient searching and sorting algorithms. The idea of exploiting sorted order to skip unnecessary comparisons laid the groundwork for pointer-based strategies.

1970s • Merge-Style Pointer Techniques

The merge step in merge sort — walking two pointers through two sorted halves — became a well-known pattern. Programmers began applying similar pointer logic to other problems on sorted data.

1980s • Sliding Window in Networking

The sliding window concept appeared in TCP/IP networking protocols, where a "window" of data packets moved through a stream. Algorithm designers borrowed this metaphor for subarray and substring problems.

2000s–Present • Competitive Programming & Interviews

Platforms like LeetCode and Codeforces popularized two-pointer and sliding window as core problem-solving patterns. Today they are considered essential skills for any aspiring software developer.

The central question these patterns address is: How can we examine all relevant sub-parts of an array or string without resorting to expensive nested loops? By maintaining just one or two index variables that move through the data in a coordinated way, we can often reduce an O(n²) brute-force solution down to O(n) — a massive improvement for large inputs.

SECTION 2

Core Principles & Definitions

Both techniques share a common philosophy: instead of checking every combination from scratch, we keep track of where we are in the array and make small, intelligent adjustments. Let's define the two patterns and their core ideas.

Two Pointers

Use two index variables (often called left and right) that start at opposite ends of a sorted array and move toward each other based on a condition. Each element is visited at most once by each pointer.

Sliding Window

Maintain a contiguous subarray (the "window") defined by a start and end index. Expand the window by advancing end and shrink it by advancing start, updating a running result as you go.

No Backtracking

In both patterns, pointers only move forward (or inward). They never jump backwards to re-examine elements. This guarantee is what keeps the total work linear — O(n) instead of O(n²).

Preconditions Matter

Two-pointer problems often require sorted input so you know which direction to adjust. Sliding window problems typically involve finding an optimal contiguous subarray or substring, where expanding/shrinking logic stays consistent.

✦

KEY TAKEAWAY

Think of it like reading a book with two bookmarks. Instead of flipping through every single page pair, you place one bookmark near the front and one near the back, then slide them toward each other based on what you find. The two-pointer pattern works like this on sorted data. The sliding window is like dragging a magnifying glass across a line of text — you see a fixed-width (or variable-width) section and slide it along, one character at a time.

SECTION 3

Visual Explanation — Two-Pointer in Action

Let's visualize the classic two-pointer approach for the "Two Sum on a Sorted Array" problem. Given the sorted array [1, 3, 5, 7, 9, 11] and a target sum of 12, we place a left pointer at the beginning and a right pointer at the end. At each step, we check the sum and decide which pointer to move.

The green L pointer starts at index 0, and the amber R pointer starts at the last index. If the current sum is too small, we move L right to increase it. If too large, we move R left to decrease it. In the best case, we find the answer on the very first check.

Notice how each pointer only moves in one direction — left always increases and right always decreases. This means the total number of pointer moves across the entire algorithm is at most n, giving us O(n) time complexity compared to the O(n²) brute-force approach of checking every pair.

SECTION 4

How It Works — Complexity Analysis

Understanding why these patterns are efficient requires a look at their time and space complexity. The key insight is that although we are searching through pairs or subarrays, the pointer movement is strictly monotonic — pointers never go backward.

BRUTE-FORCE PAIR CHECK

T(n) = n × (n − 1) / 2 ∈ O(n²)

Checking every pair in an array of length n requires roughly n²/2 comparisons. For n = 10,000, that's about 50 million operations.

TWO-POINTER TIME

T(n) = O(n)

Each pointer moves at most n steps. Since there are two pointers, the total work is at most 2n, which simplifies to O(n). For n = 10,000, that's roughly 10,000 operations — a 5,000× speedup.

SLIDING WINDOW TIME

T(n) = O(n) (each element enters and leaves the window at most once)

The end pointer advances n times total, and the start pointer also advances at most n times total. Combined, the work is at most 2n = O(n).

SPACE COMPLEXITY

S(n) = O(1)

Both patterns use only a constant number of extra variables (the pointers, a running sum, etc.), so the space overhead is O(1) — no extra arrays or data structures are needed.

💡

Why O(n) vs O(n²) Matters

If your input has 100,000 elements, an O(n²) solution does roughly 10 billion operations — that might take 10+ seconds. An O(n) solution does about 100,000 operations — finishing in under a millisecond. In competitive programming and real software, this difference is the gap between "accepted" and "time limit exceeded."

SECTION 5

Pattern Classification — Fixed vs. Variable Window

The sliding window comes in two flavors. A fixed-size window is used when the problem specifies a subarray of exactly k elements — for example, "find the maximum sum of any 3 consecutive elements." A variable-size window expands and contracts based on a condition — for example, "find the smallest subarray whose sum is at least S." Understanding which flavor to use is the first decision you make when applying this pattern.

The fixed window (top) always spans exactly k = 3 elements and slides one position at a time. The variable window (bottom) grows by advancing the end pointer and shrinks by advancing the start pointer, searching for the optimal size.

Feature	Fixed-Size Window	Variable-Size Window
Window size	Constant (k given in problem)	Changes dynamically
When to use	"Find max/min of all subarrays of size k"	"Find smallest/longest subarray with property X"
Pointer movement	Both pointers advance together, one step per iteration	`end` advances always; `start` advances only when condition is met
Typical update	Add new element, remove oldest element	Add new element; while condition holds, remove from start

Comparing fixed-size and variable-size sliding windows

SECTION 6

Worked Example — Maximum Sum Subarray of Size K

Let's walk through a complete Java implementation. The problem: given an array of integers and a number k, find the maximum sum of any k consecutive elements. We will use the fixed-size sliding window pattern.

Maximum Sum of K Consecutive Elements

1
Step 1 — Understand the Input

We have int[] arr = {4, 2, 1, 7, 8, 1, 2, 8, 1, 0} and k = 3. We need to find the largest sum among all subarrays of length 3.

Array length n = 10, window size k = 3
2
Step 2 — Compute the First Window Sum

Sum the first k elements: windowSum = arr[0] + arr[1] + arr[2] = 4 + 2 + 1 = 7. Set maxSum = 7. In Java:

int windowSum = 0; for (int i = 0; i < k; i++) { windowSum += arr[i]; } int maxSum = windowSum;
3
Step 3 — Slide the Window

For each position i from k to n−1, we add arr[i] (the new element entering the window) and subtract arr[i - k] (the element leaving the window). This avoids re-summing the entire window from scratch. In Java:

for (int i = k; i < arr.length; i++) { windowSum += arr[i] - arr[i - k]; maxSum = Math.max(maxSum, windowSum); }
4
Step 4 — Trace Through the Array

Window positions and their sums: [4,2,1]=7 → [2,1,7]=10 → [1,7,8]=16 → [7,8,1]=16 → [8,1,2]=11 → [1,2,8]=11 → [2,8,1]=11 → [8,1,0]=9. The maximum sum appears at indices [2,3,4] and [3,4,5], both giving a sum of 16.

Maximum sum = 16
5
Step 5 — Complete Method

Here is the full Java method combining all steps. Note that the time complexity is O(n) and space complexity is O(1).

public static int maxSumSubarray(int[] arr, int k) { int windowSum = 0; for (int i = 0; i < k; i++) { windowSum += arr[i]; } int maxSum = windowSum; for (int i = k; i < arr.length; i++) { windowSum += arr[i] - arr[i - k]; maxSum = Math.max(maxSum, windowSum); } return maxSum; }

SECTION 7

Strengths, Limitations & When to Use Each Pattern

Both patterns are powerful, but they are not interchangeable. Choosing the right one depends on the structure of your problem. Here's a side-by-side comparison to help you decide.

Criterion	Two-Pointer	Sliding Window
Best for	Pair-based problems on sorted data (e.g., two sum, container with most water, removing duplicates)	Contiguous subarray/substring problems (e.g., max sum, longest substring without repeats)
Precondition	Usually requires sorted input or symmetric structure	No sorting needed; works on unsorted arrays/strings
Pointer directions	Pointers move toward each other (or one chases the other)	Both pointers move in the same direction (left to right)
Limitation	Cannot handle problems requiring contiguous subarray tracking	Cannot handle pair-finding where elements are not adjacent
Time complexity	O(n) after sorting; O(n log n) if sorting is required	O(n) in most cases

Two-Pointer vs. Sliding Window comparison

🧭

CHOOSING YOUR PATTERN

Here's a simple decision rule. If the problem says "find a pair" or involves comparing elements from opposite ends of sorted data, reach for two pointers. If the problem says "find a subarray" or "find a substring" of some optimal length, reach for the sliding window. It's like choosing between binoculars (two pointers scanning from both ends) and a spotlight sweeping across a stage (sliding window moving left to right).

SECTION 8

Connection to Advanced Techniques

The two-pointer and sliding window patterns you have learned here are foundational building blocks. As you tackle harder problems, you will encounter more sophisticated variations that build directly on these ideas.

Intro Technique	Advanced Extension	What Changes
Two-pointer on sorted arrays	Three-pointer (3Sum problem)	Fix one element, then use two pointers on the rest. Time: O(n²) instead of O(n³).
Fixed sliding window	Sliding window with HashMap	Track character frequencies inside the window for substring problems like "longest substring without repeating characters."
Variable sliding window	Deque-based sliding window	Use a double-ended queue to track the maximum/minimum inside the window in O(1) per step.
Two pointers moving inward	Fast & slow pointers (cycle detection)	Two pointers move at different speeds through a linked list to detect cycles (Floyd's algorithm).

From introductory to advanced pointer-based techniques

Each of these advanced techniques follows the same core philosophy: avoid redundant work by maintaining state as you traverse the data. Once you are comfortable with the basic two-pointer and sliding window patterns, adding a HashMap, a deque, or an extra pointer feels like a natural extension rather than a completely new concept.

ℹ

What to Study Next

Practice the basic versions until they feel automatic. Then try LeetCode problems like "3Sum" (two-pointer extension), "Longest Substring Without Repeating Characters" (HashMap window), and "Sliding Window Maximum" (deque window). Each one adds exactly one new idea on top of what you already know.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why the two-pointer technique only works correctly on a sorted array when searching for a pair with a given sum. What would go wrong if the array were unsorted?

Show answer

The two-pointer technique relies on the fact that moving the left pointer right increases the sum, and moving the right pointer left decreases it. This predictable behavior only holds when the array is sorted in ascending order. If the array were unsorted, moving a pointer in one direction would not guarantee a consistent increase or decrease in the sum, so you could skip valid pairs without knowing it. For unsorted arrays, you would need a different approach — like using a HashMap to store complements — to find pairs efficiently.

Question 2: BASIC CALCULATION

Given the sorted array [2, 4, 6, 8, 10, 12] and a target sum of 14, trace the two-pointer algorithm step by step. Write down the left index, right index, current sum, and the action taken at each step.

Show answer

Start with left = 0, right = 5. Step 1: arr[0] + arr[5] = 2 + 12 = 14, which equals the target — pair found at indices (0, 5). If we continue looking for more pairs: left = 1, right = 4 → 4 + 10 = 14 — another pair at (1, 4). Then left = 2, right = 3 → 6 + 8 = 14 — pair at (2, 3). Then left = 3, right = 2, so left ≥ right and we stop. The algorithm finds all three pairs in just 3 comparisons instead of the 15 that brute force would require.

Question 3: INTERMEDIATE

Write a Java method public static double maxAvgSubarray(int[] arr, int k) that returns the maximum average of any subarray of length k, using the sliding window technique. Test your logic with arr = {1, 12, -5, -6, 50, 3} and k = 4.

Show answer

The approach mirrors the max sum problem: compute the sum of the first k elements, then slide the window. Divide the max sum by k at the end. The code is:

public static double maxAvgSubarray(int[] arr, int k) { int windowSum = 0; for (int i = 0; i < k; i++) windowSum += arr[i]; int maxSum = windowSum; for (int i = k; i < arr.length; i++) { windowSum += arr[i] - arr[i - k]; maxSum = Math.max(maxSum, windowSum); } return (double) maxSum / k; }

For the test case, the window sums are: [1,12,-5,-6]=2, [12,-5,-6,50]=51, [-5,-6,50,3]=42. The maximum sum is 51, so the maximum average is 51/4 = 12.75.

Question 4: APPLIED

A weather station records daily temperatures in an array. You want to find the shortest stretch of consecutive days where the total rainfall (given in a separate array) is at least 100 mm. Write a Java method using a variable-size sliding window. Input: int[] rain = {10, 20, 30, 5, 50, 40, 10} and target = 100.

Show answer

Use a variable sliding window: expand by adding rain[end], and whenever the sum ≥ 100, try shrinking from the start. Track the minimum window length.

public static int minDaysForRain(int[] rain, int target) { int start = 0, sum = 0, minLen = Integer.MAX_VALUE; for (int end = 0; end < rain.length; end++) { sum += rain[end]; while (sum >= target) { minLen = Math.min(minLen, end - start + 1); sum -= rain[start]; start++; } } return minLen == Integer.MAX_VALUE ? -1 : minLen; }

Tracing: the window [30,5,50,40] at indices 2–5 sums to 125 ≥ 100 (length 4), then shrinks to [5,50,40]=95 < 100. The window [5,50,40,10]=105 ≥ 100 (length 4), shrinks to [50,40,10]=100 ≥ 100 (length 3), shrinks to [40,10]=50 < 100. Minimum length is 3.

Question 5: CRITICAL THINKING

Consider a problem where you need to find the longest substring of a string that contains at most 2 distinct characters. Explain which pattern you would use (two-pointer or sliding window) and why. Describe the high-level algorithm without writing full code. What data structure would you add to the basic sliding window to track the distinct characters?

Show answer

This is a variable-size sliding window problem because we are looking for the longest contiguous substring satisfying a condition. We would use a HashMap<Character, Integer> to count the frequency of each character inside the current window. The end pointer expands the window one character at a time, adding to the map. When the map contains more than 2 distinct keys, we shrink from the start — decrementing counts and removing keys that hit zero — until we are back to 2 or fewer distinct characters. At each valid state, we update the maximum length. This combines the sliding window framework with a HashMap, which is exactly the kind of extension discussed in Section 8. The time complexity remains O(n) because each character enters and leaves the window at most once, even though the HashMap operations add a small constant factor.

SUMMARY

Lesson Summary

Summary

The two-pointer pattern uses two index variables — typically starting at opposite ends of a sorted array — that move toward each other based on a comparison with the target. It reduces pair-search problems from O(n²) to O(n) by exploiting the sorted order to decide which pointer to advance. The sliding window pattern maintains a contiguous subarray defined by start and end pointers that both move left-to-right. It comes in two flavors: fixed-size (window always has k elements) and variable-size (window grows and shrinks to satisfy a condition).

Both patterns share the key principle of no backtracking — pointers only move forward, ensuring O(n) time and O(1) space. To choose between them, ask yourself: am I searching for a pair (two-pointer) or an optimal contiguous subarray or substring (sliding window)? Mastering these two patterns gives you a strong foundation for more advanced techniques like three-pointer, HashMap-based windows, and deque-based sliding window.