Historical Context & Motivation
Since the dawn of computing, programmers have faced a recurring challenge: how do you efficiently find information hidden inside large collections of data? Early computer scientists quickly realized that sorting — arranging items in a predictable order — transforms messy, disorganized data into something you can reason about. Once data is sorted, you can scan through it in a single pass and answer questions that would otherwise require checking every possible combination. This two-step approach of "sort first, then scan" has become one of the most fundamental problem-solving patterns in computer science.
The central question this pattern addresses is straightforward: when you have an unsorted collection of data, how can you avoid brute-force nested loops that check every pair or combination? The answer, surprisingly often, is to sort the data first and then walk through it in a single organized pass.
Core Principles & Definitions
The sorting + scanning pattern rests on a simple but powerful insight: sorted data has structure you can exploit. When numbers are in order, neighbors are close in value, duplicates sit side by side, and you can make decisions about which direction to move. These properties let you replace expensive nested loops with elegant single-pass scans. Below are the foundational ideas you need to understand this pattern.
Sort as Preprocessing
Arrays.sort(). This reorders the data so that patterns become visible and exploitable in a subsequent pass.Linear Scan
Two-Pointer Scan
Sorting Brings Duplicates Together
Trade-off: Time vs. Simplicity
Visual Explanation — Before and After Sorting
The diagram below illustrates how sorting transforms an unsorted array into one where a simple left-to-right scan can detect duplicates. On the left, duplicate values are scattered in unpredictable positions. On the right, after sorting, identical values sit right next to each other, so a single comparison with the previous element is enough to find them.
Arrays.sort(), duplicate pairs (2,2), (5,5), and (8,8) are adjacent, making detection a simple neighbor comparison.Notice how in the unsorted version, the two 2s are in positions 1 and 3, the two 5s are in positions 0 and 5, and the two 8s are in positions 2 and 7. To find these duplicates without sorting, you would need to compare every element against every other element — that's a nested loop. After sorting, each duplicate pair sits side by side, so a single scan comparing arr[i] to arr[i-1] is all you need.
How It Works — The Two-Phase Pattern
The sorting + scanning pattern always follows the same two-phase structure. Understanding the time complexity of each phase helps you see why this approach is so effective.
Arrays.sort() uses a dual-pivot quicksort for primitives and TimSort for objects, both running in O(n log n) on average.In Java, the pattern looks like this in code. First, you call Arrays.sort(arr) to sort the array in-place. Then, you write a for loop that scans through the sorted array, making decisions based on the order you now know exists. The key insight is that after sorting, you can trust that arr[i] ≤ arr[i+1] for all valid i. This guarantee lets you make powerful deductions at each step without looking backward.
Arrays.sort() modifies the original array. If you need to preserve the original order for later use, make a copy first with int[] copy = Arrays.copyOf(arr, arr.length) before sorting.Types of Scanning Patterns
Once your data is sorted, there are several scanning strategies you can apply depending on the problem. The diagram below illustrates the three most common scan types you'll encounter.
| Scan Type | How It Works | Best For | Time After Sort |
|---|---|---|---|
| Left-to-Right | One pointer moves from index 0 to n−1, comparing each element to its neighbor | Duplicates, gaps, unique count | O(n) |
| Two-Pointer | One pointer at start, one at end; move inward based on sum or condition | Two-sum, pair matching | O(n) |
| Anchor + Runner | Outer pointer anchors; inner pointer runs forward through a group of related elements | 3Sum, group processing | O(n) per anchor |
Worked Example — Finding a Pair with a Target Sum
Let's walk through a classic problem: given an array of integers and a target sum, find whether any two elements add up to the target. We'll solve it using the sorting + two-pointer scanning pattern.
int[] arr = {8, 3, 1, 5, 7, 2} and int target = 10, determine if any two distinct elements in the array sum to the target. If so, return the pair.Arrays.sort(arr). The original array {8, 3, 1, 5, 7, 2} becomes {1, 2, 3, 5, 7, 8}. This costs O(n log n) time.{1, 2, 3, 5, 7, 8}left = 0 (pointing at 1) and right = 5 (pointing at 8). We'll move these pointers inward based on the current sum.L→1, R→8, sum = 9left to index 1.L→2, R→8, sum = 10Arrays.sort(arr); then int left = 0, right = arr.length - 1; followed by a while (left < right) loop. Inside, compute int sum = arr[left] + arr[right]; — if sum equals target, return the pair; if sum < target, increment left; if sum > target, decrement right.Strengths, Limitations & Alternatives
The sorting + scanning pattern is powerful, but it's not the right tool for every situation. Let's compare it to alternative approaches so you know when to reach for it and when to consider something else.
| Approach | Time Complexity | Space Complexity | Pros | Cons |
|---|---|---|---|---|
| Brute Force (nested loops) | O(n²) | O(1) | Simple to write; no preprocessing needed | Very slow for large arrays; doesn't scale |
| Sort + Scan | O(n log n) | O(1)* | Fast; clean logic; easy to debug | Modifies original array; loses original order |
| HashMap / HashSet | O(n) | O(n) | Fastest time complexity; preserves order | Uses extra memory; hash collisions can occur |
- Use sort + scan when: the problem involves pairs, duplicates, gaps, or proximity; when memory is constrained; when you need the solution to be easy to read and verify.
- Avoid sort + scan when: the original order matters and can't be lost; when O(n) time is strictly required; when the data is coming in as a stream and can't be stored all at once.
Connection to Advanced Patterns
The sorting + scanning pattern you've learned here is the foundation for several more advanced algorithmic techniques. As you progress in computer science, you'll see this same "impose order, then exploit it" strategy appear in increasingly sophisticated forms.
| This Lesson (Intro) | Advanced Version |
|---|---|
| Sort array, scan for pair with target sum | 3Sum / 4Sum: Sort, fix one element, then two-pointer scan for remaining pair |
| Sort to find duplicates in O(n log n) | Merge sort count inversions: Count how many pairs are out of order during the sort itself |
| Sort array of numbers and scan | Sort by custom key: Sort objects or intervals by start time, length, or other criteria, then scan |
| Two-pointer on a single sorted array | Merge two sorted arrays: Two pointers on different arrays, merging results in sorted order |
| Linear scan after sort | Binary search after sort: For repeated queries on sorted data, use O(log n) search instead of O(n) scan |
As you can see, the sorting + scanning idea doesn't stop at simple problems. The 3Sum problem, for example, uses exactly the two-pointer scan you learned here but wraps it inside an outer loop that fixes one element at a time. Interval scheduling problems sort intervals by their start or end time and then scan to find overlaps. The core intuition — sort first, then use the order — remains the same throughout all of these.
Practice Problems
Test your understanding of the sorting + scanning pattern with these five problems. Each one builds on the concepts from the lesson, starting with recall and progressing to creative application.
{4, 1, 7, 1, 3, 4, 7, 7}, use the sort + scan pattern to determine how many unique values are in the array. Show the sorted array and describe each comparison your scan makes.boolean hasPairWithSum(int[] arr, int target) that uses the sort + two-pointer pattern. Then trace through its execution for arr = {11, 2, 7, 6, 3} and target = 9.{92, 68, 85, 71, 88, 95}, what is the minimum gap? Write the approach using sort + scan and find the answer.Lesson Summary
The sorting + scanning pattern is a two-phase problem-solving strategy: first, sort the data using Arrays.sort() in O(n log n) time, then scan through the sorted array in O(n) time to find your answer. The total complexity of O(n log n) dramatically beats the O(n²) brute-force alternative. Three key scanning strategies include the left-to-right scan for duplicates and gaps, the two-pointer scan for pair-finding problems, and the anchor + runner scan for group processing.
This pattern works because sorted data has exploitable structure: duplicates cluster together, neighbors differ minimally, and you can reason about direction (move left for smaller sums, right for larger). While a HashMap can sometimes achieve O(n) time, sort + scan offers simplicity, low memory overhead, and a clean foundation for advanced patterns like 3Sum, interval scheduling, and binary search. Master this pattern and you'll have a go-to strategy for a huge class of array problems.