Skip to content
Tutorials Center
My learning

Topics

Lesson 194 of 201 ยท Data Structures and Algorithms

Problem-Solving Patterns

Learn three reusable Java patterns - two pointers, sliding window and prefix sums - and turn slow O(n squared) loops into O(n) solutions with runnable code.

After you know arrays, maps and a few sorting algorithms, a new skill matters more than any single data structure: recognizing the shape of a problem. Many interview and real-world tasks, such as "find two numbers that add up to a target", "longest stretch without a repeat" or "how many ranges sum to 10", are variations of a handful of patterns. Once you know the pattern, the code almost writes itself, and it is usually dramatically faster than the first brute-force idea.

This lesson teaches three of the most useful patterns on arrays and strings: two pointers, sliding window and prefix sums. All three share one theme: avoid recomputing work you have already done. They rely on the basics from Arrays, HashMap and the cost model from Data Structures in Java, and they pair well with Searching and Sorting Algorithms.

The idea: remove repeated work

The brute-force way to look at every pair or every sub-range is two nested loops, which takes O(nยฒ) steps. For 100,000 elements that is ten billion operations. The patterns below keep a small amount of state (two indexes, a running total, a table of sums) so each element is visited a constant number of times, giving O(n).

flowchart TD
    Q{"What does the problem ask for?"}
    Q -->|"a pair or triple in sorted data,<br/>or reversing / partitioning in place"| TP["Two pointers"]
    Q -->|"best or count of a contiguous<br/>sub-array or substring"| SW["Sliding window"]
    Q -->|"many sum queries over ranges,<br/>or sub-arrays with a target sum"| PS["Prefix sums"]
    SW -->|"values can be negative<br/>and the target is a sum"| PS

A quick decision guide: contiguous ranges point to a window, unless negative numbers break the window's growing and shrinking logic, in which case prefix sums are the safer tool.

Pattern 1: two pointers

Keep two indexes and move them according to a rule. There are two common layouts:

  • Opposite ends: left starts at the beginning, right at the end, and they move toward each other. Works when the data is sorted or symmetric.
  • Same direction (fast and slow): a read index scans every element while a write index marks where the next kept element goes. Works for in-place filtering.

Pair with a target sum in a sorted array

Given a sorted array and a target, find two numbers that add up to it. Brute force tries every pair. With two pointers, look at the sum of the two ends: if it is too small, the only way to increase it is to move left up; if it is too large, the only way to decrease it is to move right down. Each step discards one element for good, so the loop runs at most n times.

Java Two pointers on a sorted array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The palindrome check shows the same layout on a string: compare from both ends, skipping punctuation, and stop when the pointers meet.

Same direction: remove duplicates in place

For a sorted array, duplicates sit next to each other. A read pointer scans all elements, and a write pointer marks the end of the "clean" prefix. Each time read finds a value different from the last kept one, it is copied to write. No extra array is needed, so the extra memory is O(1).

Java Fast and slow pointers: in-place cleanup

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

moveZerosToEnd keeps the relative order of the non-zero values, because read and write only ever move forward.

Pattern 2: sliding window

A window is a contiguous range [start, end] of an array or string. Instead of recalculating the answer for every range from scratch, you slide the window: add the new element on the right, remove the old element on the left, and update the answer incrementally.

Fixed-size window

"What is the largest sum of any 3 consecutive days?" Compute the first window's sum once. After that, moving by one position costs one addition and one subtraction rather than re-adding k numbers. That brings the cost from O(nยทk) to O(n).

Variable-size window

For "longest substring with no repeated character" the size is not fixed. Grow the window by moving end; whenever the rule breaks, shrink from start until the window is valid again. Each index enters the window once and leaves at most once, so the total work is O(n), even though there is a loop inside the loop.

flowchart LR
    S["start = 0, end = 0<br/>empty window"] --> G["Add chars[end]<br/>to the window"]
    G --> V{"Window still valid?"}
    V -->|yes| U["Update best answer<br/>end++"]
    V -->|no| X["Remove chars[start]<br/>start++"]
    X --> V
    U --> G

The variable window grows on the right, and shrinks on the left only while the rule is broken.

Java Fixed and variable sliding windows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The shrinking logic in shortestSubarrayWithSumAtLeast only works when all numbers are positive. Removing an element from the left must always make the sum smaller. With negative numbers that guarantee disappears, and a sliding window can miss answers. Use prefix sums (next section) in that case.

Pattern 3: prefix sums

A prefix sum array stores running totals: prefix[i] is the sum of the first i elements, with prefix[0] = 0. The sum of any range from index l to r (inclusive) is then

prefix[r + 1] - prefix[l]

in constant time. You pay O(n) once to build the table and then answer each range query in O(1). If you have q queries, that is O(n + q) instead of O(nยทq).

Counting sub-arrays that sum to k

Prefix sums also solve "how many contiguous sub-arrays add up to k?", even with negative numbers. If the running total at index j is S and an earlier running total was S - k, then the elements between those two points add up to exactly k. Keep a HashMap that counts how many times each running total has appeared, and for every new total add the count of total - k to the answer.

Java Prefix sums: range queries and counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

For grids, the same idea extends to two dimensions: a 2D prefix table lets you sum any rectangle with four lookups.

Choosing and combining patterns

Clue in the problem Try
Sorted input, pair/triple, "closest to target" Two pointers (after sorting if needed)
Partition, reverse, filter or dedupe in place Same-direction two pointers
"Longest / shortest / maximum contiguous ..." with positives Sliding window
Many range-sum queries Prefix sums
Sub-array with a target sum, negatives allowed Prefix sums + HashMap
Need to know if you have seen a value HashSet / HashMap as helper

Patterns combine freely. A three-number sum problem sorts the array, fixes one number and runs a two-pointer scan for the rest: O(nยฒ) instead of O(nยณ). Counting distinct values in each window pairs a sliding window with a HashMap of counts. To check the cost of your own solution, count how many times each element can be visited, as in Data Structures in Java; if each element enters and leaves a window once, you have O(n).

Finally, always test the edges: an empty array, a single element, all elements equal, the answer at the very start or end, and negative numbers. Patterns are easy to get off by one, and a handful of quick checks catches most mistakes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What condition must hold to find a pair with a given sum using two pointers on opposite ends?

    Because the array is sorted, a sum that is too small can only be fixed by moving left up, and a sum that is too large only by moving right down. Without order that reasoning fails.
  2. 2. A sliding window solution has a while loop inside a for loop. Why is it still O(n)?

    The inner loop only advances start, which never moves backward. Over the whole run, start and end each move at most n times.
  3. 3. With prefix = {0, 5, 8, 16, 18} built from the array {5, 3, 8, 2}, what is the sum of the elements at indexes 1 to 3?

    The range sum is prefix[3 + 1] - prefix[1] = 18 - 5 = 13, which is 3 + 8 + 2.
  4. 4. Why can the shrinking sliding window not be used for "shortest sub-array with sum at least k" when the array contains negative numbers?

    The window relies on sums changing monotonically when an element is added or removed. Negative values break that, so another approach such as prefix sums is needed.

Summary

  • Patterns turn O(nยฒ) brute force into O(n) by never redoing work you have already done.
  • Two pointers work from both ends of sorted data, or as a read/write pair for in-place cleanup.
  • Sliding window keeps a running answer for a contiguous range: fixed size with add-new-drop-old, variable size with grow-then-shrink. It needs monotonic behavior, so be careful with negatives.
  • Prefix sums answer range-sum queries in O(1) after O(n) preparation, and with a HashMap count sub-arrays with a target sum.
  • Combine patterns with sorting and hash maps, and always test empty, single-element and extreme inputs.

Next: Java Cheat Sheet, a one-page summary of the syntax and APIs from this tutorial.