Introduction

When a problem asks for an O(N log N) algorithm, it usually means you need to replace repeated linear work with sorting, binary search, or an ordered data structure. The general pattern is to pay one sorting cost up front and then answer each remaining question in logarithmic or constant time.

A Concrete O(N log N) Example

Consider this representative problem: given an integer array and a value k, count how many pairs satisfy the condition that arr[j] - arr[i] <= k for i < j.

A naive double loop checks every pair and runs in O(N^2). That is often too slow for large input sizes.

The usual O(N log N) approach is:

1. sort the array once
2. for each position, find the rightmost valid partner with binary search
3. add the number of matching elements in that range

1from bisect import bisect_right
2
3
4def count_pairs(arr, k):
5    arr = sorted(arr)
6    total = 0
7
8    for i, value in enumerate(arr):
9        right = bisect_right(arr, value + k)
10        total += max(0, right - i - 1)
11
12    return total
13
14
15print(count_pairs([1, 4, 6, 8, 10], 3))

The sort costs O(N log N), and each binary search costs O(log N), repeated N times. The total remains O(N log N).

Why Sorting Changes the Problem

Without sorting, every element has to compare itself against many unrelated positions. After sorting, valid partners for a fixed value appear in one contiguous block. That property is what makes binary search useful.

This is the main lesson behind many O(N log N) designs:

• sort the data into a structure with useful order
• exploit that order to avoid repeated scanning

Once the input is ordered, many boundary queries become cheap.

Two-Pointer Variant After Sorting

Some problems that look like they need binary search can be solved with two pointers after sorting. The post-sort scan is linear, so sorting still dominates the complexity.

1def count_pairs_two_pointer(arr, k):
2    arr.sort()
3    total = 0
4    left = 0
5
6    for right in range(len(arr)):
7        while arr[right] - arr[left] > k:
8            left += 1
9        total += right - left
10
11    return total
12
13
14print(count_pairs_two_pointer([1, 4, 6, 8, 10], 3))

This is often easier to reason about once you notice that the valid window only moves forward.

Recognizing O(N log N) Opportunities

Several problem shapes regularly point toward this complexity class:

• counting pairs under a threshold
• nearest-greater or nearest-smaller style queries after ordering
• interval overlap checks on mostly static data
• top-k selection using heaps
• inversion counting with divide and conquer

The important habit is to ask, "what repeated work can be replaced by one ordered view of the data?"

Sometimes the answer is sorting plus binary search. Sometimes it is a heap or balanced tree. The underlying idea is the same: avoid recomputing structure inside every iteration.

Watch for Hidden Linear Work

Many solutions are labeled O(N log N) but quietly contain a linear operation inside the loop. That destroys the complexity claim.

Examples of hidden trouble include:

• slicing large arrays inside every iteration
• deleting from the middle of a list repeatedly
• calling a function that does a full scan under the hood

A correct complexity check should examine every operation inside the repeated path, not just the obvious loop headers.

C++ Version of the Same Idea

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5long long countPairs(std::vector<int> a, int k) {
6    std::sort(a.begin(), a.end());
7    long long total = 0;
8
9    for (size_t i = 0; i < a.size(); ++i) {
10        int limit = a[i] + k;
11        auto it = std::upper_bound(a.begin(), a.end(), limit);
12        long long right = std::distance(a.begin(), it);
13        total += std::max(0LL, right - static_cast<long long>(i) - 1);
14    }
15
16    return total;
17}
18
19int main() {
20    std::cout << countPairs({1, 4, 6, 8, 10}, 3) << "\n";
21}

The language changes, but the algorithmic structure is the same: sort once, then use logarithmic boundary lookup.

Common Pitfalls

The most common pitfall is still writing nested scans and then describing the result as O(N log N) without checking the actual work. Another is forgetting that binary search requires sorted input.

Off-by-one errors are also common, especially when duplicates exist and you need the first invalid position or the last valid one. That is why functions like bisect_right and upper_bound are useful: they encode the boundary logic directly.

Finally, do not stop at the complexity target alone. A correct O(N log N) algorithm that mishandles duplicates or empty input is still wrong.

Summary

• 'O(N log N) solutions usually come from sorting or using logarithmic data structures.'
• Sort once, then reuse the ordered structure to avoid repeated linear scans.
• Binary search and two-pointer techniques are common post-sort tools.
• Check carefully for hidden linear work inside loops.
• Complexity matters, but boundary correctness and duplicate handling matter too.