Sorting + Scanning — Use sorting + scanning patterns (intro) - Java

SECTION 1

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.

1945 • Early Sorting on ENIAC

John von Neumann demonstrated merge sort on the ENIAC computer, proving that sorting data was one of the first essential operations in computing.

1962 • Quicksort Published

Tony Hoare published the quicksort algorithm, giving programmers a fast, practical sorting tool that could handle real-world datasets efficiently.

1973 • Two-Pointer Technique Popularized

Researchers began formalizing the idea of scanning sorted arrays with two pointers from opposite ends, unlocking efficient solutions for pair-finding problems.

1993 • Java's Arrays.sort() Introduced

Java included built-in sorting methods, making the "sort first" pattern accessible to everyday programmers without needing to implement sorting from scratch.

2010s • Coding Interviews Standardize the Pattern

Technical interviews at major companies made sorting + scanning a standard problem-solving pattern, recognizing it as a core skill for software engineers.

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.

SECTION 2

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

Before solving the actual problem, sort the array using Arrays.sort(). This reorders the data so that patterns become visible and exploitable in a subsequent pass.

Linear Scan

After sorting, walk through the array from left to right in a single pass (O(n) time). Compare each element to its neighbors or track running information to find your answer.

Two-Pointer Scan

Place one pointer at the start and another at the end of the sorted array. Move them inward based on conditions — if the sum is too small, advance the left pointer; if too large, advance the right.

Sorting Brings Duplicates Together

Sorting clusters identical values next to each other. This makes it trivial to detect, count, or skip duplicates with a single scan instead of using a hash set.

Trade-off: Time vs. Simplicity

Sorting costs O(n log n), but it often reduces the main logic from O(n²) to O(n). The total O(n log n) is a worthwhile trade-off for cleaner, faster code.

✦

KEY TAKEAWAY

Think of sorting like alphabetizing a messy pile of student papers before searching for a specific name. Without sorting, you'd have to check every single paper. After sorting, you can flip to the right section almost immediately. Sorting transforms chaos into order, and order makes scanning fast.

SECTION 3

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.

The left side shows elements scattered randomly. After 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.

SECTION 4

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.

PHASE 1 — SORTING COST

T_sort = O(n log n)

Where n is the number of elements. Java's Arrays.sort() uses a dual-pivot quicksort for primitives and TimSort for objects, both running in O(n log n) on average.

PHASE 2 — SCANNING COST

T_scan = O(n)

A single pass through the sorted array visiting each element once. Whether using a simple left-to-right scan or a two-pointer approach, each element is examined at most a constant number of times.

TOTAL TIME COMPLEXITY

T_total = O(n log n) + O(n) = O(n log n)

The sorting step dominates. Compare this to the brute-force approach of O(n²) using nested loops — for 10,000 elements, that's roughly 130,000 operations versus 100,000,000 operations.

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.

⚠

Common Gotcha

Remember that 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.

SECTION 5

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.

Three common scanning strategies after sorting: a simple left-to-right scan, a two-pointer inward scan, and an anchor + runner scan. All exploit the sorted order to avoid nested brute-force checks.

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`

Summary of scanning strategies on sorted arrays

SECTION 6

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.

ℹ

Problem Statement

Given 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.

Two-Sum with Sort + Two Pointers

1
Step 1 — Sort the Array

Call 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.

Sorted: {1, 2, 3, 5, 7, 8}
2
Step 2 — Initialize Two Pointers

Set 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 = 9
3
Step 3 — Compare Sum to Target

Sum = 1 + 8 = 9, which is less than 10. Since the array is sorted, the only way to increase the sum is to move the left pointer right (to a larger value). Move left to index 1.

L→2, R→8, sum = 10
4
Step 4 — Match Found!

Sum = 2 + 8 = 10, which equals our target. We found a valid pair. In just 2 iterations of the scan phase, we found the answer. If the sum had been too large, we would have moved the right pointer left instead.

Pair found: (2, 8) → sum = 10 ✓
5
Step 5 — Write the Java Code

Here's the complete Java implementation: Arrays.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.

Total time: O(n log n) for sort + O(n) for scan = O(n log n)

SECTION 7

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

* In-place sort; some sort implementations use O(log n) stack space

🎯

WHEN TO CHOOSE SORT + SCAN

Choose sort + scan when you want a good balance of speed and simplicity, especially when memory is limited. Think of it like organizing your locker: spending five minutes sorting everything saves you hours of searching later. If you need absolute fastest time and have memory to spare, a HashMap approach might beat it, but sort + scan is often cleaner and less error-prone.

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.

SECTION 8

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

How introductory sort + scan concepts evolve into advanced techniques

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.

SECTION 9

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.

Question 1: CONCEPTUAL

Explain why sorting an array before scanning for duplicates reduces the time complexity from O(n²) to O(n log n). What property of a sorted array makes the scan phase only O(n)?

Show answer

In an unsorted array, finding duplicates with brute force requires comparing every element to every other element using nested loops, which is O(n²). After sorting (O(n log n)), all duplicate values are guaranteed to be adjacent in the array. This means you only need to compare each element to its immediate predecessor — a single pass that takes O(n) time. The total is O(n log n) + O(n) = O(n log n), since the sort dominates. The key property is that sorted order means equal values are always neighbors.

Question 2: BASIC CALCULATION

Given the array {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.

Show answer

First, sort the array: {1, 1, 3, 4, 4, 7, 7, 7}. Start a counter at 1 (the first element is always unique). Scan from index 1 to 7, comparing each element to the previous one. Index 1: 1 == 1, skip. Index 2: 3 ≠ 1, count = 2. Index 3: 4 ≠ 3, count = 3. Index 4: 4 == 4, skip. Index 5: 7 ≠ 4, count = 4. Index 6: 7 == 7, skip. Index 7: 7 == 7, skip. The answer is 4 unique values: {1, 3, 4, 7}.

Question 3: INTERMEDIATE

Write a Java method 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.

Show answer

The method sorts the array to get {2, 3, 6, 7, 11}, then sets left = 0 and right = 4. Iteration 1: arr[0] + arr[4] = 2 + 11 = 13 > 9, so right-- (right = 3). Iteration 2: arr[0] + arr[3] = 2 + 7 = 9 == target, return true. The pair (2, 7) sums to 9. In Java:

public static boolean hasPairWithSum(int[] arr, int target) { Arrays.sort(arr); int left = 0, right = arr.length - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) return true; else if (sum < target) left++; else right--; } return false; }

The sort costs O(n log n) and the scan costs O(n), for a total of O(n log n).

Question 4: APPLIED

A teacher has an array of student test scores. She wants to find the smallest difference between any two students' scores. For example, given scores {92, 68, 85, 71, 88, 95}, what is the minimum gap? Write the approach using sort + scan and find the answer.

Show answer

Sort the scores: {68, 71, 85, 88, 92, 95}. The minimum gap between any two scores must occur between adjacent elements in a sorted array (if a and b are sorted with a < c < b, then c−a and b−c are both smaller than b−a). Scan from index 1, computing arr[i] − arr[i−1] and tracking the minimum. Gaps: 71−68=3, 85−71=14, 88−85=3, 92−88=4, 95−92=3. The minimum gap is 3, occurring between multiple pairs (68,71), (85,88), and (92,95). This runs in O(n log n) total — far better than the O(n²) brute force of checking every pair.

Question 5: CRITICAL THINKING

Consider this problem: given an array of integers, find the length of the longest consecutive sequence (e.g., in {100, 4, 200, 1, 3, 2}, the answer is 4 because of the sequence 1, 2, 3, 4). Explain how you would solve this with sort + scan. Then discuss: could a HashSet-based approach be faster? What are the trade-offs of each method?

Show answer

Sort + scan approach: Sort the array to get {1, 2, 3, 4, 100, 200}. Scan left to right, tracking the current consecutive streak. If arr[i] == arr[i−1] + 1, extend the streak. If arr[i] == arr[i−1], skip (duplicate). Otherwise, reset the streak. Track the maximum streak seen. This gives O(n log n) time and O(1) extra space. A HashSet approach adds all elements to a set, then for each element that has no predecessor (num−1 not in set), counts forward while num+1 exists. This is O(n) time but O(n) space. The trade-off is classic: sort + scan is slower but uses less memory and produces cleaner, more debuggable code. The HashSet is theoretically optimal in time but requires extra space and is more complex to implement correctly with duplicates.

SUMMARY

Lesson Summary

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.