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

SECTION 1

Historical Context & Motivation

Imagine you have a messy pile of 500 numbered index cards and you need to find two cards that add up to a target sum. You could check every possible pair — but that would take a very long time. Now imagine those cards are already arranged in order from smallest to largest. Suddenly, the problem becomes much easier because the structure of sorted data lets you make smart decisions about where to look next.

The idea of sorting data before searching it is one of the oldest and most powerful strategies in computer science. Sorting algorithms have been studied since the 1940s, and once data is sorted, a whole family of efficient scanning techniques becomes possible. This sort-then-scan pattern is a cornerstone of algorithmic problem-solving and appears in coding interviews, competitive programming, and real-world software constantly.

1945 • Merge Sort Invented

John von Neumann develops merge sort, one of the first efficient sorting algorithms, running in O(n log n) time.

1962 • Quicksort Published

Tony Hoare publishes quicksort, which becomes the most widely used sorting algorithm in practice due to its excellent average-case performance.

1986 • Two-Pointer Technique Popularized

The two-pointer scanning technique on sorted arrays becomes a standard tool in algorithm textbooks, enabling O(n) solutions to problems that previously required O(n²).

2000s • Timsort in Python

Tim Peters creates Timsort for Python's built-in sorted() function. It combines merge sort and insertion sort and is now Python's default sort, running in O(n log n).

2010s–Now • Coding Interview Standard

The sort + scan pattern becomes one of the most frequently tested problem-solving patterns in technical interviews and competitive programming contests worldwide.

The central question this pattern addresses is: how can we transform a slow, brute-force search into a fast, structured scan by sorting the data first? By paying an upfront cost of O(n log n) to sort, we unlock scanning strategies that reduce the overall complexity from O(n²) — or worse — down to O(n log n).

SECTION 2

Core Principles & Definitions

The sort + scan pattern rests on a few simple but powerful ideas. Understanding these principles will help you recognize when this pattern applies and how to implement it correctly in Python.

Sort First

Use Python's sorted() or .sort() to arrange elements in order. This costs O(n log n) time but creates structure you can exploit.

Scan with Purpose

Walk through the sorted data using a pointer (or two pointers) that move based on comparisons. Because the data is ordered, each comparison tells you which direction to move.

Eliminate Wasted Work

In unsorted data, you often must compare every element to every other element. Sorting lets you skip large portions of the data because you know what lies ahead.

Two-Pointer Technique

Place one pointer at the start and one at the end of a sorted list. Move them toward each other based on whether the current combination is too large or too small.

Greedy Decisions on Sorted Data

When data is sorted, the next smallest (or largest) element is always immediately available. This enables greedy strategies that build solutions one step at a time.

✦

KEY TAKEAWAY

Think of sorting like alphabetizing a bookshelf. Finding a specific book on a messy shelf means checking every single one. But on an alphabetized shelf, you can jump right to the right section and scan from there. The time you spend organizing is more than repaid by the speed of every search afterward.

A key insight is that sorting is a one-time cost that unlocks repeated benefits. Whether you need to find pairs, remove duplicates, identify the closest values, or merge intervals, sorting the data first almost always makes the problem easier to think about and faster to solve.

SECTION 3

Visual Explanation — Sort Then Scan

The following diagram contrasts the brute-force approach (checking all pairs in unsorted data) with the sort + scan approach using two pointers. Notice how sorting transforms a chaotic search into a clean, directed walk through the data.

The left panel shows brute force: every pair must be checked, giving O(n²) comparisons. The right panel shows the sorted array with two pointers (L and R) that converge toward the target sum. The bottom panel traces the two-pointer walk step by step.

Notice how in the brute-force panel, lines connect every element to every other element — that's 10 checks for just 5 numbers. In the sort + scan panel, the two pointers (L and R) start at opposite ends. If the sum is too big, R moves left (toward smaller values). If the sum is too small, L moves right (toward larger values). This directional decision-making is only possible because the data is sorted. Each step eliminates an entire row or column of possibilities, which is why the scan itself runs in O(n) time.

SECTION 4

How It Works — Time Complexity Breakdown

Understanding the time complexity of this pattern helps you see why it's worth the cost of sorting. Let's break down each phase.

SORTING PHASE

T_sort = O(n log n)

Where n is the number of elements. Python's built-in sorted() uses Timsort, which guarantees O(n log n) in the worst case.

SCANNING PHASE

T_scan = O(n)

A single pass with one or two pointers visits each element at most once. Each pointer only moves forward (or inward), so the total number of pointer moves is at most n.

TOTAL COMPLEXITY

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

Since O(n log n) grows faster than O(n), the sorting phase dominates. The total is O(n log n), which is dramatically better than the brute-force O(n²) for large inputs.

To put this in perspective: for a list of 1,000,000 elements, a brute-force O(n²) approach requires about 1,000,000,000,000 operations (one trillion). The sort + scan approach needs roughly 20,000,000 operations (twenty million) — about 50,000 times faster. That's the difference between a program that runs for hours and one that finishes in under a second.

💡

When Does This Pattern Apply?

Use sort + scan when: (1) the problem involves finding pairs, triplets, or ranges; (2) the order of the original data doesn't matter for the answer; (3) you need to eliminate duplicates or compare adjacent elements. If the original order matters, this pattern may not work directly — consider making a copy first.

SECTION 5

Common Scanning Patterns on Sorted Data

Once your data is sorted, several scanning patterns become available. Each one exploits the sorted order in a different way. The diagram below illustrates the three most important patterns you'll use.

Three core scanning patterns on sorted data. Two-Pointer Inward (left) converges from both ends to find pairs. Linear Scan (center) compares adjacent elements for duplicates or closest values. Anchor + Runner (right) fixes one element and scans forward for multi-element combinations.

Pattern	When to Use	Scan Complexity
Two-Pointer Inward	Finding two elements with a target sum, or checking if a pair satisfies a condition	`O(n)`
Linear Scan	Detecting duplicates, finding the smallest gap between elements, or counting unique values	`O(n)`
Anchor + Runner	Three-sum problems, finding triplets, or grouping elements by fixing one element and scanning the rest	`O(n²)` (but better than O(n³) brute force)

Common scanning patterns and their complexities (scan phase only)

SECTION 6

Worked Example — Two Sum with Sort + Scan

Let's solve a classic problem step by step: given a list of numbers, find two numbers that add up to a target sum. We'll use the sort + two-pointer scan approach.

ℹ

Problem Statement

Given nums = [11, 2, 7, 15, 1, 8] and target = 9, find two numbers that add up to 9. Return the pair.

Sort + Two-Pointer Solution

1
Step 1 — Sort the Array

We sort the list in ascending order using Python's built-in sort. nums = sorted([11, 2, 7, 15, 1, 8]) gives us:

[1, 2, 7, 8, 11, 15]
2
Step 2 — Initialize Two Pointers

Place left = 0 (pointing at 1) and right = 5 (pointing at 15). These pointers will move inward.

L → 1, R → 15
3
Step 3 — Compare and Move

Check: 1 + 15 = 16, which is greater than 9. Since the sum is too big and the array is sorted, the only way to make the sum smaller is to move right left (toward smaller values). Now R → 11. Check: 1 + 11 = 12, still too big. Move R left again. Now R → 8. Check: 1 + 8 = 9.

1 + 8 = 9 ✓ — Match found!
4
Step 4 — Return the Result

The pair (1, 8) sums to 9. We only needed 3 comparisons instead of the 15 that brute force would require for a list of 6 elements.

return (1, 8)
5
Step 5 — Full Python Code

Here is the complete implementation:def two_sum_sorted(nums, target): nums.sort() left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return (nums[left], nums[right]) elif s < target: left += 1 else: right -= 1 return None

Time complexity: O(n log n) for sort + O(n) for scan = O(n log n) total

SECTION 7

Strengths & Limitations

Like any problem-solving pattern, sort + scan has situations where it shines and situations where other approaches might be better. Understanding these trade-offs helps you pick the right tool for each problem.

Strengths ✅	Limitations ⚠️
Reduces O(n²) brute-force problems to O(n log n)	Sorting itself costs O(n log n), which may be unnecessary if only one query is needed and a hash-based O(n) solution exists
Conceptually clean — easy to reason about correctness when data is in order	Sorting destroys the original order, so if indices from the original array are needed, you must track them separately
Works well for multiple queries on the same data — sort once, scan many times	Not useful when data arrives in a stream and you need real-time answers (you can't sort an incomplete list)
Uses O(1) extra space (if sorting in place) compared to O(n) for a hash set	For some problems (like finding a single pair), a hash map gives O(n) time without needing to sort

Sort + Scan: when to use it and when to consider alternatives

⚖️

WHEN TO CHOOSE SORT + SCAN

Think of sort + scan as the Swiss Army knife of algorithmic patterns. It's not always the absolute fastest tool for a single specific task (a dedicated tool might be faster), but it works reliably across a huge range of problems. Choose it when the problem involves relationships between elements (pairs, triplets, gaps, duplicates) and when you need a clean, bug-free solution that's easy to get right.

SECTION 8

Connection to Advanced Techniques

The sort + scan pattern is a stepping stone to more advanced algorithmic techniques. Once you're comfortable with it, you'll find that many harder problems are essentially variations of the same idea.

Intro Pattern	Advanced Extension	What Changes
Two-pointer pair finding	Three-sum / k-sum	Fix one element, then use two-pointer on the rest. Generalizes to k nested loops reduced to k−1.
Sort + linear scan	Merge intervals	Sort intervals by start time, then scan to merge overlapping ones. Used in scheduling and calendar apps.
Sort + scan for closest pair	Binary search on sorted data	Instead of scanning linearly, use binary search for O(log n) lookups. Combines sort + binary search.
Sort for greedy selection	Greedy algorithms	Many greedy algorithms start by sorting (e.g., activity selection, fractional knapsack) and then scan for optimal choices.

From basic sort + scan to advanced algorithmic patterns

As you progress in computer science, you'll encounter problems like merge intervals, three-sum, and meeting room scheduling — all of which build directly on the sort + scan foundation you've learned today. Mastering the basic pattern now means these advanced problems will feel like natural extensions rather than brand-new concepts.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why sorting a list before searching for a pair with a target sum is more efficient than checking every possible pair. What property of sorted data makes the two-pointer technique work?

Show answer

In an unsorted list, you have no information about where values are, so you must check all n × (n−1) / 2 pairs, giving O(n²) time. Once the list is sorted, you know that moving the left pointer right increases the sum, and moving the right pointer left decreases it. This directional guarantee means each pointer comparison eliminates at least one candidate, so the scan requires at most n steps. The key property is that sorted order turns random access into predictable, directed movement.

Question 2: BASIC CALCULATION

Given nums = [4, 1, 6, 3, 8] and target = 7, trace through the sort + two-pointer algorithm step by step. Write the sorted list, show each pointer position, the sum calculated, and the pointer movement at each step.

Show answer

Sorted: [1, 3, 4, 6, 8]. Start: L=0 (1), R=4 (8), sum=9 > 7 → move R left. L=0 (1), R=3 (6), sum=7 = 7 → found! The pair is (1, 6). This required only 2 comparisons. The brute-force approach would check up to 10 pairs for 5 elements. The two-pointer approach works because after sorting, we know moving R left will always decrease the sum, giving us a clear direction to adjust.

Question 3: INTERMEDIATE

Write a Python function has_duplicate(nums) that returns True if any value appears more than once in the list, using the sort + linear scan pattern. What is the time and space complexity of your solution?

Show answer

Solution: def has_duplicate(nums): nums.sort(); return any(nums[i] == nums[i-1] for i in range(1, len(nums))). After sorting, all duplicates become adjacent, so a single pass comparing each element to its neighbor is sufficient. Time complexity is O(n log n) for the sort plus O(n) for the scan, giving O(n log n) total. Space complexity is O(1) if sorting in place (ignoring Timsort's internal O(n) buffer), or O(n) if using sorted() which creates a new list. An alternative O(n) solution uses a hash set, but the sort + scan approach uses less extra memory.

Question 4: APPLIED

A teacher has a list of student test scores: [88, 72, 95, 71, 84, 90, 73, 69]. She wants to find the smallest gap between any two students' scores. Write a Python function using sort + scan to solve this, and explain why sorting makes this problem much simpler than brute force.

Show answer

Solution: def min_gap(scores): scores.sort(); return min(scores[i] - scores[i-1] for i in range(1, len(scores))). Sorted: [69, 71, 72, 73, 84, 88, 90, 95]. Adjacent differences: 2, 1, 1, 11, 4, 2, 5. Minimum gap is 1 (between 71-72 or 72-73). Without sorting, you'd compare all 28 pairs. With sorting, the closest pair must be adjacent in the sorted order (because if a < b < c, then b−a < c−a), so you only need 7 comparisons. This reduces O(n²) to O(n log n).

Question 5: CRITICAL THINKING

Consider this problem: given a list of integers, return the original indices of two elements that sum to a target. Can you still use the sort + two-pointer approach? What complication arises, and how would you handle it? Compare this to using a hash map approach.

Show answer

The complication is that sorting destroys the original indices. To handle this, you can create a list of (value, original_index) tuples, sort by value, then apply two pointers on the sorted tuples while tracking the original indices. For example: indexed = sorted(enumerate(nums), key=lambda x: x[1]). This still works in O(n log n) time but requires O(n) space for the tuples. A hash map approach (storing {value: index} as you iterate) solves it in O(n) time and O(n) space, which is technically faster. However, the sort + scan approach is still valuable because: (1) it generalizes to finding all pairs, not just one; (2) it extends naturally to three-sum; and (3) it uses less space if you don't need original indices. The best approach depends on the specific problem requirements.

SUMMARY

Lesson Summary

Summary

The sort + scan pattern is a foundational problem-solving strategy: pay an upfront O(n log n) sorting cost to unlock efficient scanning techniques that exploit sorted order. The two-pointer inward technique places pointers at both ends and converges toward a target, solving pair-finding problems in O(n) scan time. The linear scan compares adjacent elements to find duplicates or minimum gaps. The anchor + runner pattern fixes one element and scans forward for multi-element combinations like three-sum.

This pattern transforms O(n²) brute-force problems into O(n log n) solutions and is one of the most versatile tools in your Python problem-solving toolkit. Remember: when a problem involves relationships between elements — pairs, gaps, duplicates, or ranges — try sorting first and see if a clean scan emerges. Python's built-in sorted() and .sort() make the sorting step effortless, letting you focus on designing the right scan strategy.