Optimizing Search via Sorting

In our last lesson, we focused on the mechanics of sorting in TypeScript, ensuring you can confidently use custom comparators for numbers and multiple keys. But sorting is more than just a way to present data neatly; it's one of the most powerful preprocessing steps in an algorithm designer's toolkit.

This lesson explores a fundamental algorithmic pattern: using sorting to replace a complicated, inefficient search with a simple and fast "structured scan." You will learn to identify problems where an initial $O(n\log n)$ investment in sorting unlocks a much faster $O(n)$ solution, dramatically improving performance over naive $O(n^2)$ approaches. This pattern is a key step in moving from brute-force thinking to efficient algorithm design.

The Core Idea: Trading $O(n^2)$ for $O(n\log n)$

Many problems, when first approached, seem to require comparing every element with every other element. Consider this simple problem: "Given an array of numbers, find if any two of them sum up to a target value."

For an array like [9, 2, 5, 1] and a target of 7, a naive approach would be to use nested loops:

• Check 9 + 2, 9 + 5, 9 + 1
• Check 2 + 5 (found it!), 2 + 1
• Check 5 + 1

This all-pairs comparison works, but its time complexity is $O(n^2)$. For an array with a million items, this is a trillion operations—far too slow.

The question we'll answer today is: what if we sort the array first? If our array becomes [1, 2, 5, 9], does that give us enough structure to avoid checking every pair? The answer is a resounding yes. By imposing order, we can make intelligent decisions and replace the nested-loop search with a single, linear pass. This "sort-then-scan" strategy typically results in an overall time complexity of $O(n\log n)$, which is vastly superior to $O(n^2)$.

Example 1: Finding Target Pairs with a Two-Pointer Scan

Let's formalize the problem of finding pairs that sum to a target. As we just discussed, the brute-force method is inefficient. Sorting the array first enables a classic and elegant solution known as the two-pointer technique.

The following resource explains how sorting the array allows for a "squeeze" approach, where one pointer starts at the beginning of the sorted array and another at the end. They then move towards each other in a structured way, eliminating vast portions of the search space with each step.

The logic you just read about is the essence of a structured scan. After sorting, we can make this powerful deduction at each step:

• If currentSum < target, we need a larger sum. Since the array is sorted, the only way to achieve this without re-checking pairs is to move the left pointer to the right (left++).
• If currentSum > target, we need a smaller sum. We must move the right pointer to the left (right--).
• If currentSum === target, we've found a pair.

This linear scan is only possible because of the order we imposed by sorting.

Example 2: Merging Overlapping Intervals

The sort-and-scan pattern is especially powerful for problems involving intervals. A common task is to merge all overlapping intervals in a list. For example, given [[1, 4], [8, 10], [3, 6]], the intervals [1, 4] and [3, 6] overlap and should be merged into [1, 6]. The final result would be [[1, 6], [8, 10]].

Without any order, this is a messy problem. You'd have to compare every interval with every other, which can get complicated. But what if we sort the intervals by their start times?

Let's watch a short video that provides excellent visual intuition for why sorting is so effective here.

As the video demonstrates, once the intervals are sorted by their start points, we only need to compare each interval with the previous merged interval. This transforms the problem from a global, all-pairs comparison into a local, sequential one.

This image shows the step-by-step process of such a scan:

Now, let's dive into a more detailed explanation and a concrete implementation.

Example 3: Exploiting Inherent Structure

Sometimes, the input is already sorted, but the operation you need to perform scrambles that order. This is a subtle variation where the principle of a structured scan still applies, but you might not need to call .sort() again.

Consider the problem: "Given a sorted array of integers (which can be negative), return an array of the squares of each number, also in sorted order."

• Input: [-4, -1, 0, 3, 10]
• Squares: [16, 1, 0, 9, 100]
• Sorted Squares: [0, 1, 9, 16, 100]

A straightforward approach is to square every number and then sort the result. This works and has a complexity of $O(n\log n)$. But can we do better? Since the original array is already sorted, can we achieve the final result in $O(n)$ time?

The key is to realize that the largest squared numbers will come from the numbers with the largest absolute values. In a sorted array, these will always be at the two ends. This insight allows us to use a two-pointer scan to build the sorted result directly.

This example shows that the "structured scan" pattern is not just about calling a sort function. It's about recognizing or creating order and then exploiting that order to process the data in a single, intelligent pass.

Conclusion

In this lesson, we established a powerful pattern for tackling a wide range of algorithmic problems. By investing in an upfront sort, we can often simplify a complex search into a linear scan.

Here are the key takeaways:

• The Pattern: For problems requiring comparisons between elements, always ask: "If I sort the data first, can I solve it in a single pass?"
• From $O(n^2)$ to $O(n\log n)$: Sorting transforms many seemingly quadratic problems into log-linear ones by replacing brute-force nested loops with a sort followed by a structured scan.
• Enabling Local Decisions: Sorting brings related items close together, allowing your algorithm to make decisions based on local, adjacent information rather than needing a global view of the entire dataset.
• Common Applications: This pattern is crucial for problems involving finding pairs, analyzing intervals, or detecting duplicates in a different way than using a hash set.

Now that we've seen how powerful sorted data can be, our next lesson will introduce one of the most famous and efficient algorithms that depends on it: binary search. We'll learn how to implement it correctly to find values in logarithmic time, a massive speedup even over the linear scans we saw today.