Sorting-based Pattern

Source: Dev.to

Overview

The Sorting-based Pattern solves problems by first sorting the data and then leveraging the sorted order to simplify logic, reduce complexity, or enable other efficient patterns like two pointers or greedy decisions. Sorting often transforms an otherwise complex problem into a structured one.

When to Use

Use this pattern when:

• Order of elements matters
• Relative comparisons are important
• Grouping or pairing is required
• You want to apply two pointers or greedy logic
• A small increase in time (sorting) enables a big simplification

Time & Space

• Sorting Time: O(N log N)
• Post‑processing: Usually O(N)
• Space Complexity: O(1) or O(N) depending on sort implementation

Core Idea

• Sort the array first
• Use the sorted property to:
  • Eliminate unnecessary comparisons
  • Make monotonic decisions
  • Detect patterns easily
  • Apply linear scans or pointer‑based techniques after sorting

Example 1: Two Sum Using Sorting

Problem: Check if there exists a pair with sum equal to a target.

Logic:

1. Sort the array.
2. Use two pointers from opposite ends.

def two_sum_sort(nums, target):
    nums.sort()
    left = 0
    right = len(nums) - 1

    while left  0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left  2:
                return False

    return True

Identification Checklist

Ask these questions:

• Does sorted order simplify decisions?
• Can sorting unlock a linear scan?
• Is relative ordering important?
• Is N log N acceptable?

If yes, the Sorting-based Pattern fits.

Common Pitfalls

• Forgetting to handle duplicates after sorting.
• Assuming a stable sort when it is not required.
• Sorting when the original order must be preserved.
• Overlooking faster non‑sorting solutions.

Summary

• Sort first, think later.
• Enables two‑pointer and greedy strategies.
• Often the key to reducing complexity.
• A must‑know foundational problem‑solving pattern.