Chương 4 - Sorting

Sort tự nó là bài toán đã giải. Chương này không dạy bạn cài đặt quicksort - Python đã có sorted() rất tốt (Timsort, O(n log n) worst, stable). Cái cần học là: khi nào sort là tiền đề giải bài, và bí mật nằm ở hàm so sánh (comparator) tuỳ biến và việc duyệt mảng đã sort bằng pattern two pointers / sweep line.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Biết khi nào sort là tiền đề: interval, lexicographic, custom order.
  • Thuộc comparator pattern (sort theo key tuple, cmp_to_key).
  • Hiểu Dutch flag 3-pointer làm việc thế nào.
  • Phân biệt khi sort làm mất index gốc và cách giữ index.

Khi nào dùng pattern này?

  • Khi đề bài có cấu trúc thứ tự (interval, time, lexicographic, …).
  • Khi sort trước làm bài “nhỏ lại” (O(n log n) chỉ là chi phí mở màn).
  • Khi cần so sánh không theo trị số tự nhiên - ví dụ “33” và “3” phải so theo cách nối chuỗi (bài 4.3 Largest Number).

3 câu hỏi vàng: 1. Sort theo khoá nào? start, end, length, freq, ratio? 2. Sort xong duyệt thế nào? one-pass / two pointers / sweep line / heap? 3. Cần stable không? Python sorted mặc định là stable - đây là tài sản quý.

Template code 

from functools import cmp_to_key
from typing import List

# 1) Sort theo khoá đơn giản
nums.sort(key=lambda x: x[0])

# 2) Sort theo nhiều khoá (tie-breaker)
nums.sort(key=lambda x: (x[0], -x[1]))    # x[0] tăng, x[1] giảm

# 3) Sort theo comparator tuỳ biến
def cmp(a, b) -> int:
    if a + b > b + a:   return -1   # a đứng trước
    if a + b < b + a:   return  1   # b đứng trước
    return 0
arr.sort(key=cmp_to_key(cmp))

# 4) Sweep line trên mảng các sự kiện
events = [(start, +1), (end, -1)]
events.sort()

Bài tự luyện cuối chương

  • LC 1859 - Sorting the Sentence
  • LC 1636 - Sort Array by Increasing Frequency
  • LC 252 - Meeting Rooms (kiểm tra có overlap)
  • LC 1235 - Maximum Profit in Job Scheduling (Chương 39)
  • LC 1996 - The Number of Weak Characters in the Game
  • LC 1366 - Rank Teams by Votes

4.1 Sort Colors / Dutch National Flag (LC 75)

Đề bài

Cho mảng nums chỉ chứa các giá trị 0, 1, 2 (đại diện cho 3 màu). Hãy sắp xếp nums sao cho cùng màu đứng cạnh nhau theo thứ tự 0 → 1 → 2. Phải làm in-place, không được dùng hàm sort của ngôn ngữ.

Ví dụ 

Input:  nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Input:  nums = [2, 0, 1]
Output: [0, 1, 2]

Ràng buộc

  • 1 <= len(nums) <= 300
  • nums[i] ∈ {0, 1, 2}
  • Follow-up: làm trong một lượt với O(1) extra space.

Clarifying questions

  • Có thể có giá trị khác {0,1,2} không? → Theo đề: không.
  • Có cho phép tạo mảng mới không? → Theo follow-up: không.

Hướng tiếp cận

Cách 1 - Counting sort 2 lượt, O(n). Đếm số lượng 0, 1, 2 rồi ghi đè lại. Đơn giản nhưng đi 2 lượt.

Cách 2 - Dutch National Flag (Edsger Dijkstra), 1 lượt, O(n).

Giữ 3 con trỏ: - lo = ranh giới phải của vùng 0s (mọi phần tử ở [0..lo-1] là 0). - hi = ranh giới trái của vùng 2s (mọi phần tử ở [hi+1..n-1] là 2). - mid = con trỏ duyệt giữa hai vùng.

Bất biến: [0..lo-1] = 0, [lo..mid-1] = 1, [mid..hi] chưa xử lý, [hi+1..n-1] = 2.

Tại mỗi bước: - nums[mid] == 0 → swap với nums[lo], lo++, mid++. - nums[mid] == 1 → đã đúng vùng, mid++. - nums[mid] == 2 → swap với nums[hi], hi-- (mid không tăng vì giá trị mới từ hi xuống chưa được xử lý).

Hình minh hoạ với nums = [2, 0, 2, 1, 1, 0]:

                  lo  mid          hi
Khởi tạo  :  [ 2,  0,  2,  1,  1,  0 ]
                ↑   ↑                ↑
              lo=0 mid=0           hi=5

mid=0: nums[0]=2 → swap(0,5), hi--
              [ 0,  0,  2,  1,  1,  2 ]
                ↑   ↑           ↑
              lo=0 mid=0      hi=4

mid=0: nums[0]=0 → swap(lo,mid)=swap(0,0), lo++, mid++
              [ 0,  0,  2,  1,  1,  2 ]
                    ↑   ↑       ↑
                  lo=1 mid=1  hi=4

mid=1: nums[1]=0 → swap(1,1), lo++, mid++
              [ 0,  0,  2,  1,  1,  2 ]
                        ↑   ↑   ↑
                       lo=2 mid=2 hi=4

mid=2: nums[2]=2 → swap(2,4), hi--
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑   ↑   ↑
                       lo=2 mid=2 hi=3

mid=2: nums[2]=1 → mid++
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑       ↑
                       lo=2 mid=3 hi=3

mid=3: nums[3]=1 → mid++
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑           ↑
                       lo=2  mid=4 hi=3   ← mid > hi → dừng

Kết quả : [0, 0, 1, 1, 2, 2]  ✓

Code Python 3 

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        lo, mid, hi = 0, 0, len(nums) - 1
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:  # nums[mid] == 2
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1
                # KHÔNG tăng mid - giá trị từ hi chưa biết là gì

Phân tích độ phức tạp

  • Thời gian: O(n) - mỗi vòng tăng mid hoặc giảm hi ít nhất 1 lần.
  • Bộ nhớ: O(1).

Bình luận

  • Bẫy thường gặp:
    • Tăng mid khi vừa swap với hi - sẽ bỏ qua phần tử vừa swap về.
    • Điều kiện vòng lặp mid < hi thay vì mid <= hi - bỏ sót xử lý ô cuối.
  • Tổng quát hoá: Đây là ý tưởng của 3-way quicksort partition. Quicksort O(n log n) về trung bình, nhưng nếu có nhiều phần tử trùng, 3-way partition tránh được trường hợp O(n²) thoái hoá.
  • Follow-up phổ biến:
    1. “Nếu có k màu (k > 3) thì sao?” → Counting sort, O(n + k).
    2. LC 215 - Kth Largest: quickselect dùng 3-way partition (Chương 17).
    3. LC 324 - Wiggle Sort II: cùng kỹ thuật 3-pointer.

Bài tự luyện liên quan

  • LC 88 - Merge Sorted Array (in-place merge).
  • LC 324 - Wiggle Sort II.
  • LC 280 - Wiggle Sort (bài 4.6).

4.2 Merge Intervals (LC 56)

Đề bài

Cho mảng các khoảng intervals[i] = [start_i, end_i]. Hãy gộp tất cả các khoảng giao nhau lại thành các khoảng không giao nhau, và trả về kết quả.

Ví dụ 

Input:  intervals = [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Giải thích: [1,3] và [2,6] giao nhau → gộp thành [1,6].

Input:  intervals = [[1,4], [4,5]]
Output: [[1,5]]
Giải thích: [1,4] và [4,5] coi là giao (chia sẻ điểm 4).

Ràng buộc

  • 1 <= len(intervals) <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

Clarifying questions

  • Hai khoảng chỉ chạm tại 1 điểm có gộp không? → Theo LC: có (như [1,4] và [4,5]).
  • Output có cần sort theo start không? → Theo LC: có (tự nhiên xuất hiện sau sort).
  • Mảng input đã sort chưa? → Không, phải tự sort.

Hướng tiếp cận

Brute force. Lặp đi lặp lại tìm cặp giao nhau và gộp. O(n²) hoặc tệ hơn.

Tối ưu - Sort + 1 lượt - O(n log n).

Sort theo start tăng dần. Sau đó duyệt, giữ last = khoảng cuối cùng đã thêm vào kết quả. Với khoảng cur tiếp theo: - Nếu cur.start <= last.end → giao nhau, mở rộng last.end = max(last.end, cur.end). - Nếu không → push cur thành khoảng mới.

Hình minh hoạ với [[1,3], [2,6], [8,10], [15,18]]:

Trục số:
   1   3   5   7   9  11  13  15  17  19
   |   |   |   |   |   |   |   |   |   |
   ├───┤                                       [1,3]
       ├──────────┤                            [2,6]
                       ├───┤                   [8,10]
                                       ├───┤   [15,18]

Sau khi sort theo start: [[1,3], [2,6], [8,10], [15,18]]

Duyệt:
  Push [1,3]                              result = [[1,3]]
  cur=[2,6], 2 <= 3 → mở rộng [1, max(3,6)] = [1,6]
                                           result = [[1,6]]
  cur=[8,10], 8 > 6 → push                result = [[1,6], [8,10]]
  cur=[15,18], 15 > 10 → push             result = [[1,6], [8,10], [15,18]]

Kết quả: [[1,6], [8,10], [15,18]]

Code Python 3 

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        result: list[list[int]] = []
        for cur in intervals:
            if result and cur[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], cur[1])
            else:
                result.append(cur[:])   # copy để khỏi share reference
        return result

Phân tích độ phức tạp

  • Thời gian: O(n log n) - chi phí chính là sort.
  • Bộ nhớ: O(n) cho output (hoặc O(log n) cho stack sort).

Bình luận

  • Bẫy thường gặp:
    • Dùng < thay vì <= khi check overlap → bỏ sót case “chạm tại điểm”.
    • Không copy cur mà result.append(cur) trực tiếp → khi sửa result[-1][1] ở vòng sau, có thể vô tình sửa luôn phần tử trong input.
  • Follow-up phổ biến:
    1. LC 57 - Insert Interval: chèn 1 khoảng vào mảng đã sort + merge (Chương 14).
    2. LC 252 / 253 - Meeting Rooms (II): đếm phòng tối đa.
    3. LC 435 - Non-overlapping Intervals: chọn số khoảng tối đa không giao nhau (greedy, Chương 16).
  • Mẹo trình bày: Trên bảng, vẽ ngay timeline trục số. Interviewer sẽ follow theo dễ hơn là chỉ đọc code.

Bài tự luyện liên quan

  • LC 57 - Insert Interval.
  • LC 252 - Meeting Rooms.
  • LC 986 - Interval List Intersections.

4.3 Largest Number (LC 179)

Đề bài

Cho mảng số nguyên không âm nums. Hãy ghép chúng (theo thứ tự nào đó) lại thành một chuỗi sao cho số tạo ra là lớn nhất. Trả về kết quả dưới dạng chuỗi (vì số có thể rất lớn).

Ví dụ 

Input:  nums = [10, 2]
Output: "210"

Input:  nums = [3, 30, 34, 5, 9]
Output: "9534330"

Input:  nums = [0, 0]
Output: "0"   (không phải "00")

Ràng buộc

  • 1 <= len(nums) <= 100
  • 0 <= nums[i] <= 10^9

Clarifying questions

  • Nếu tất cả là 0, trả "0" hay "000...0"? → "0".
  • Số 0 ở đầu hợp lệ không? → Không cho phép (trừ kết quả “0”).

Hướng tiếp cận

Brute force - thử mọi hoán vị O(n! · n). TLE khi n đủ lớn.

Tối ưu - Sort với comparator tuỳ biến - O(n log n · L) với L = độ dài tối đa.

Insight: Để quyết định a đứng trước b hay sau, chỉ cần so sánh 2 cách ghép: str(a) + str(b) vs str(b) + str(a) - chuỗi nào lớn hơn thì cách đó “tốt hơn”.

Tại sao đúng? Quan hệ “ghép nào lớn hơn” có tính bắc cầu - chứng minh chặt qua trường hợp Lexicographic của các chuỗi ghép, đảm bảo tồn tại thứ tự sort hợp lệ.

Ví dụ: a = 3, b = 30 → "330"

"303" → 3 đứng trước 30.

Code Python 3 

from functools import cmp_to_key
from typing import List

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = [str(x) for x in nums]

        def cmp(a: str, b: str) -> int:
            if a + b > b + a:   return -1   # a đứng trước
            if a + b < b + a:   return  1   # b đứng trước
            return 0

        strs.sort(key=cmp_to_key(cmp))
        result = ''.join(strs)
        # edge case: [0, 0, 0] → tránh ra "000"
        return '0' if result[0] == '0' else result

Phân tích độ phức tạp

  • Thời gian: O(n log n · L) - mỗi phép so sánh O(L), có O(n log n) lần so sánh.
  • Bộ nhớ: O(n · L) cho list chuỗi.

Bình luận

  • Bẫy thường gặp:
    • Quên xử lý case all-zero → output ra "000" thay vì "0".
    • Dùng comparator nhầm dấu (-1 / 1) - luôn test với example nhỏ.
  • Tại sao Python phải dùng cmp_to_key? Python 3 bỏ tham số cmp= trong sort() - chỉ còn key=. Khi cần comparator tuỳ biến, phải đưa qua functools.cmp_to_key() để chuyển thành “key function”.
  • Cách hay hơn (không dùng cmp_to_key)?
    • Lặp lại mỗi chuỗi đến độ dài cố định lớn rồi sort lexicographic: strs.sort(key=lambda s: s * 10, reverse=True) (vì max độ dài ~ 10).
  • Follow-up phổ biến:
    1. LC 1356 - Sort Integers by The Number of 1 Bits: cùng pattern key tuple.
    2. LC 791 - Custom Sort String (bài 4.5).

Bài tự luyện liên quan

  • LC 1356 - Sort Integers by The Number of 1 Bits.
  • LC 1636 - Sort Array by Increasing Frequency.
  • LC 451 - Sort Characters By Frequency.

4.4 Meeting Rooms II (LC 253)

Đề bài

Cho mảng các khoảng intervals[i] = [start_i, end_i] đại diện cho các cuộc họp. Tìm số phòng tối thiểu cần thiết để chứa tất cả.

(Tức là, tại mọi thời điểm, có tối đa mấy cuộc họp đang diễn ra đồng thời?)

Ví dụ 

Input:  intervals = [[0,30], [5,10], [15,20]]
Output: 2
Giải thích: tại t=5, [0,30] và [5,10] cùng diễn ra → cần 2 phòng.

Input:  intervals = [[7,10], [2,4]]
Output: 1
Giải thích: 2 cuộc họp không overlap, 1 phòng dùng được cả 2.

Ràng buộc

  • 1 <= len(intervals) <= 10^4
  • 0 <= start_i < end_i <= 10^6

Clarifying questions

  • Hai cuộc họp chạm tại 1 điểm ([1,4] và [4,5]) có overlap không? → Theo quy ước LC: không overlap (vì end là exclusive, hoặc end == start được hiểu là “ngay sau khi xong là họp mới”).
  • Phòng có thể tái sử dụng không? → Có.

Hướng tiếp cận

Có 3 cách hay, đều xứng đáng biết:

Cách 1 - Heap (priority queue) - O(n log n).

Sort theo start. Duyệt từng cuộc họp, dùng min-heap chứa end_time của các cuộc đang diễn ra. Khi cuộc mới đến (start): - Nếu heap top có end <= start → cuộc cũ đã xong → pop ra (tái dùng phòng). - Push end của cuộc mới.

Kích thước heap tại mỗi thời điểm = số phòng đang dùng → max của size là đáp án.

Cách 2 - Sweep line / Chronological - O(n log n).

Tạo 2 mảng: starts (đã sort) và ends (đã sort). Duyệt 2 con trỏ: nếu starts[i] < ends[j] → cuộc mới bắt đầu trước cuộc cũ kết thúc → cần thêm phòng (rooms++, i++); ngược lại → giải phóng (i++ thì sao đây - sai). Đúng ra: i++ khi starts[i] < ends[j] và j++ khi starts[i] >= ends[j].

Cách 3 - Event-driven, O(n log n).

Mỗi cuộc tạo 2 sự kiện: (start, +1) và (end, -1). Sort tất cả sự kiện (ưu tiên -1 trước +1 nếu cùng time → ưu tiên đóng phòng). Duyệt và giữ cur/peak.

Hình minh hoạ với [[0,30], [5,10], [15,20]] - heap-based:

Sort by start: [[0,30], [5,10], [15,20]]

Bước 1: cuộc [0,30]    heap = [30]     → rooms = 1
Bước 2: cuộc [5,10]    top=30 > 5 → giữ; push 10  heap = [10, 30]  → rooms = 2 ★
Bước 3: cuộc [15,20]   top=10 <= 15 → pop 10; push 20  heap = [20, 30] → rooms = 2

Trục số:
   0   5  10  15  20  25  30
   |   |   |   |   |   |   |
   ├───────────────────────┤    [0, 30] dùng phòng A
       ├───┤                    [5, 10] dùng phòng B
                ├───┤            [15, 20] tái dùng phòng B

Code Python 3 

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap: list[int] = []   # min-heap of end times
        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
        return len(heap)


class SolutionEvents:
    """Cách event-driven - clean cho follow-up."""

    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for s, e in intervals:
            events.append((s, +1))
            events.append((e, -1))
        # Khi cùng time: ưu tiên -1 trước +1 (cuộc kết thúc thì phòng giải phóng trước cuộc mới)
        events.sort(key=lambda x: (x[0], x[1]))

        cur = peak = 0
        for _, delta in events:
            cur += delta
            peak = max(peak, cur)
        return peak

Phân tích độ phức tạp

  • Thời gian: O(n log n).
  • Bộ nhớ: O(n).

Bình luận

  • Bẫy thường gặp:
    • Trong cách event: sort thiếu tie-breaker → khi (end == start) xử lý sai thứ tự.
    • Quên check heap[0] <= start (dấu <=)
      • nếu dùng < thì 2 cuộc kề nhau bị tính overlap.
  • Khi nào nên dùng cách nào?
    • Heap: khi cần biết phòng nào đang dùng (mở rộng dễ).
    • Events: khi cần xử lý nhiều loại sự kiện (mở/đóng/báo cáo) cùng lúc
      • pattern hay cho bài “skyline” (LC 218).
  • Follow-up phổ biến:
    1. “Tìm phòng nào dùng nhiều nhất / ít nhất?” → Heap đánh nhãn phòng.
    2. LC 218 - The Skyline Problem: cùng pattern sweep line.
    3. LC 1851 - Minimum Interval to Include Each Query.

Bài tự luyện liên quan

  • LC 252 - Meeting Rooms.
  • LC 218 - The Skyline Problem.
  • LC 759 - Employee Free Time.

4.5 Custom Sort String (LC 791)

Đề bài

Cho hai chuỗi order (toàn các ký tự phân biệt) và s. Hãy sắp xếp lại s sao cho thứ tự các ký tự xuất hiện trong order được tôn trọng. Các ký tự không nằm trong order có thể đặt ở bất cứ đâu trong kết quả.

Ví dụ 

Input:  order = "cba", s = "abcd"
Output: "cbad"
Giải thích: trong order, c < b < a. Các ký tự d không xuất hiện trong order
            nên đặt đâu cũng được.

Input:  order = "bcafg", s = "abcd"
Output: "bcad"

Ràng buộc

  • 1 <= len(order) <= 26, các ký tự trong order phân biệt.
  • 1 <= len(s) <= 200
  • Cả hai chỉ chứa chữ thường.

Clarifying questions

  • Ký tự không trong order đặt ở đâu? → Đâu cũng được. Mình quy ước đẩy về cuối cho gọn.
  • Có phân biệt hoa thường? → Theo đề: không (cả 2 chỉ chữ thường).

Hướng tiếp cận

Cách 1 - Sort với comparator theo bảng index, O(|s| log |s|).

Tạo dict priority = {ch: i for i, ch in enumerate(order)}. Mỗi ký tự không có trong order cho priority lớn vô cùng (ví dụ 26). Rồi sort s theo priority này.

Cách 2 - Counter + emit theo order, O(|s|).

Đếm Counter(s), sau đó duyệt qua từng ký tự trong order và “in ra” đúng số lần. Cuối cùng nối thêm các ký tự còn lại (không trong order).

Cách 2 không cần sort, nhanh hơn, và rất tự nhiên - interviewer thường mong đợi cách này.

Code Python 3 

from collections import Counter

class Solution:
    """Cách 2 - Counter + emit theo order."""

    def customSortString(self, order: str, s: str) -> str:
        cnt = Counter(s)
        parts: list[str] = []
        # 1. Phần các ký tự thuộc order, theo đúng thứ tự order.
        for ch in order:
            if ch in cnt:
                parts.append(ch * cnt.pop(ch))
        # 2. Các ký tự còn lại (không trong order) - thứ tự không quan trọng.
        for ch, c in cnt.items():
            parts.append(ch * c)
        return ''.join(parts)


class SolutionSort:
    """Cách 1 - comparator theo bảng index."""

    def customSortString(self, order: str, s: str) -> str:
        priority = {ch: i for i, ch in enumerate(order)}
        return ''.join(sorted(s, key=lambda ch: priority.get(ch, 26)))

Phân tích độ phức tạp

Cách Time Space
Counter O(|s| + |order|) O(1)
Sort key O(|s| log |s|) O(|s|)

Bình luận

  • Bẫy thường gặp:
    • Trong cách 1: dùng priority[ch] thay vì priority.get(ch, 26) → KeyError với ký tự không trong order.
    • Trong cách 2: dùng cnt[ch] không pop → khi duyệt phần còn lại sẽ in trùng. Nhớ dùng cnt.pop(ch).
  • Pattern “Counter + emit” rất hữu ích cho mọi bài “sắp xếp theo thứ tự cho sẵn”: thay vì sort thực sự, ta đi qua thứ tự đó và lấy phần tử ra.
  • Follow-up phổ biến:
    1. “order có thể chứa duplicate?” → Đề loại trừ, nhưng nếu có thì lấy vị trí đầu tiên.
    2. “s rất dài (10^9 ký tự)?” → Counter vẫn O(|s|), nhưng phải streaming.

Bài tự luyện liên quan

  • LC 1636 - Sort Array by Increasing Frequency.
  • LC 451 - Sort Characters By Frequency.
  • LC 1356 - Sort Integers by The Number of 1 Bits.

4.6 Wiggle Sort (LC 280)

Đề bài

Cho mảng nums. Sắp xếp lại để thoả mãn:

nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] <= ...

Tức là vị trí lẻ luôn >= vị trí kề bên trái và phải.

Ví dụ 

Input:  nums = [3, 5, 2, 1, 6, 4]
Output: [3, 5, 1, 6, 2, 4]   (một trong nhiều đáp án hợp lệ)

Input:  nums = [6, 6, 5, 6, 3, 8]
Output: [6, 6, 5, 6, 3, 8]   (đã thoả mãn)

Ràng buộc

  • 1 <= len(nums) <= 5·10^4
  • 0 <= nums[i] <= 10^4
  • Phải làm in-place.

Clarifying questions

  • Có duplicate không? → Có thể có. Quy ước <= và >= (không strict) giúp xử lý duplicate tự nhiên.
  • Có cần một đáp án xác định, hay miễn hợp lệ? → Miễn hợp lệ.

Hướng tiếp cận

Cách 1 - Sort rồi swap cặp, O(n log n). Sort tăng dần, sau đó với mỗi cặp (i, i+1) với i lẻ → swap. Bài giải đúng nhưng không tối ưu.

Cách 2 - Greedy 1 lượt, O(n).

Quan sát điều kiện: tại mỗi vị trí i, - Nếu i lẻ (1, 3, 5, …): nums[i] >= nums[i-1]. - Nếu i chẵn (2, 4, 6, …): nums[i] <= nums[i-1].

Duyệt từ i = 1, nếu vi phạm thì swap nums[i] với nums[i-1]. Tại sao swap đảm bảo không phá quan hệ trước đó? Vì ta chỉ sửa phần tử ở vị trí i-1 (làm nó nhỏ hơn hoặc lớn hơn), và quan hệ giữa nums[i-2] và nums[i-1] ở bước trước đã đảm bảo “biên” phù hợp.

Hình minh hoạ với nums = [3, 5, 2, 1, 6, 4]:

Index :   0   1   2   3   4   5
Input :  [3,  5,  2,  1,  6,  4]
            lẻ  chẵn lẻ  chẵn lẻ
            ≥   ≤    ≥   ≤    ≥

i=1 (lẻ):  cần nums[1] >= nums[0]   5 >= 3 ✓
i=2 (chẵn):cần nums[2] <= nums[1]   2 <= 5 ✓
i=3 (lẻ):  cần nums[3] >= nums[2]   1 >= 2 ✗ → swap
           [3, 5, 1, 2, 6, 4]
i=4 (chẵn):cần nums[4] <= nums[3]   6 <= 2 ✗ → swap
           [3, 5, 1, 6, 2, 4]
i=5 (lẻ):  cần nums[5] >= nums[4]   4 >= 2 ✓

Kết quả : [3, 5, 1, 6, 2, 4]  ✓

Code Python 3 

from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        for i in range(1, len(nums)):
            should_be_greater = (i % 2 == 1)
            if (should_be_greater and nums[i] < nums[i - 1]) or \
               (not should_be_greater and nums[i] > nums[i - 1]):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

Phân tích độ phức tạp

  • Thời gian: O(n) - đúng 1 lượt.
  • Bộ nhớ: O(1).

Bình luận

  • Tại sao 1 lượt là đủ? Sau khi xử lý nums[i] (swap nếu cần), thuộc tính của các vị trí từ 0 đến i được bảo toàn. Trong lúc swap, chỉ nums[i-1] bị thay đổi - nhưng nó chỉ ảnh hưởng đến cặp (i-2, i-1), mà cặp đó được thiết kế để vẫn còn đúng sau swap (vì nếu nums[i] < nums[i-1] mà cần nums[i] >= nums[i-1], thì hoán đổi cho nums[i-1] nhỏ hơn → vẫn thoả nums[i-1] <= nums[i-2] ở bước trước).
  • Bẫy thường gặp:
    • Dùng < / > strict thay vì <= / >= - sẽ sai khi có duplicate.
  • Follow-up phổ biến:
    1. LC 324 - Wiggle Sort II: yêu cầu strict (< và >) → khó hơn nhiều, phải sort rồi đan xen 2 nửa.

Bài tự luyện liên quan

  • LC 324 - Wiggle Sort II.
  • LC 75 - Sort Colors (bài 4.1).
  • LC 215 - Kth Largest Element (quickselect).

Tóm tắt chương & Quyết định

Sorting mua gì / mất gì

Mua: - Đưa thứ tự về monotonic → cho phép two-pointer, binary search, sweep. - Hợp nhóm các phần tử “giống nhau” cạnh nhau (anagram, intervals).

Mất: - Mất index gốc → nếu output yêu cầu index, lưu (value, idx) trước. - Mutate input - làm rõ với interviewer trước khi sort. - O(n log n), không miễn phí.

Largest Number (LC 179) - bẫy comparator

  • So sánh (a+b) vs (b+a) là bắc cầu (transitive) - chứng minh được nên an toàn dùng cmp_to_key.
  • Lưu ý: Python 3 không có tham số cmp mặc định nữa. Dùng from functools import cmp_to_key.
  • Edge "00...0" → strip leading zeros sau khi nối.

Meeting Rooms II - heap vs sweep

  Heap Sweep line
Tư duy Phòng nào trống sớm nhất → tái dùng Đếm overlap tại mỗi mốc thời gian
Code heapq + sort theo start Sort events (time, ±1)
Output yêu cầu Số phòng max Số phòng max
Khi mở rộng Dễ trả về schedule (phòng nào lúc nào) Khó trả về schedule

Wiggle Sort: LC 280 vs 324

  • LC 280: nums[0] ≤ nums[1] ≥ nums[2] ≤ ... - chỉ cần swap láng giềng sai → O(n).
  • LC 324: nums[0] < nums[1] > nums[2] < ... - chặt, cần sort + interleave → O(n log n) hoặc median trick.