Chương 1 - Array

Array (mảng) là cấu trúc dữ liệu cơ bản nhất nhưng cũng là pattern xuất hiện nhiều nhất trong phỏng vấn coding ở Big Tech. Phần lớn các kỹ thuật ở chương sau (two pointers, sliding window, prefix sum, monotonic stack, …) đều bắt nguồn từ việc thao tác trên array. Mục tiêu của chương: thành thạo các thao tác in-place, two-pass, và bắt đầu hình thành thói quen “nghĩ về index thay vì nghĩ về phần tử”.

Mục tiêu chương

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

Thành thạo 4 trick array: in-place, two-pass, prefix-suffix, two-pointer.
Biết hỏi clarifying questions chuẩn (sort/dup/in-place/overflow).
Nhận diện khi nào cần O(1) extra space.
Tránh các bẫy: off-by-one, shallow copy, mutation trong loop.

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

Đề bài cho một mảng số / chuỗi và yêu cầu tìm cặp / bộ ba / dãy con thoả mãn điều kiện.
Có thể không cho phép dùng bộ nhớ phụ (in-place) hoặc yêu cầu O(1) extra space.
Có dạng quen thuộc: “tìm chỉ số”, “đếm số lần”, “đảo / xoay / sắp xếp lại”, “chia mảng làm hai phần”.
Khi nhận đề: luôn hỏi interviewer 3 câu chốt:
1. Mảng có sorted không? Có duplicate không?
2. Có thể modify in-place không, hay phải giữ nguyên?
3. Giá trị có thể âm / có thể là 0 / có overflow không?

Template code

from typing import List

def two_pass_pattern(nums: List[int]) -> List[int]:
    """Mẫu 2-lượt: pass 1 gom thông tin, pass 2 dùng thông tin đó."""
    n = len(nums)
    aux = [0] * n
    # pass 1: tính prefix / suffix / count
    for i in range(n):
        aux[i] = ...   # tuỳ bài
    # pass 2: dùng aux để ra kết quả
    out = [0] * n
    for i in range(n):
        out[i] = ...   # tuỳ bài
    return out


def two_pointers_in_place(nums: List[int]) -> int:
    """Mẫu two pointers in-place: slow = vị trí ghi, fast = vị trí đọc."""
    slow = 0
    for fast in range(len(nums)):
        if condition(nums[fast]):
            nums[slow] = nums[fast]
            slow += 1
    return slow  # độ dài phần "hợp lệ" sau khi nén

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

LC 26 - Remove Duplicates from Sorted Array
LC 27 - Remove Element
LC 88 - Merge Sorted Array
LC 169 - Majority Element (Boyer–Moore voting)
LC 268 - Missing Number
LC 287 - Find the Duplicate Number
LC 525 - Contiguous Array
LC 769 - Max Chunks To Make Sorted

1.1 Two Sum (LC 1)

Đề bài

Cho một mảng số nguyên nums và một số nguyên target. Hãy trả về chỉ số của hai phần tử trong nums sao cho tổng của chúng bằng target.

Bạn có thể giả định mỗi input có đúng một đáp án, và không được dùng cùng một phần tử hai lần.

Ví dụ

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Giải thích: nums[0] + nums[1] == 9.

Ràng buộc

2 <= len(nums) <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Chỉ có duy nhất một cặp đáp án.

Clarifying questions

Có duplicate trong mảng không? → Có thể có, nhưng đáp án vẫn duy nhất.
Mảng đã sorted chưa? → Không. (Nếu sorted, dùng two pointers - xem LC 167.)
Cần trả về index hay giá trị? → Index (0-based).

Hướng tiếp cận

Brute force - O(n²). Duyệt mọi cặp (i, j) với i < j và kiểm tra nums[i] + nums[j] == target. Dễ code nhưng sẽ TLE khi n lớn.

Tối ưu - Hash map một lượt - O(n). Khi đứng tại chỉ số i, ta cần tìm xem có j < i nào để nums[j] == target - nums[i] hay không. Dùng dict để lưu {giá_trị: chỉ_số} của các phần tử đã thấy.

Mẹo trình bày: Luôn bắt đầu bằng brute force, nói rõ độ phức tạp của nó, sau đó nói: “Em nghĩ có thể thay phép tìm tuyến tính O(n) bằng hash map tra cứu O(1), nhờ đó tổng độ phức tạp giảm từ O(n²) xuống O(n)…” - interviewer rất thích luồng tư duy này.

Code Python 3

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}
        for i, x in enumerate(nums):
            complement = target - x
            if complement in seen:
                return [seen[complement], i]
            seen[x] = i
        return []  # theo đề bài, dòng này không bao giờ chạy

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

Thời gian: O(n) - duyệt 1 lượt, mỗi look-up trong dict là O(1) trung bình.
Bộ nhớ: O(n) - dict lưu tối đa n cặp (giá_trị, chỉ_số).

Bình luận

Bẫy thường gặp: ghi seen[x] = i trước khi check complement - sẽ sai khi nums = [3, 3] và target = 6 (lúc đó complement == x và ta sẽ dùng cùng một phần tử hai lần).
Follow-up phổ biến:
1. Nếu mảng đã sorted → two pointers, O(n) time, O(1) extra space (LC 167).
2. Trả về tất cả cặp (có thể duplicate) → phải sort + skip duplicate.
3. Mở rộng lên 3Sum, 4Sum (xem Chương 26).
Biến thể: Two Sum trên BST (LC 653), Two Sum trên data stream (LC 170).

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

LC 167 - Two Sum II (mảng đã sort).
LC 170 - Two Sum III (Data structure design).
LC 653 - Two Sum IV (Input is a BST).

1.2 Best Time to Buy and Sell Stock (LC 121)

Đề bài

Cho mảng prices với prices[i] là giá cổ phiếu vào ngày thứ i. Bạn được mua một lần rồi bán một lần sau đó (không được bán trước khi mua). Hãy trả về lợi nhuận lớn nhất có thể, hoặc 0 nếu không có giao dịch nào có lãi.

Ví dụ

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Giải thích: mua ngày 2 (giá 1), bán ngày 5 (giá 6), lợi nhuận = 6 - 1 = 5.

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Giải thích: giá giảm liên tục, không có giao dịch nào có lãi.

Ràng buộc

1 <= len(prices) <= 10^5
0 <= prices[i] <= 10^4

Clarifying questions

Có bắt buộc phải mua không? → Không. Nếu không có lãi, trả về 0.
Mua bán cùng ngày được không? → Không, phải bán sau ngày mua strictly.
Được giao dịch nhiều lần không? → Không, đúng 1 lần mua + 1 lần bán. (Multiple transactions là một bài khác - LC 122.)

Hướng tiếp cận

Brute force - O(n²). Duyệt mọi cặp (i, j) với i < j và lấy max(prices[j] - prices[i]). TLE với n = 10^5.

Tối ưu - một lượt, O(n). Khi đứng tại ngày i và quyết định “sẽ bán hôm nay”, lợi nhuận tối ưu là prices[i] - min(prices[0..i-1]). Vậy ta chỉ cần duy trì min_so_far khi duyệt và cập nhật best mỗi bước.

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

day        :   0    1    2    3    4    5
prices     :   7    1    5    3    6    4
                    │              │
                    │ mua ở đây    │ bán ở đây
                    ▼              ▼
min_so_far :   7    1    1    1    1    1
profit_now :   0    0    4    2    5    3   (= prices[i] - min_so_far)
best       :   0    0    4    4    5    5   ← đáp án = 5
                              ▲
                              giữ nguyên vì 2 < 4

Mindset: Đây là DP một biến. State min_so_far chính là cách rút gọn mảng dp[i] = min(prices[0..i]) về O(1) space - kỹ thuật sẽ gặp đi gặp lại ở các chương DP sau.

Code Python 3

from typing import List
import math

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_so_far = math.inf
        best = 0
        for p in prices:
            min_so_far = min(min_so_far, p)
            best = max(best, p - min_so_far)
        return best

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

Thời gian: O(n) - duyệt 1 lượt.
Bộ nhớ: O(1) - chỉ 2 biến.

Bình luận

Bẫy thường gặp: khởi tạo best = -inf rồi cuối cùng quên xử lý trường hợp tất cả giá giảm - sẽ trả về số âm. Khởi tạo best = 0 cho an toàn.
Follow-up phổ biến:
1. Cho phép nhiều giao dịch không giới hạn (LC 122).
2. Tối đa k giao dịch (LC 188) - DP với 3 chiều.
3. Có cooldown 1 ngày sau khi bán (LC 309).
4. Có phí giao dịch (LC 714).
Cả họ bài này được cover ở Chương 29 - Dynamic Programming.

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

LC 122 - Best Time to Buy and Sell Stock II (multiple transactions).
LC 309 - Best Time to Buy and Sell Stock with Cooldown.
LC 714 - Best Time to Buy and Sell Stock with Transaction Fee.

1.3 Product of Array Except Self (LC 238)

Đề bài

Cho một mảng nums có n số nguyên, trả về mảng answer cùng độ dài, sao cho answer[i] là tích của tất cả phần tử của nums trừ nums[i].

Ràng buộc đặc biệt: - Không được dùng phép chia. - Phải chạy trong O(n) time.

Ví dụ

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Giải thích:
  answer[0] = 2*3*4 = 24
  answer[1] = 1*3*4 = 12
  answer[2] = 1*2*4 = 8
  answer[3] = 1*2*3 = 6

Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Ràng buộc

2 <= len(nums) <= 10^5
-30 <= nums[i] <= 30
Tích bất kỳ của các phần tử nằm trong phạm vi int 32-bit.

Clarifying questions

Mảng có chứa số 0 không? → Có thể, và đó là case quan trọng (1 zero → 1 vị trí khác 0; ≥2 zero → all-zero).
Output có được tính vào bộ nhớ phụ không? → Theo LC, output array không tính. Follow-up: làm O(1) extra space.
Cần trả về mảng mới hay sửa in-place trên nums? → Mảng mới.

Hướng tiếp cận

Brute force - O(n²). Với mỗi i, duyệt lại toàn mảng để tính tích - đề bài đã cấm sẵn.

Phép chia - O(n) nhưng bị cấm. Tính total = product(nums) rồi answer[i] = total / nums[i]. Cấm vì khi nums[i] == 0 ta chia cho 0; hơn nữa, nhiều ngôn ngữ không có integer-exact division.

Tối ưu - Prefix product + Suffix product - O(n) time, O(1) extra space (không tính output).

Quan sát: answer[i] = (∏ nums[0..i-1]) * (∏ nums[i+1..n-1]). Gọi 2 lượng: - left[i] = tích nums[0..i-1] (left product, left[0] = 1). - right[i] = tích nums[i+1..n-1] (right product, right[n-1] = 1). Khi đó answer[i] = left[i] * right[i].

Để đạt O(1) extra space, ta dùng chính mảng answer: - Lượt 1 (trái → phải): điền answer[i] = left[i]. - Lượt 2 (phải → trái): nhân answer[i] *= right, vừa duyệt vừa cập nhật biến right.

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

              i=0     i=1     i=2     i=3
nums      :  [  1  ,   2  ,   3  ,   4  ]

                 ┌─────────────┐
                 │  prefix →   │   (tích các phần tử BÊN TRÁI i)
                 ▼             ▼
left[i]   :  [  1  ,   1  ,   2  ,   6  ]
              (rỗng) (1)   (1·2) (1·2·3)

                         ┌─────────────┐
                         │   ← suffix  │  (tích các phần tử BÊN PHẢI i)
                         ▼             ▼
right[i]  :  [ 24  ,  12  ,   4  ,   1  ]
            (2·3·4)(3·4)  (4)  (rỗng)

                         ↓  nhân từng vị trí  ↓

answer[i] :  [ 24  ,  12  ,   8  ,   6  ]
              1·24   1·12   2·4    6·1

Trong code thực, ta không lưu cả 2 mảng left và right - chỉ dùng answer cho lượt prefix, rồi dùng 1 biến right rolling từ phải sang trái để nhân vào answer ngay tại chỗ.

Code Python 3

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # Lượt 1: answer[i] = tích các phần tử ở bên trái i.
        left = 1
        for i in range(n):
            answer[i] = left
            left *= nums[i]

        # Lượt 2: nhân thêm tích bên phải, dùng biến right rolling.
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]

        return answer

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

Thời gian: O(n) - đúng 2 lượt qua mảng.
Bộ nhớ: O(1) extra (không tính output).

Bình luận

Bẫy với số 0: nếu mảng chứa đúng 1 số 0 → chỉ vị trí của số 0 có kết quả khác 0; nếu ≥ 2 số 0 → toàn bộ output là 0. Cách tiếp cận prefix/suffix xử lý tự nhiên các case này, không cần special-case.
Follow-up phổ biến: “Làm thế nào với phép chia, nhưng vẫn xử lý đúng số 0?” → Đếm số 0 (zero_count). Nếu zero_count >= 2 → all-zero. Nếu == 1 → chỉ vị trí đó nhận product_non_zero, các vị trí khác là 0. Nếu == 0 → chia bình thường.
Biến thể: Maximum Product Subarray (LC 152) - cũng dùng pattern duy trì cả max và min “đến i” vì có thể có số âm.

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

LC 152 - Maximum Product Subarray.
LC 2031 - Count Subarrays With More Ones Than Zeros (prefix trick).
LC 1685 - Sum of Absolute Differences in a Sorted Array.

1.4 Move Zeroes (LC 283)

Đề bài

Cho mảng nums, hãy di chuyển tất cả số 0 về cuối mảng, giữ nguyên thứ tự tương đối của các phần tử khác 0. Phải làm in-place, không được tạo mảng phụ.

Ví dụ

Input:  nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Input:  nums = [0]
Output: [0]

Ràng buộc

1 <= len(nums) <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
Phải làm in-place, không return (modify trực tiếp nums).
Follow-up: tối thiểu hoá số lần ghi (write operations).

Clarifying questions

Có cần giữ thứ tự tương đối của các số khác 0 không? → Có, đó là yêu cầu chính.
Số âm tính là khác 0 không? → Có, chỉ riêng số 0 mới bị “đẩy” về cuối.

Hướng tiếp cận

Brute force - O(n) time, O(n) extra space. Tạo mảng phụ chứa các số khác 0, sau đó pad số 0 cho đủ n. Đề bài cấm dùng mảng phụ - bị loại.

Tối ưu - Two pointers - O(n) time, O(1) extra space. Dùng 2 con trỏ: - slow = vị trí tiếp theo để ghi một số khác

- fast = vị trí đang đọc trong mảng.

Pass 1: với mỗi fast, nếu nums[fast] != 0 → nums[slow] = nums[fast], tăng slow. Pass 2: từ slow đến hết mảng, gán 0.

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

                    Lượt 1: dồn các số khác 0 về đầu
                    ──────────────────────────────────

Khởi tạo :  [ 0 , 1 , 0 , 3 , 12]      slow=0  fast=0
              S
              F

fast=0:  nums[0]=0, bỏ qua
         [ 0 , 1 , 0 , 3 , 12]         slow=0  fast=1
           S
               F

fast=1:  nums[1]=1≠0 → ghi nums[0]=1, slow++
         [ 1 , 1 , 0 , 3 , 12]         slow=1  fast=2
               S
                   F

fast=2:  nums[2]=0, bỏ qua             slow=1  fast=3
fast=3:  nums[3]=3≠0 → ghi nums[1]=3, slow++
         [ 1 , 3 , 0 , 3 , 12]         slow=2  fast=4
                   S
                       F

fast=4:  nums[4]=12≠0 → ghi nums[2]=12, slow++
         [ 1 , 3 ,12 , 3 , 12]         slow=3  fast=hết

                    Lượt 2: từ slow đến hết, gán 0
                    ──────────────────────────────────

         [ 1 , 3 ,12 , 0 , 0 ]    ← đáp án
                       ▲   ▲
                   gán 0  gán 0

Cách này tối thiểu hoá số phép ghi về đúng n (vì mỗi ô được ghi đúng 1 lần). Có một biến thể dùng swap ngay khi đi qua, code ngắn hơn nhưng số ghi gấp đôi.

Code Python 3

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        # Lượt 1: dồn các số khác 0 về đầu.
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        # Lượt 2: phần còn lại gán 0.
        for i in range(slow, len(nums)):
            nums[i] = 0

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

Thời gian: O(n) - 2 lượt liên tiếp, tổng cộng vẫn O(n).
Bộ nhớ: O(1).

Bình luận

Biến thể swap one-pass (ngắn hơn nhưng mỗi cặp bị swap = 2 write; cách 2-pass chỉ 1 write/ô - khi interviewer hỏi “tối thiểu hoá số write”, đưa giải pháp 2-pass):

slow = 0
for fast in range(len(nums)):
    if nums[fast] != 0:
        nums[slow], nums[fast] = nums[fast], nums[slow]
        slow += 1

Bẫy thường gặp: quên reset từ slow đến hết mảng → vẫn còn duplicate của các số khác 0.
Follow-up phổ biến:
1. Move tất cả số âm về cuối → cùng pattern.
2. Sort 3 màu (LC 75) → dùng 3 con trỏ, giải ở Chương 4.

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

LC 27 - Remove Element.
LC 26 - Remove Duplicates from Sorted Array.
LC 75 - Sort Colors (Dutch national flag, Chương 4).

1.5 Container With Most Water (LC 11)

Đề bài

Cho mảng height với height[i] là chiều cao của cột thứ i. Hãy chọn ra 2 cột i < j sao cho lượng nước chứa được giữa chúng là lớn nhất.

Lượng nước = min(height[i], height[j]) * (j - i).

Ví dụ

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Giải thích: chọn cột 1 (cao 8) và cột 8 (cao 7) → 7 * (8-1) = 49.

Input:  height = [1, 1]
Output: 1

Ràng buộc

2 <= len(height) <= 10^5
0 <= height[i] <= 10^4

Clarifying questions

Cột có chiều rộng không? → Không, coi như chiều rộng 0 (chỉ tính khoảng cách j - i).
Có cho phép trả về index không hay chỉ diện tích? → Chỉ diện tích.

Hướng tiếp cận

Brute force - O(n²). Duyệt mọi cặp (i, j) và lấy max. TLE với n = 10^5.

Tối ưu - Two pointers, O(n). Đặt l = 0, r = n - 1. Tại mỗi bước, diện tích hiện tại = min(height[l], height[r]) * (r - l).

Câu hỏi cốt lõi: dịch con trỏ nào? - Dịch con trỏ ở bên thấp hơn.

Tại sao? Diện tích bị giới hạn bởi cột thấp hơn. Nếu dịch con trỏ ở cột cao hơn vào trong, khoảng cách giảm và cột thấp vẫn là bottleneck → diện tích chỉ có thể giảm hoặc bằng. Còn nếu dịch con trỏ ở cột thấp hơn, ta có cơ hội (không bảo đảm) gặp một cột cao hơn để diện tích tăng.

Proof bằng “loại trừ”: Khi cố định cột thấp (giả sử bên trái) và dịch cột bên phải vào, mọi cặp (l, r' < r) đều có diện tích ≤ height[l] * (r - l). Do đó các cặp này không thể là đáp án nếu chưa tốt hơn cái hiện tại - ta “loại trừ” chúng cùng lúc và chỉ cần dịch l.

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

         ▓                                ▓
   8     ▓       ▓                        |          ← chiều cao 8
   7     ▓       ▓                        ▓
   6     ▓   ▓   ▓               ▓        ▓
   5     ▓   ▓   ▓       ▓       ▓        ▓
   4     ▓   ▓   ▓       ▓   ▓   ▓        ▓
   3     ▓   ▓   ▓       ▓   ▓   ▓    ▓   ▓
   2     ▓   ▓   ▓   ▓   ▓   ▓   ▓    ▓   ▓
   1 ▓   ▓   ▓   ▓   ▓   ▓   ▓   ▓    ▓   ▓
       └─┴───┴───┴───┴───┴───┴───┴────┴───┴─
index: 0   1   2   3   4   5   6    7   8
       L                                  R

Bảng trace (★ = đáp án tốt nhất tại thời điểm đó):

  bước │  L   R │ min(h[L], h[R]) │ width │  area │ move
  ─────┼────────┼─────────────────┼───────┼───────┼──────────────
   1   │  0   8 │       1         │   8   │    8  │ h[L]<h[R] → L++
   2   │  1   8 │       7         │   7   │  49 ★ │ h[L]>=h[R] → R--
   3   │  1   7 │       3         │   6   │   18  │ → R--
   4   │  1   6 │       8         │   5   │   40  │ → R--
   5   │  1   5 │       4         │   4   │   16  │ → R--
   6   │  1   4 │       5         │   3   │   15  │ → R--
   7   │  1   3 │       2         │   2   │    4  │ → R--
   8   │  1   2 │       6         │   1   │    6  │ → R--
   ─── │  1   1 │       stop      │       │       │

Đáp án: 49 (cặp cột index 1 và 8, cao 8 và 7).

Code Python 3

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0
        while l < r:
            h = min(height[l], height[r])
            best = max(best, h * (r - l))
            # Luôn dịch con trỏ ở phía thấp hơn.
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return best

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

Thời gian: O(n) - mỗi vòng lặp dịch 1 con trỏ, tổng tối đa n - 1 bước.
Bộ nhớ: O(1).

Bình luận

Bẫy thường gặp: dịch sai con trỏ (dịch cột cao thay vì cột thấp) - vẫn cho ra giá trị nào đó nhưng có thể bỏ lỡ đáp án thật.
Khi height[l] == height[r]: dịch con trỏ nào cũng được, vì cặp (l, r) với cả 2 cột bằng nhau đã được đo, các cặp tiếp theo phải có một bên ≤ h hiện tại → không tốt hơn nữa.
Follow-up phổ biến: “Cho mỗi cột có chiều rộng 1, tính tổng nước đọng” → bài Trapping Rain Water (LC 42, Chương 26).

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

LC 42 - Trapping Rain Water.
LC 167 - Two Sum II (cùng pattern two pointers từ hai đầu).
LC 977 - Squares of a Sorted Array.

1.6 Rotate Array (LC 189)

Đề bài

Cho mảng nums và một số nguyên không âm k. Hãy xoay mảng sang phải k bước.

Ví dụ

Input:  nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Giải thích: xoay phải 1 bước → [7,1,2,3,4,5,6]; 2 bước → [6,7,1,2,3,4,5]; 3 bước → [5,6,7,1,2,3,4].

Input:  nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

Ràng buộc

1 <= len(nums) <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5
Phải làm in-place với O(1) extra space (follow-up).

Clarifying questions

k có thể lớn hơn n không? → Có - phải k %= n trước.
k = 0 được phép không? → Có, output giống input.
Xoay phải hay xoay trái? → Đề bài là phải. Cần hỏi rõ để tránh nhầm.

Hướng tiếp cận

Brute force - Xoay 1 bước, lặp k lần - O(n·k). TLE.

Mảng phụ - O(n) time, O(n) space. new[(i + k) % n] = nums[i], rồi copy new về nums. Đơn giản nhưng vi phạm follow-up O(1) space.

Tối ưu - Three Reverses, O(n) time, O(1) extra space. Quan sát ví dụ với n = 7, k = 3: - Reverse toàn bộ: [7, 6, 5, 4, 3, 2, 1]. - Reverse [0..k-1]: [5, 6, 7, 4, 3, 2, 1]. - Reverse [k..n-1]: [5, 6, 7, 1, 2, 3, 4]. ✓

Trực giác: Khi reverse toàn bộ, phần “đáng lẽ ra cuối” giờ đứng đầu nhưng bị đảo ngược. Hai lần reverse con tiếp theo “sửa” lại thứ tự bên trong mỗi khối.

Hình minh hoạ với n = 7, k = 3:

Input         :  [ 1   2   3   4 │ 5   6   7 ]
                                  ▲
                  k=3 phần tử cuối cần "nhảy" lên đầu

──────────────────────────────────────────────────

Bước 1: reverse toàn bộ [0..6]
                  ◀═══════════════════════════▶
                 [ 7   6   5   4   3   2   1 ]
                   ↑               ↑
                  (5,6,7 đảo)     (1,2,3,4 đảo)

Bước 2: reverse [0..k-1] = [0..2]   (sửa lại 3 phần tử đầu)
                  ◀═══════▶
                 [ 5   6   7 │ 4   3   2   1 ]
                                ↑
                  3 phần tử đầu  4 phần tử cuối vẫn đảo
                  đã đúng        cần sửa tiếp

Bước 3: reverse [k..n-1] = [3..6]   (sửa lại 4 phần tử cuối)
                              ◀═══════════════▶
                 [ 5   6   7 │ 1   2   3   4 ]   ← đáp án ✓

Code Python 3

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n  # luôn normalize trước

        def reverse(left: int, right: int) -> None:
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n - 1)        # đảo toàn bộ
        reverse(0, k - 1)        # đảo phần đầu (k phần tử)
        reverse(k, n - 1)        # đảo phần đuôi

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

Thời gian: O(n) - mỗi phần tử bị swap đúng 2 lần.
Bộ nhớ: O(1).

Bình luận

Bẫy thường gặp:
- Quên k %= n → khi k > n, các vòng reverse có index âm hoặc sai phạm.
- Nhầm xoay trái ↔︎ phải. Để xoay trái k bước: làm tương tự nhưng reverse [0..k-1] trước, sau đó [k..n-1], cuối cùng reverse cả mảng (hoặc tương đương: rotate phải n - k).
Lời giải dùng cycle replacement (GCD trick): Dịch chuyển gcd(n, k) chu trình độc lập, mỗi chu trình “đẩy” phần tử theo nhịp k. Code phức tạp hơn một chút nhưng cũng O(n) / O(1). Nên biết cho follow-up.
Follow-up phổ biến:
1. Cho mảng quá lớn để fit RAM, làm sao xoay? → Disk-based block reversal.
2. Mảng các string độ dài thay đổi → vẫn áp dụng được 3-reverse.

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

LC 61 - Rotate List (xoay linked list, Chương 7).
LC 796 - Rotate String.
LC 48 - Rotate Image (xoay ma trận 2D).

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

Array decision checklist (trước khi viết code)

Câu hỏi	Nếu YES	Nếu NO
Cho phép mutate input không?	In-place (Move Zeroes, Rotate)	Tạo array kết quả
Cần giữ thứ tự gốc?	Two-pointer cùng chiều	Có thể swap tự do
Trả về index hay value?	Cẩn thận khi sort: lưu `(value, index)`	-
Có số 0 / số âm?	Product Except Self không dùng được division	Có thể prefix×suffix bình thường
Cần O(1) bộ nhớ?	3-reverse trick, in-place marker	Có thể dùng hash/extra array

Cửa ngõ sang pattern khác

Prefix Sum / Difference Array → Chương 19 (subarray sum, range update).
Two Pointers → Chương 26 (3Sum, Container, Sort Colors).
Sliding Window → Chương 27 (subarray với ràng buộc động).
Sorting + Greedy → Chương 4, 16 (Meeting Rooms, Jump Game).
Monotonic Stack → Chương 18 (Next Greater, Largest Rectangle).

Recap Rotate Array - so sánh 3 cách

Cách	Time	Space	Khi nào chọn
Extra array	O(n)	O(n)	Dễ viết, ít bug nhất; khi RAM dư
3-reverse	O(n)	O(1)	Mặc định trong phỏng vấn - đẹp & ngắn
Cyclic replacement (GCD)	O(n)	O(1)	Khi interviewer hỏi follow-up “không reverse”