Sorting-based Pattern

Sorting-based Pattern

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

Logic:

• Sort the array
• Use two pointers from opposite ends

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

while left < right:
    s = nums[left] + nums[right]

    if s == target:
        return True
    elif s < target:
        left += 1
    else:
        right -= 1

return False

EXAMPLE 2: Merge Overlapping Intervals

Problem:
Given intervals, merge all overlapping intervals.

Logic:

• Sort intervals by start time
• Compare current interval with last merged interval

def merge_intervals(intervals):
if not intervals:
return []

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]

for start, end in intervals[1:]:
    last_end = merged[-1][1]

    if start <= last_end:
        merged[-1][1] = max(last_end, end)
    else:
        merged.append([start, end])

return merged

EXAMPLE 3: Find All Triplets That Sum to Zero (3Sum)

Problem:
Find all unique triplets such that a + b + c = 0.

Logic:

• Sort array
• Fix one element
• Use two pointers for remaining two

def three_sum(nums):
nums.sort()
result = []

for i in range(len(nums)):
    if i > 0 and nums[i] == nums[i - 1]:
        continue

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

    while left < right:
        total = nums[i] + nums[left] + nums[right]

        if total == 0:
            result.append([nums[i], nums[left], nums[right]])

            left += 1
            right -= 1

            while left < right and nums[left] == nums[left - 1]:
                left += 1
            while left < right and nums[right] == nums[right + 1]:
                right -= 1

        elif total < 0:
            left += 1
        else:
            right -= 1

return result

EXAMPLE 4: Check if Array Can Be Made Non-decreasing

Problem:
Check if array can become non-decreasing by modifying at most one element.

Logic:

• Sorting gives the target order
• Compare with original array

def check_possibility(nums):
sorted_nums = sorted(nums)
mismatch = 0

for i in range(len(nums)):

    if nums[i] != sorted_nums[i]:

        mismatch += 1

        if mismatch > 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, Sorting-based Pattern fits.

COMMON PITFALLS

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

SUMMARY

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