Sorting Patterns — Comprehensive Guide

# Exchange argument sort → greedy sweep
items.sort(key=lambda x: exchange_key(x))   # proven order
result = 0
state = initial_state()
for item in items:
    state = update(state, item)              # greedy decision
    result = optimise(result, state)
return result

import heapq

def mincostToHireWorkers(quality, wage, k):
    # Sort by wage/quality ratio. At any chosen ratio r,
    # worker i's fair wage = quality[i] * r.
    workers = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])
    max_heap = []   # store -quality (max-heap)
    q_sum = 0
    result = float('inf')

    for q, w in workers:
        ratio = w / q
        heapq.heappush(max_heap, -q)
        q_sum += q
        if len(max_heap) > k:
            q_sum += heapq.heappop(max_heap)   # remove largest quality
        if len(max_heap) == k:
            result = min(result, ratio * q_sum)
    return result
# Time: O(n log n), Space: O(k)

# 1235. Maximum Profit in Job Scheduling
from bisect import bisect_right

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(endTime, startTime, profit))
    ends = [j[0] for j in jobs]
    # dp[i] = max profit using first i jobs
    dp = [0] * (len(jobs) + 1)
    for i, (end, start, p) in enumerate(jobs):
        # last job that ends <= start of this job
        j = bisect_right(ends, start)
        dp[i + 1] = max(dp[i], dp[j] + p)
    return dp[-1]
# Time: O(n log n), Space: O(n)

# 1691. Maximum Height by Stacking Cuboids
# Sort all 3 sides of each cuboid, then sort cuboids.
# dp[i] = max stack height with cuboid i on top.
def maxHeight(cuboids):
    cuboids = [sorted(c) for c in cuboids]
    cuboids.sort()
    n = len(cuboids)
    dp = [c[2] for c in cuboids]
    for i in range(n):
        for j in range(i):
            if all(cuboids[j][k] <= cuboids[i][k] for k in range(3)):
                dp[i] = max(dp[i], dp[j] + cuboids[i][2])
    return max(dp)

# 891. Sum of Subsequence Widths
# After sorting, a[i] is max in 2^i subsequences and min in 2^(n-1-i) subsequences.
def sumSubseqWidths(nums):
    MOD = 10**9 + 7
    nums.sort()
    n = len(nums)
    result = 0
    pw = 1
    for i, x in enumerate(nums):
        result = (result + pw * x - pw * nums[n - 1 - i]) % MOD
        pw = pw * 2 % MOD
    return result

def solve(nums, k):
    nums.sort()

    def count(mid):
        # How many [things] have value <= mid?
        # Two-pointer scan in O(n) because nums is sorted
        ...

    lo, hi = min_possible, max_possible
    while lo < hi:
        mid = (lo + hi) // 2
        if count(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

from bisect import bisect_right

def smallestDistancePair(nums, k):
    nums.sort()
    n = len(nums)

    def count_pairs(mid):
        # Count pairs with distance <= mid using sliding window
        left = res = 0
        for right in range(n):
            while nums[right] - nums[left] > mid:
                left += 1
            res += right - left
        return res

    lo, hi = 0, nums[-1] - nums[0]
    while lo < hi:
        mid = (lo + hi) // 2
        if count_pairs(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo
# Time: O(n log n + n log W) where W = max - min

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (negate values): lower half
        self.hi = []   # min-heap: upper half

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

# 1851. Minimum Interval to Include Each Query
def minInterval(intervals, queries):
    intervals.sort()
    indexed_queries = sorted(enumerate(queries), key=lambda x: x[1])
    result = [-1] * len(queries)
    heap = []   # (size, right_end)
    i = 0

    for qi, q in indexed_queries:
        # Activate all intervals whose left <= q
        while i < len(intervals) and intervals[i][0] <= q:
            l, r = intervals[i]
            heapq.heappush(heap, (r - l + 1, r))
            i += 1
        # Remove expired intervals
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        if heap:
            result[qi] = heap[0][0]
    return result

# 630. Course Schedule III
def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])   # sort by deadline
    heap = []   # max-heap of durations (negate)
    time = 0
    for duration, last_day in courses:
        time += duration
        heapq.heappush(heap, -duration)
        if time > last_day:
            time += heapq.heappop(heap)   # drop the longest course
    return len(heap)

import heapq

def getSkyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h, r))   # start: negative height = active
        events.append((r, 0, 0))    # end
    events.sort()

    result = [[0, 0]]
    heap = [(0, float('inf'))]   # (neg_height, end)

    for x, neg_h, r in events:
        if neg_h:   # start event
            heapq.heappush(heap, (neg_h, r))
        # Remove expired buildings
        while heap[0][1] <= x:
            heapq.heappop(heap)
        cur_max = -heap[0][0]
        if result[-1][1] != cur_max:
            result.append([x, cur_max])
    return result[1:]

# Generic Kruskal template
parent = list(range(n))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    a, b = find(a), find(b)
    if a == b: return False
    parent[a] = b
    return True

edges.sort(key=lambda e: e[2])   # sort by weight
mst_cost = 0
for u, v, w in edges:
    if union(u, v):
        mst_cost += w

def distanceLimitedPathsExist(n, edgeList, queries):
    edgeList.sort(key=lambda e: e[2])
    # Attach original index to queries before sorting
    queries = sorted(enumerate(queries), key=lambda x: x[1][2])
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x

    result = [False] * len(queries)
    ei = 0
    for qi, (u, v, limit) in queries:
        while ei < len(edgeList) and edgeList[ei][2] < limit:
            a, b, _ = edgeList[ei]
            ra, rb = find(a), find(b)
            if ra != rb: parent[ra] = rb
            ei += 1
        result[qi] = find(u) == find(v)
    return result

# Sort all cells by value. For each cell (r,c,v), dp[r][c] = 
# 1 + max dp over cells in same row/col with smaller value.
# Use two segment trees (one per row, one per col) for range max queries.
from sortedcontainers import SortedList

def maxIncreasingCells(mat):
    m, n = len(mat), len(mat[0])
    from collections import defaultdict
    val_to_cells = defaultdict(list)
    for r in range(m):
        for c in range(n):
            val_to_cells[mat[r][c]].append((r, c))

    row_max = [0] * m
    col_max = [0] * n
    result = 0

    for val in sorted(val_to_cells):
        cells = val_to_cells[val]
        # Compute new dp values before updating (same value can't extend itself)
        new_dp = []
        for r, c in cells:
            dp_rc = 1 + max(row_max[r], col_max[c])
            new_dp.append(dp_rc)
            result = max(result, dp_rc)
        for (r, c), dp_rc in zip(cells, new_dp):
            row_max[r] = max(row_max[r], dp_rc)
            col_max[c] = max(col_max[c], dp_rc)
    return result
# Time: O(mn log(mn)), Space: O(mn)

# Sort indices by value (breaking ties by index) for "odd jumps."
# Monotonic stack finds, for each index, the next index in sorted order.
def oddEvenJumps(arr):
    n = len(arr)
    # next_higher[i] = smallest index j > i where arr[j] >= arr[i]
    # next_lower[i]  = smallest index j > i where arr[j] <= arr[i]

    def make_next(sorted_indices):
        result = [None] * n
        stack = []
        for i in sorted_indices:
            while stack and stack[-1] < i:
                result[stack.pop()] = i
            stack.append(i)
        return result

    sorted_by_val = sorted(range(n), key=lambda i: (arr[i], i))
    sorted_by_val_desc = sorted(range(n), key=lambda i: (-arr[i], i))

    next_higher = make_next(sorted_by_val)
    next_lower  = make_next(sorted_by_val_desc)

    # DP: odd[i] = can reach end starting with odd jump from i
    odd  = [False] * n
    even = [False] * n
    odd[-1] = even[-1] = True

    for i in range(n - 2, -1, -1):
        if next_higher[i] is not None:
            odd[i]  = even[next_higher[i]]
        if next_lower[i] is not None:
            even[i] = odd[next_lower[i]]

    return sum(odd)
# Time: O(n log n), Space: O(n)

# 296. Best Meeting Point
# Sort row coords and col coords independently, then take medians.
def minTotalDistance(grid):
    rows, cols = [], []
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c]:
                rows.append(r)
                cols.append(c)
    cols.sort()
    mid_r = rows[len(rows) // 2]
    mid_c = cols[len(cols) // 2]
    return sum(abs(r - mid_r) for r in rows) + sum(abs(c - mid_c) for c in cols)

# 899. Orderly Queue
# K=1: only cyclic rotations possible → return minimum rotation.
# K≥2: any permutation reachable (bubble-sort argument) → return sorted string.
def orderlyQueue(s, k):
    if k == 1:
        return min(s[i:] + s[:i] for i in range(len(s)))
    return ''.join(sorted(s))

# 3102. Minimize Manhattan Distances
# Manhattan distance |x1-x2| + |y1-y2| = Chebyshev max(|u1-u2|, |v1-v2|)
# where u = x+y, v = x-y.
# After transform, minimize max(|u1-u2|, |v1-v2|) → just sort u and v separately.
def minimumDistance(points):
    from sortedcontainers import SortedList
    us = SortedList(x + y for x, y in points)
    vs = SortedList(x - y for x, y in points)
    result = float('inf')
    for x, y in points:
        u, v = x + y, x - y
        us.remove(u); vs.remove(v)
        result = min(result, max(us[-1]-us[0], vs[-1]-vs[0]))
        us.add(u); vs.add(v)
    return result

# 2459. Sort Array by Moving Items to Empty Space
# Count cycles in the permutation. Minimum swaps = n - num_cycles.
# (Special case if 0 is in a cycle.)
def sortArray(nums):
    def count_swaps(arr, target):
        visited = [False] * len(arr)
        pos = {v: i for i, v in enumerate(arr)}
        swaps = 0
        for i in range(len(arr)):
            if not visited[i] and arr[i] != target[i]:
                cycle = 0
                j = i
                while not visited[j]:
                    visited[j] = True
                    j = pos[target[j]]
                    cycle += 1
                swaps += cycle + 1   # extra swap to move 0 in
        return swaps
    n = len(nums)
    return min(count_swaps(nums, list(range(n))),
               count_swaps(nums, list(range(1, n)) + [0]))

from bisect import bisect_left

def maxEnvelopes(envelopes):
    envelopes.sort(key=lambda x: (x[0], -x[1]))   # width asc, height desc
    # LIS on heights using patience sorting (O(n log n))
    tails = []
    for _, h in envelopes:
        pos = bisect_left(tails, h)
        if pos == len(tails):
            tails.append(h)
        else:
            tails[pos] = h
    return len(tails)
# Time: O(n log n), Space: O(n)

from bisect import bisect_left

def lengthOfLIS(nums):
    tails = []   # tails[i] = smallest tail of all IS of length i+1
    for x in nums:
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)