排序演算法與技巧

# Python - Classic Quick Sort
def quickSort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # Partition and get pivot index
        pi = partition(arr, low, high)
        
        # Recursively sort left and right
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    
    return arr

def partition(arr, low, high):
    # Choose rightmost as pivot
    pivot = arr[high]
    i = low - 1  # Smaller element index
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 3-way Quick Sort for duplicates
def quickSort3Way(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        lt, gt = partition3Way(arr, low, high)
        quickSort3Way(arr, low, lt - 1)
        quickSort3Way(arr, gt + 1, high)
    
    return arr

def partition3Way(arr, low, high):
    pivot = arr[low]
    i = low
    lt = low
    gt = high
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    return lt, gt

// Java - Quick Sort
public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    
    swap(arr, i + 1, high);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// java
// LC 75 - Sort Colors
// time = O(n), space = O(1)
// IDEA: Dutch National Flag — 3 pointers lo / i / hi.
//   Invariant:  [0, lo)  == 0   |   [lo, i) == 1   |   (hi, n-1] == 2
//   KEY TRAP: after swapping with `hi`, do NOT advance i — the value pulled
//             in from the back has not been examined yet.
public void sortColors(int[] nums) {
    int lo = 0, i = 0, hi = nums.length - 1;
    while (i <= hi) {
        if (nums[i] == 0) {
            int t = nums[lo]; nums[lo] = nums[i]; nums[i] = t;
            lo++; i++;                 // safe: nums[lo] was a 1 (already seen)
        } else if (nums[i] == 2) {
            int t = nums[hi]; nums[hi] = nums[i]; nums[i] = t;
            hi--;                      // NOTE: i stays put
        } else {
            i++;
        }
    }
}

# python
# LC 75 - Sort Colors
# time = O(n), space = O(1)
# IDEA: Dutch National Flag one-pass 3-way partition
class Solution:
    def sortColors(self, nums):
        lo, i, hi = 0, 0, len(nums) - 1
        while i <= hi:
            if nums[i] == 0:
                nums[lo], nums[i] = nums[i], nums[lo]
                lo += 1
                i += 1
            elif nums[i] == 2:
                nums[hi], nums[i] = nums[i], nums[hi]
                hi -= 1          # NOTE: do NOT advance i here
            else:
                i += 1

# Python - Merge Sort
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# In-place merge sort
def mergeSortInPlace(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        mid = (left + right) // 2
        mergeSortInPlace(arr, left, mid)
        mergeSortInPlace(arr, mid + 1, right)
        mergeInPlace(arr, left, mid, right)
    
    return arr

def mergeInPlace(arr, left, mid, right):
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]
    
    i = j = 0
    k = left
    
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1
    
    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1
    
    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1

// Java - Merge Sort
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];
    
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }
    
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }
    
    while (i < n1) {
        arr[k++] = leftArr[i++];
    }
    
    while (j < n2) {
        arr[k++] = rightArr[j++];
    }
}

// java
// LC 88 - Merge Sorted Array
// time = O(m + n), space = O(1)
// IDEA: write from the back. k = last free slot, i/j = last real elems.
//   Loop on `j` only: if nums2 is exhausted, the nums1 prefix is already in place.
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
}

# python
# LC 88 - Merge Sorted Array
# time = O(m + n), space = O(1)
# IDEA: fill nums1 from the tail so we never overwrite an unread element
class Solution:
    def merge(self, nums1, m, nums2, n):
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

# Python - Custom sorting
class Solution:
    def customSort(self, items):
        # Single key
        items.sort(key=lambda x: x[0])
        
        # Multiple keys
        items.sort(key=lambda x: (x[0], -x[1], x[2]))
        
        # Complex comparison
        def compare(item):
            # Return tuple of sort keys
            if condition:
                return (0, item.value, item.name)
            else:
                return (1, -item.priority, item.id)
        
        items.sort(key=compare)
        
        # Using functools for traditional comparison
        from functools import cmp_to_key
        
        def compare_func(a, b):
            if a < b:
                return -1
            elif a > b:
                return 1
            else:
                return 0
        
        items.sort(key=cmp_to_key(compare_func))
        
        return items

# Custom class for sorting
class CustomComparable:
    def __init__(self, value, priority):
        self.value = value
        self.priority = priority
    
    def __lt__(self, other):
        # Define less than for sorting
        if self.priority != other.priority:
            return self.priority > other.priority
        return self.value < other.value

// Java - Custom comparator
public void customSort(List<Item> items) {
    // Lambda comparator
    items.sort((a, b) -> a.value - b.value);
    
    // Multiple criteria
    items.sort((a, b) -> {
        if (a.priority != b.priority) {
            return b.priority - a.priority;  // Descending
        }
        return a.name.compareTo(b.name);    // Ascending
    });
    
    // Using Comparator methods
    items.sort(Comparator
        .comparingInt(Item::getPriority).reversed()
        .thenComparing(Item::getName));
    
    // Custom Comparator class
    items.sort(new Comparator<Item>() {
        @Override
        public int compare(Item a, Item b) {
            // Custom logic
            return customCompare(a, b);
        }
    });
}

// Comparable interface
class Item implements Comparable<Item> {
    int value;
    String name;
    
    @Override
    public int compareTo(Item other) {
        if (this.value != other.value) {
            return this.value - other.value;
        }
        return this.name.compareTo(other.name);
    }
}

# Python - Quick Select for k-th smallest
def quickSelect(arr, k):
    # Find k-th smallest (0-indexed)
    return quickSelectHelper(arr, 0, len(arr) - 1, k - 1)

def quickSelectHelper(arr, left, right, k):
    if left == right:
        return arr[left]
    
    # Random pivot for better average case
    import random
    pivot_idx = random.randint(left, right)
    pivot_idx = partition(arr, left, right, pivot_idx)
    
    if k == pivot_idx:
        return arr[k]
    elif k < pivot_idx:
        return quickSelectHelper(arr, left, pivot_idx - 1, k)
    else:
        return quickSelectHelper(arr, pivot_idx + 1, right, k)

def partition(arr, left, right, pivot_idx):
    pivot = arr[pivot_idx]
    # Move pivot to end
    arr[pivot_idx], arr[right] = arr[right], arr[pivot_idx]
    
    store_idx = left
    for i in range(left, right):
        if arr[i] < pivot:
            arr[store_idx], arr[i] = arr[i], arr[store_idx]
            store_idx += 1
    
    # Move pivot to final position
    arr[store_idx], arr[right] = arr[right], arr[store_idx]
    return store_idx

# Python - Counting Sort
def countingSort(arr, max_val=None):
    if not arr:
        return arr
    
    if max_val is None:
        max_val = max(arr)
    min_val = min(arr)
    
    # Create counting array
    range_size = max_val - min_val + 1
    count = [0] * range_size
    
    # Count occurrences
    for num in arr:
        count[num - min_val] += 1
    
    # Reconstruct sorted array
    idx = 0
    for i in range(range_size):
        while count[i] > 0:
            arr[idx] = i + min_val
            idx += 1
            count[i] -= 1
    
    return arr

# Stable counting sort
def stableCountingSort(arr):
    if not arr:
        return arr
    
    max_val = max(arr)
    min_val = min(arr)
    range_size = max_val - min_val + 1
    
    count = [0] * range_size
    output = [0] * len(arr)
    
    # Count occurrences
    for num in arr:
        count[num - min_val] += 1
    
    # Cumulative count
    for i in range(1, range_size):
        count[i] += count[i - 1]
    
    # Build output array (stable)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
    
    return output

# Python - Topological Sort (Kahn's Algorithm)
def topologicalSort(numNodes, edges):
    # Build graph and in-degree
    graph = defaultdict(list)
    in_degree = [0] * numNodes
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Queue for nodes with no dependencies
    queue = deque([i for i in range(numNodes) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check for cycle
    if len(result) != numNodes:
        return []  # Cycle detected
    
    return result

# DFS-based Topological Sort
def topologicalSortDFS(numNodes, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
    
    for i in range(numNodes):
        if i not in visited:
            dfs(i)
    
    return stack[::-1]

// java
// LC 315 - Count of Smaller Numbers After Self
// time = O(n log n), space = O(n)
// IDEA: merge sort over an INDEX array. While merging, `moved` = how many
//       right-half elements have already been emitted. Every time we emit a
//       LEFT element, exactly `moved` smaller elements sat after it → add.
public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    int[] count = new int[n];
    int[] idx = new int[n];
    for (int i = 0; i < n; i++) idx[i] = i;

    sortCount(nums, idx, new int[n], 0, n - 1, count);

    List<Integer> res = new ArrayList<>();
    for (int c : count) res.add(c);
    return res;
}

private void sortCount(int[] nums, int[] idx, int[] tmp, int lo, int hi, int[] count) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    sortCount(nums, idx, tmp, lo, mid, count);
    sortCount(nums, idx, tmp, mid + 1, hi, count);

    int i = lo, j = mid + 1, k = lo;
    int moved = 0;                          // # of right-half elems already merged
    while (i <= mid && j <= hi) {
        if (nums[idx[j]] < nums[idx[i]]) {  // strict `<` keeps the sort stable
            moved++;
            tmp[k++] = idx[j++];
        } else {
            count[idx[i]] += moved;         // <-- the whole trick
            tmp[k++] = idx[i++];
        }
    }
    while (i <= mid) { count[idx[i]] += moved; tmp[k++] = idx[i++]; }
    while (j <= hi)  { tmp[k++] = idx[j++]; }
    for (int t = lo; t <= hi; t++) idx[t] = tmp[t];
}

# python
# LC 315 - Count of Smaller Numbers After Self
# time = O(n log n), space = O(n)
# IDEA: merge sort the INDEX list; `moved` counts right-half elements already
#       emitted, which are exactly the smaller-and-to-the-right ones.
class Solution:
    def countSmaller(self, nums):
        n = len(nums)
        count = [0] * n
        idx = list(range(n))

        def sort_count(lo, hi):
            if lo >= hi:
                return
            mid = (lo + hi) // 2
            sort_count(lo, mid)
            sort_count(mid + 1, hi)

            i, j, moved, tmp = lo, mid + 1, 0, []
            while i <= mid and j <= hi:
                if nums[idx[j]] < nums[idx[i]]:   # right elem is smaller
                    moved += 1
                    tmp.append(idx[j]); j += 1
                else:
                    count[idx[i]] += moved        # <-- the whole trick
                    tmp.append(idx[i]); i += 1
            while i <= mid:
                count[idx[i]] += moved
                tmp.append(idx[i]); i += 1
            while j <= hi:
                tmp.append(idx[j]); j += 1
            idx[lo:hi + 1] = tmp

        sort_count(0, n - 1)
        return count

left = [2(i1), 5(i0)]      right = [1(i3), 6(i2)]      moved = 0
 step 1: 1 < 2   -> emit right, moved = 1
 step 2: 2 <= 6  -> emit left  , count[1] += 1   -> count[1] = 1
 step 3: 5 <= 6  -> emit left  , count[0] += 1   -> count[0] = 2 (1 came from the earlier level)
 step 4: drain right
answer = [2,1,1,0]

// java
// LC 220 - Contains Duplicate III
// time = O(n), space = O(min(n, indexDiff))
// IDEA: bucket width = valueDiff + 1, so "same bucket" == "within valueDiff".
//       Keep only the last `indexDiff` elements as a sliding window of buckets.
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    if (indexDiff <= 0 || valueDiff < 0) return false;
    long w = (long) valueDiff + 1;                 // NOTE: long, valueDiff can be MAX_VALUE
    Map<Long, Long> bucket = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        long id = bucketId(nums[i], w);
        if (bucket.containsKey(id)) return true;                                        // same bucket
        if (bucket.containsKey(id - 1) && nums[i] - bucket.get(id - 1) <= valueDiff) return true;
        if (bucket.containsKey(id + 1) && bucket.get(id + 1) - nums[i] <= valueDiff) return true;

        bucket.put(id, (long) nums[i]);            // at most 1 value per bucket in the window
        if (i >= indexDiff) bucket.remove(bucketId(nums[i - indexDiff], w));  // slide
    }
    return false;
}

// KEY TRAP: Java integer division truncates toward zero, so -1/3 == 0 == 2/3.
//           Negative values need an explicit floor.
private long bucketId(long x, long w) {
    return x < 0 ? (x + 1) / w - 1 : x / w;
}

# python
# LC 220 - Contains Duplicate III
# time = O(n), space = O(min(n, indexDiff))
# IDEA: bucket width = valueDiff + 1; check own bucket + 2 neighbours only.
#       Python's // already floors, so negatives need no special case.
class Solution:
    def containsNearbyAlmostDuplicate(self, nums, indexDiff, valueDiff):
        if indexDiff <= 0 or valueDiff < 0:
            return False
        w = valueDiff + 1
        bucket = {}
        for i, x in enumerate(nums):
            bid = x // w
            if bid in bucket:
                return True
            if bid - 1 in bucket and x - bucket[bid - 1] <= valueDiff:
                return True
            if bid + 1 in bucket and bucket[bid + 1] - x <= valueDiff:
                return True
            bucket[bid] = x
            if i >= indexDiff:                     # slide the window
                bucket.pop(nums[i - indexDiff] // w, None)
        return False

// java
// LC 354 - Russian Doll Envelopes
// time = O(n log n), space = O(n)
// IDEA: sort width ASC, height DESC on ties -> answer = LIS over heights.
//   WHY height DESC? envelopes [3,5] and [3,7] must never both be chosen.
//   With height DESC they appear as 7 then 5 (decreasing), so no increasing
//   subsequence can pick both. With height ASC you'd wrongly nest them.
public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

    int[] tails = new int[envelopes.length];   // tails[l] = min tail of an LIS of length l+1
    int len = 0;
    for (int[] e : envelopes) {
        int i = Arrays.binarySearch(tails, 0, len, e[1]);
        if (i < 0) i = -(i + 1);               // insertion point = lower_bound
        tails[i] = e[1];
        if (i == len) len++;
    }
    return len;
}

# python
# LC 354 - Russian Doll Envelopes
# time = O(n log n), space = O(n)
# IDEA: sort (w ASC, h DESC) -> strictly-increasing LIS over heights
import bisect
class Solution:
    def maxEnvelopes(self, envelopes):
        # NOTE: -e[1] is the whole trick (blocks same-width nesting)
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        tails = []
        for _, h in envelopes:
            i = bisect.bisect_left(tails, h)   # bisect_left => STRICTLY increasing
            if i == len(tails):
                tails.append(h)
            else:
                tails[i] = h
        return len(tails)

// java
// LC 406 - Queue Reconstruction by Height
// time = O(n^2) (list insert), space = O(n)
// IDEA: height DESC, k ASC. Insert person at index k — everyone already in
//       the list is taller/equal, so exactly k of them end up in front.
public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] p : people) res.add(p[1], p);
    return res.toArray(new int[0][]);
}

# python
# LC 406 - Queue Reconstruction by Height
# time = O(n^2), space = O(n)
# IDEA: sort (-h, k) then insert each person at index k
class Solution:
    def reconstructQueue(self, people):
        people.sort(key=lambda p: (-p[0], p[1]))
        res = []
        for p in people:
            res.insert(p[1], p)
        return res

// java
// LC 1048 - Longest String Chain
// time = O(n * L^2), space = O(n * L)   (L = max word length)
// IDEA: sort by length -> predecessors always come first. For each word try
//       deleting each char and look the shorter word up in the dp map.
public int longestStrChain(String[] words) {
    Arrays.sort(words, (a, b) -> a.length() - b.length());
    Map<String, Integer> dp = new HashMap<>();
    int best = 0;
    for (String w : words) {
        int cur = 1;
        for (int i = 0; i < w.length(); i++) {
            String pre = w.substring(0, i) + w.substring(i + 1);
            cur = Math.max(cur, dp.getOrDefault(pre, 0) + 1);
        }
        dp.put(w, cur);
        best = Math.max(best, cur);
    }
    return best;
}

# python
# LC 1048 - Longest String Chain
# time = O(n * L^2), space = O(n * L)
# IDEA: sort by length so predecessors are already in dp when we reach a word
class Solution:
    def longestStrChain(self, words):
        words.sort(key=len)
        dp = {}
        best = 0
        for w in words:
            cur = 1
            for i in range(len(w)):
                cur = max(cur, dp.get(w[:i] + w[i + 1:], 0) + 1)
            dp[w] = cur
            best = max(best, cur)
        return best

// java
// LC 645 - Set Mismatch
// time = O(n), space = O(1)
// IDEA: cyclic sort — send nums[i] to index nums[i]-1.
//   LOOP CONDITION: use `nums[i] != nums[nums[i]-1]` (compare VALUES), not
//   `nums[i] != i+1`. With duplicates the "home" slot is already taken, and
//   comparing values is what stops the swap loop from spinning forever.
public int[] findErrorNums(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] != nums[nums[i] - 1]) {
            int t = nums[i];
            nums[i] = nums[t - 1];
            nums[t - 1] = t;
        }
    }
    // now nums[i] should be i+1; the one that isn't gives both answers
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return new int[]{nums[i], i + 1};  // {duplicated, missing}
    }
    return new int[]{-1, -1};
}

# python
# LC 645 - Set Mismatch
# time = O(n), space = O(1)
# IDEA: cyclic sort, then scan for the index whose value is not i+1
class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        for i in range(n):
            # NOTE: compare VALUES (not nums[i] != i+1) so duplicates terminate
            while nums[i] != nums[nums[i] - 1]:
                t = nums[i]
                nums[i], nums[t - 1] = nums[t - 1], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return [nums[i], i + 1]   # [duplicated, missing]
        return [-1, -1]

online   : answer query i the moment it arrives           (must handle any order)
offline  : you have all q queries -> reorder them freely  (this template)

// java
// LC 1847 - Closest Room
// IDEA: offline. Rooms by size DESC, queries by minSize DESC; one pointer adds rooms into
//       a TreeSet as the size requirement relaxes, then floor/ceiling gives the nearest id.
// time = O(n log n + q log q + q log n), space = O(n + q)
public int[] closestRoom(int[][] rooms, int[][] queries) {
    int n = rooms.length, q = queries.length;
    Arrays.sort(rooms, (a, b) -> b[1] - a[1]);            // size descending

    Integer[] order = new Integer[q];
    for (int i = 0; i < q; i++) order[i] = i;
    // NOTE !!! sort the INDICES, not the queries — ans must go back in the caller's order
    Arrays.sort(order, (a, b) -> queries[b][1] - queries[a][1]);

    TreeSet<Integer> ids = new TreeSet<>();
    int[] ans = new int[q];
    int j = 0;

    for (int qi : order) {
        int preferred = queries[qi][0], minSize = queries[qi][1];
        while (j < n && rooms[j][1] >= minSize) ids.add(rooms[j++][0]);   // monotone: add only

        Integer lo = ids.floor(preferred), hi = ids.ceiling(preferred);
        if (lo == null && hi == null)      ans[qi] = -1;
        else if (lo == null)               ans[qi] = hi;
        else if (hi == null)               ans[qi] = lo;
        // tie -> smaller id, so `<=` favours the floor
        else ans[qi] = (preferred - lo <= hi - preferred) ? lo : hi;
    }
    return ans;
}

# python
# LC 1847 - Closest Room
# IDEA: same sweep. `ids` is kept sorted so bisect finds the two candidates around
#       `preferred`; insort keeps this to the standard library, at O(n) per insert.
# time = O(n^2 + q log q + q log n), space = O(n + q)
from bisect import bisect_left, insort

def closestRoom(rooms, queries):
    rooms = sorted(rooms, key=lambda r: -r[1])                  # size descending
    order = sorted(range(len(queries)), key=lambda i: -queries[i][1])

    ids = []
    ans = [-1] * len(queries)
    j = 0

    for qi in order:
        preferred, min_size = queries[qi]
        while j < len(rooms) and rooms[j][1] >= min_size:
            insort(ids, rooms[j][0])                            # O(n) memmove per insert
            j += 1
        if not ids:
            continue                                            # no room is big enough

        k = bisect_left(ids, preferred)
        best = None
        for cand in (ids[k - 1] if k > 0 else None, ids[k] if k < len(ids) else None):
            if cand is None:
                continue
            # strict `<` keeps the smaller id on a tie, because the floor is seen first
            if best is None or abs(cand - preferred) < abs(best - preferred):
                best = cand
        ans[qi] = best

    return ans

Problem Analysis Flowchart:

1. Need custom ordering rules?
   ├── YES → Custom Comparator
   │         ├── Multiple criteria → Tuple comparison
   │         └── Complex logic → Comparison function
   └── NO → Continue to 2

2. Dealing with dependencies?
   ├── YES → Topological Sort
   │         ├── Detect cycle → Kahn's algorithm
   │         └── Find ordering → DFS approach
   └── NO → Continue to 3

3. Working with intervals?
   ├── YES → Sort by start/end
   │         ├── Merge overlapping → Greedy merge
   │         └── Find conflicts → Sweep line
   └── NO → Continue to 4

4. Finding k-th element?
   ├── YES → Quick Select or Heap
   │         ├── One-time query → Quick select O(n)
   │         └── Multiple queries → Heap O(n log k)
   └── NO → Continue to 5

5. Limited value range?
   ├── YES → Counting/Bucket Sort
   │         ├── Integers → Counting sort
   │         └── With precision → Bucket sort
   └── NO → Use standard sorting

# Sort with multiple keys
items.sort(key=lambda x: (x[0], -x[1], x[2]))

# Sort by custom class
items.sort(key=lambda x: x.priority, reverse=True)

# Stable sort in multiple passes
items.sort(key=lambda x: x.secondary)  # First
items.sort(key=lambda x: x.primary)    # Then primary

# In-place vs new list
arr.sort()           # In-place
sorted_arr = sorted(arr)  # New list

// Lambda comparator
Arrays.sort(arr, (a, b) -> a - b);

// Method reference
Arrays.sort(arr, Integer::compare);

// Comparator chaining
Arrays.sort(items, Comparator
    .comparing(Item::getPriority)
    .thenComparing(Item::getName));

// Reverse order
Arrays.sort(arr, Collections.reverseOrder());

# python
# LC 969 Pancake Sorting
# V0
# IDEA : pankcake sort + while loop
# IDEA : 3 STEPS
#   -> step 1) Find the maximum number in arr
#   -> step 2) Reverse from 0 to max_idx
#   -> step 3) Reverse whole list
# https://github.com/yennanliu/CS_basics/blob/master/algorithm/python/pancake_sort.py
class Solution(object):
    def pancakeSort(self, arr):
        """Sort Array with Pancake Sort.
        :param arr: Collection containing comparable items
        :return: Collection ordered in ascending order of items
        Examples:
        >>> pancake_sort([0, 5, 3, 2, 2])
        [0, 2, 2, 3, 5]
        >>> pancake_sort([])
        []
        >>> pancake_sort([-2, -5, -45])
        [-45, -5, -2]
        """
        cur = len(arr)
        res = []
        while cur > 1:
            # step 1) Find the maximum number in arr
            max_idx = arr.index(max(arr[0:cur]))
            res = res + [max_idx+1, cur] # idx is 1 based
            # step 2) Reverse from 0 to max_idx
            # NOTE: `arr[:max_idx][::-1]` EXCLUDES arr[max_idx]; the commented
            #       `arr[max_idx::-1]` INCLUDES it — they are NOT equivalent.
            #       Prefer the commented form to keep the pivot element.
            #arr = arr[max_idx::-1] + arr[max_idx + 1 : len(arr)] # includes pivot
            arr = arr[:max_idx][::-1] + arr[max_idx + 1 : len(arr)]
            # step 3) Reverse whole list
            #arr = arr[cur - 1 :: -1] + arr[cur : len(arr)] # this is OK as well
            #arr = arr[:cur - 1][::-1] + arr[cur : len(arr)] # this is OK as well
            tmp = arr[::-1]
            arr = tmp
            cur -= 1
        print ("arr = " + str(arr))
        return res

# V1
# https://leetcode.com/problems/pancake-sorting/discuss/817978/Python-O(n2)-by-simulation-w-Comment
# https://leetcode.com/problems/pancake-sorting/discuss/330990/Python
class Solution:
    def pancakeSort(self, A):

        res = []

        for x in range(len(A), 1, -1):
            # Carry out pancake-sort from largest number n to smallest number 1

            # find the index of x
            i = A.index(x)

            # flip first i+1 elements to put x on A[0]
            # flip first x elements to put x on A[x-1]
            # now, x is on its corresponding position A[x-1] on ascending order
            # 
            """
            # array extend
            In [10]: x = [1,2,3]

            In [11]: x.extend([4])

            In [12]: x
            Out[12]: [1, 2, 3, 4]

            In [13]: x = [1,2,3]

            In [14]: x = x + [4]

            In [15]: x
            Out[15]: [1, 2, 3, 4]

            """
            #res.extend([i + 1, x])
            res = res + [i + 1, x]

            # update A
            """
            https://stackoverflow.com/questions/509211/understanding-slice-notation

            a[::-1]    # all items in the array, reversed
            a[1::-1]   # the first two items, reversed
            a[:-3:-1]  # the last two items, reversed
            a[-3::-1]  # everything except the last two items, reversed

            -> A[:i:-1] : last i items, reversed

            """
            A = A[:i:-1] + A[:i]
        #print ("res = " + str(res))
        return res

# V1
# IDEA : RECURSIVE
# https://leetcode.com/problems/pancake-sorting/discuss/553116/My-python-solution
# https://leetcode.com/problems/pancake-sorting/discuss/274921/PythonDetailed-Explanation-for-This-Problem
class Solution:
    def pancakeSort(self, A):
        pointer = len(A)
        result = []

        while pointer > 1:
            idx = A.index(pointer)
            result.append(idx + 1)
            A = A[idx::-1] + A[idx + 1:]
            result.append(pointer)
            A = A[pointer - 1::-1] + A[pointer:]
            pointer -= 1
            
        return result

// java
// aAlgorithm book (labu) p. 347

// record reverse op array
LinkedList<Integer> res = new LinkedList<>();

List<Integer> pancakeSort(int[] cakes){
	sort(cakes, cakes.length);
	return res;
}

// order first N pancakes
void sort(int[] cakes, int n){
	// base case
	if (n == 1) return;

	// find max index
	int maxCake = 0;
	int maxCakeIndex = 0;
	for (int i = 0; i < n; i ++){
		if (cakes[i] > maxCake){
			maxCakeIndex = i;
			maxCake = cakes[i];
		}
	}
	// after 1st flip, put max pancake to the 1st layer
	reverse(cakes, 0, maxCakeIndex);
	// record this flip
	res.add(maxCakeIndex+1);
	// 2nd flip, make max pancake to the bottom (last layer)
	reverse(cakes, 0, n-1);
	// record this flop
	res.add(n);
	// recursive call : flip the remaining pancakes
	sort(cakes, n-1);
}

/** flip arr[i..j] elements */
void reverse(int[] arr, int i, int j){
	while (i < j){
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
		i++;
		j--;
	}
}

# LC 937. Reorder Data in Log Files
# V0
# IDEA : SORT BY KEY
class Solution:
    def reorderLogFiles(self, logs):
        def f(log):
            id_, rest = log.split(" ", 1)
            """
            NOTE !!!
              2 cases:
               1) case 1: rest[0].isalpha() => sort by rest, id_
               2) case 2: rest[0] is digit =>  DO NOTHING (keep original order)

               syntax:
                 if condition:
                    return key1, key2, key3 ....
            """
            if rest[0].isalpha():
                return 0, rest, id_
            else:
                return 1, None, None
                #return 100, None, None  # since we need to put Digit-logs behind of Letter-logs, so first key should be ANY DIGIT BIGGER THAN 0 

        logs.sort(key = lambda x : f(x))
        return logs

# V1
# IDEA : SORT BY keys
# https://leetcode.com/problems/reorder-data-in-log-files/solution/
class Solution:
    def reorderLogFiles(self, logs):

        def get_key(log):
            _id, rest = log.split(" ", maxsplit=1)
            """
            NOTE !!!
              2 cases:
               1) case 1: rest[0].isalpha() => sort by rest, id_
               2) case 2: rest[0] is digit =>  DO NOTHING (keep original order)
            """
            return (0, rest, _id) if rest[0].isalpha() else (1, )

        return sorted(logs, key=get_key)

# LC 252. Meeting Rooms
# V0
class Solution:
    def canAttendMeetings(self, intervals):
        """
        NOTE this
        """
        intervals.sort(key=lambda x: x[0])
        for i in range(1, len(intervals)):
            """
            NOTE this : 
                -> we compare ntervals[i][0] and ntervals[i-1][1]
            """
            if intervals[i][0] < intervals[i-1][1]:
                return False
        return True

# LC 791. Custom Sort String
# V0
# IDEA : COUNTER
from collections import Counter
class Solution(object):
    def customSortString(self, order, s):
        s_map = Counter(s)
        res = ""
        for o in order:
            if o in s_map:
                res += (o * s_map[o])
                del s_map[o]
        for s in s_map:
            res += s * s_map[s]
        return res

# LC 658. Find K Closest Elements
# NOTE : there is also stack, binary search.. approaches
# V0'
# IDEA : SORTING
class Solution:
    def findClosestElements(self, arr, k, x):
        # Sort using custom comparator
        sorted_arr = sorted(arr, key = lambda num: abs(x - num))

        # Only take k elements
        result = []
        for i in range(k):
            result.append(sorted_arr[i])
        
        # Sort again to have output in ascending order
        return sorted(result)

# LC 179. Largest Number
# V0
# IDEA : Sorting via Custom Comparator
class compare(str):
    # __lt__ defines ">" operator in python
    def __lt__(x, y):
        return x+y > y+x

class Solution:
    def largestNumber(self, nums):
        largest = sorted([str(v) for v in nums], key=compare) 
        largest = ''.join(largest) 
        return '0' if largest[0] == '0' else largest 

# LC 567 
# V0
# IDEA : collections + sliding window
from collections import Counter
class Solution(object):
    def checkInclusion(self, s1, s2):
        if len(s1) > len(s2):
            return False   
        l = 0
        tmp = ""
        _s1 = Counter(s1)
        _s2 = Counter()     
        for i, item in enumerate(s2):
            ### NOTE : we need to append new element first, then compare
            _s2[item] += 1
            tmp = s2[l:i+1]
            if _s2 == _s1 and len(tmp) > 0:
                return True
            if len(tmp) >= len(s1):
                _s2[tmp[0]] -= 1
                if _s2[tmp[0]] == 0:
                    del _s2[tmp[0]]
                l += 1
        return False

// java
// LC 567
// V2
// IDEA : SORTING
// https://leetcode.com/problems/permutation-in-string/editorial/
public boolean checkInclusion_3(String s1, String s2) {
    s1 = sort(s1);
    for (int i = 0; i <= s2.length() - s1.length(); i++) {
        if (s1.equals(sort(s2.substring(i, i + s1.length()))))
            return true;
    }
    return false;
}

public String sort(String s) {
    char[] t = s.toCharArray();
    Arrays.sort(t);
    return new String(t);
} 

// java

// LC 853. Car Fleet

    // V0
    // IDEA: pair position and speed, sorting (gpt)
    /**
     * IDEA :
     *
     * The approach involves sorting the cars by their starting positions
     * (from farthest to nearest to the target)
     * and computing their time to reach the target.
     * We then iterate through these times to count the number of distinct fleets.
     *
     *
     *
     * Steps in the Code:
     *  1.  Pair Cars with Their Speeds:
     *      •   Combine position and speed into a 2D array cars for easier sorting and access.
     *  2.  Sort Cars by Position Descending:
     *      •   Use Arrays.sort with a custom comparator to sort cars from farthest to nearest relative to the target.
     *  3.  Calculate Arrival Times:
     *      •   Compute the time each car takes to reach the target using the formula:
     *
     *  time = (target - position) / speed
     *
     *  4.  Count Fleets:
     *      •   Iterate through the times array:
     *      •   If the current car’s arrival time is greater than the lastTime (time of the last fleet), it forms a new fleet.
     *      •   Update lastTime to the current car’s time.
     *  5.  Return Fleet Count:
     *      •   The number of distinct times that exceed lastTime corresponds to the number of fleets.
     *
     */
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        // Pair positions with speeds and `sort by position in descending order`
        // cars : [position][speed]
        int[][] cars = new int[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = speed[i];
        }

        /**
         * NOTE !!!
         *
         *  Sort by position descending (simulate the "car arriving" process
         */
        Arrays.sort(cars, (a, b) -> b[0] - a[0]); // Sort by position descending

        // Calculate arrival times
        double[] times = new double[n];
        for (int i = 0; i < n; i++) {
            times[i] = (double) (target - cars[i][0]) / cars[i][1];
        }

        // Count fleets
        int fleets = 0;
        double lastTime = 0;
        for (double time : times) {
            /**
             *  4.  Count Fleets:
             *  •   Iterate through the times array:
             *  •   If the current car’s arrival time is greater than the lastTime (time of the last fleet), it forms a new fleet.
             *  •   Update lastTime to the current car’s time.
             */
            // If current car's time is greater than the last fleet's time, it forms a new fleet
            if (time > lastTime) {
                fleets++;
                lastTime = time;
            }
        }

        return fleets;
    }

// java
// LC 1877. Minimize Maximum Pair Sum in Array
// Pattern: Greedy Pairing — Sort + Two Pointers

// Core idea:
//   1. Sort the array
//   2. Pair smallest with largest (two pointers from both ends)
//   3. Track the maximum pair sum across all pairs
//
// Why it works: pairing large+large inflates the max unnecessarily;
// pairing min+max balances every pair sum and minimizes the maximum.

public int minPairSum(int[] nums) {
    Arrays.sort(nums);
    int left = 0, right = nums.length - 1;
    int ans = 0;
    while (left < right) {
        ans = Math.max(ans, nums[left] + nums[right]);
        left++;
        right--;
    }
    return ans;
}

// java
// LC 692

// V0-1
// IDEA: Sort on map key set
public List<String> topKFrequent_0_1(String[] words, int k) {

    // IDEA: map sorting
    HashMap<String, Integer> freq = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
        freq.put(words[i], freq.getOrDefault(words[i], 0) + 1);
    }
    List<String> res = new ArrayList(freq.keySet());

    /**
     * NOTE !!!
     *
     *  we directly sort over map's keySet
     *  (with the data val, key that read from map)
     *
     *
     *  example:
     *
     *          Collections.sort(res,
     *                 (w1, w2) -> freq.get(w1).equals(freq.get(w2)) ? w1.compareTo(w2) : freq.get(w2) - freq.get(w1));
     */
    Collections.sort(res, (x, y) -> {
        int valDiff = freq.get(y) - freq.get(x); // sort on `value` bigger number first (decreasing order)
        if (valDiff == 0){
            // Sort on `key ` with `lexicographically` order (increasing order)
            //return y.length() - x.length(); // ?
            return x.compareTo(y);
        }
        return valDiff;
    });

    // get top K result
    return res.subList(0, k);
}