Học Trapping Rain Water, Top K Frequent và Selection Sort bằng trực quan từng bước với DSA View View 👀👀
Hoi hoi!
Mình là @nyaomaru, một frontend engineer gần đây đang cực kỳ mê ramen. 😸🍜
Bạn đã thử DSA View View chưa? 👀👀
https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo
DSA View View là một tool giúp bạn hiểu DSA bằng cách trực quan hóa cách implementation thực sự chạy ở runtime.
Trong những bài trước, chúng ta đã xem khá nhiều bài toán:
- Two Sum
- Binary Search
- Bubble Sort
- Valid Parentheses
- Reverse Linked List
- Maximum Depth of Binary Tree
- Number of Islands
- Invert Binary Tree
- Course Schedule
Lần này, chúng ta sẽ tiếp tục với ba bài:
- Trapping Rain Water
- Top K Frequent Elements
- Selection Sort
Ba bài này sử dụng ba cách suy nghĩ khá khác nhau:
Thu hẹp bài toán từ hai phía
Đếm trước, rồi tổ chức lại theo frequency
Liên tục chọn value tiếp theo cần đặt vào đúng position
Một lần nữa, implementation không quá dài.
Nhưng có nhiều state thay đổi cùng lúc, và đó mới là phần khó theo dõi.
Nếu chỉ nhìn final code, rất dễ có cảm giác:
Mình hiểu từng dòng... nhưng cả algorithm đang chạy như thế nào vậy??? 🙀
Vậy nên lần này, hãy tiếp tục nhìn trực tiếp vào runtime. 👀
🌧️ Trapping Rain Water
Bắt đầu với Trapping Rain Water.
Giả sử chúng ta có các độ cao:
[0, 1, 0, 2, 1, 0, 1, 3]
Nếu vẽ chúng thành walls, sẽ gần giống thế này:
█
█ █
█ █ █ █ █
-----------------
0 1 0 2 1 0 1 3
Mưa rơi xuống.
Một phần water sẽ chảy đi.
Nhưng một phần sẽ bị giữ lại giữa những walls cao hơn.
Ví dụ:
█~~~~~~~█
█~~~█~~~~~~~█
-----------------
Vậy câu hỏi là:
Tổng cộng có thể giữ lại bao nhiêu water?
Lần đầu nhìn bài này, mình thấy khá rối. 😿
Bởi vì lượng water nằm trên một position không chỉ phụ thuộc vào chính position đó.
Nó còn phụ thuộc vào walls ở hai phía.
Vậy chúng ta thực sự cần biết điều gì?
Một Position có thể giữ bao nhiêu Water?
Hãy tưởng tượng một position như thế này:
left wall right wall
█ █
█ x █
█ █ █
water level không thể cao hơn wall thấp hơn trong hai phía.
Vì vậy mức water tối đa là:
Math.min(leftMax, rightMax);
Sau đó trừ đi chiều cao hiện tại:
water = min(leftMax, rightMax) - currentHeight
Đó là idea cơ bản.
Nhưng có cần phải tìm lại maximum bên trái và bên phải ở mỗi position không?
Không.
Chúng ta có thể dùng Two Pointers.
Two Pointers
implementation:
function trap(height: number[]): number {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
Có khá nhiều value quan trọng:
left
right
leftMax
rightMax
water
Đây chính là kiểu code mà mình hiểu từng variable riêng lẻ...
nhưng bắt đầu lạc đường khi tất cả cùng thay đổi. 😹
Hãy dùng một example nhỏ hơn:
[2, 0, 1, 3]
Bắt đầu từ hai đầu
Ban đầu:
left = 0
right = 3
[2, 0, 1, 3]
↑ ↑
left right
Độ cao hiện tại:
height[left] = 2
height[right] = 3
Vì:
2 <= 3
nên chúng ta xử lý left side trước.
Wall cao 2 trở thành:
leftMax = 2
Sau đó di chuyển left.
[2, 0, 1, 3]
↑ ↑
left right
Bây giờ có thể giữ Water
Độ cao hiện tại là:
0
Nhưng chúng ta đã biết bên trái có wall cao 2.
Và ở thời điểm này, phía bên phải có một boundary đủ cao để giữ water ở current left position.
Vậy lượng water ở đây là:
leftMax - height[left]
2 - 0
= 2
Do đó:
water = 2
Di chuyển tiếp.
[2, 0, 1, 3]
↑ ↑
left right
Bây giờ:
height[left] = 1
leftMax = 2
nên:
2 - 1 = 1
Thêm một unit water.
water = 3
Tiếp tục xử lý phần còn lại.
Done! 🎉
Tại sao có thể xử lý phía thấp hơn trước?
Đây là phần quan trọng.
Giả sử:
height[left] <= height[right]
Ở thời điểm đó, chúng ta đã biết phía right có một wall ít nhất không thấp hơn current left wall.
Vậy với current left position, chúng ta không còn phải lo:
Phía bên phải có wall để giữ water hay không?
Đã có rồi.
Điều giới hạn lượng water lúc này là:
Wall cao nhất mà chúng ta đã thấy ở phía left là bao nhiêu?
Vì vậy có thể an toàn tính:
leftMax - height[left];
mà không cần biết tất cả future walls.
Phía right cũng hoàn toàn tương tự.
Nếu:
height[right] < height[left]
thì xử lý right side bằng rightMax.
Algorithm liên tục thu hẹp vùng chưa biết từ hai phía:
L → → → ← ← ← R
cho đến khi mọi thứ được xử lý.
Complexity
Mỗi pointer chỉ đi qua array một lần.
Time: O(n)
Space: O(1)
👀 Hãy View View nó
Bài này cực kỳ hợp với visualization.
Vì cùng lúc chúng ta có:
left
right
leftMax
rightMax
water
và tất cả thay đổi ở những thời điểm khác nhau.
Chỉ nhìn dòng này:
water += leftMax - height[left];
mình rất dễ bắt đầu hỏi:
Tại sao bây giờ lại dùng leftMax?
rightMax hiện tại là bao nhiêu?
Tại sao left di chuyển chứ không phải right?
water đã tích lũy bao nhiêu rồi?
Phần nào của array vẫn chưa được xử lý?
😿
Khi xem step-by-step, chúng ta có thể thấy search area thực sự thu nhỏ dần.
L R
↓ ↓
[2, 0, 1, 3]
L R
↓ ↓
[2, 0, 1, 3]
L R
↓ ↓
[2, 0, 1, 3]
Đồng thời:
leftMax
rightMax
water
cũng tiếp tục thay đổi.
Thực ra algorithm cứ lặp lại một câu hỏi:
Ở thời điểm này, phía nào mình đã có đủ information để xác định answer một cách an toàn?
Xử lý phía đó.
Rồi đi tiếp vào trong.
Chỉ vậy thôi. 🌧️😸
🔢 Top K Frequent Elements
Tiếp theo là Top K Frequent Elements.
Giả sử:
[1, 1, 1, 2, 2, 3]
và:
k = 2
Mỗi number xuất hiện bao nhiêu lần?
1 → 3 lần
2 → 2 lần
3 → 1 lần
Vậy hai values xuất hiện nhiều nhất là:
[1, 2]
Kết quả khá dễ hiểu.
Nhưng implementation thì sao?
Đầu tiên, đếm tất cả
Trước hết chúng ta cần frequency.
Có thể dùng Map:
const frequency = new Map<number, number>();
Sau đó đếm từng value:
for (const num of nums) {
frequency.set(num, (frequency.get(num) ?? 0) + 1);
}
Với:
[1, 1, 1, 2, 2, 3]
chúng ta có:
frequency = {
1 → 3
2 → 2
3 → 1
}
Nice.
Nhưng vẫn chưa có top K.
Tất nhiên chúng ta có thể sort tất cả theo frequency.
Nhưng ở đây có một cách khác khá thú vị.
Dùng Frequency làm Index
frequency lớn nhất không thể lớn hơn:
nums.length
Vậy chúng ta có thể tạo buckets:
const buckets: number[][] = Array.from(
{ length: nums.length + 1 },
() => []
);
Index của bucket chính là frequency.
Ví dụ:
bucket[1] = values xuất hiện 1 lần
bucket[2] = values xuất hiện 2 lần
bucket[3] = values xuất hiện 3 lần
Frequency:
1 → 3
2 → 2
3 → 1
sẽ trở thành:
index 0 → []
index 1 → [3]
index 2 → [2]
index 3 → [1]
Mình rất thích chỗ này. 👀
Lúc đầu chúng ta hỏi:
Frequency của value này là bao nhiêu?
Sau khi chuyển sang buckets, câu hỏi trở thành:
Những values nào có frequency này?
Cùng một information.
Nhưng direction bị đảo lại.
Implementation
Full implementation:
function topKFrequent(nums: number[], k: number): number[] {
const frequency = new Map<number, number>();
for (const num of nums) {
frequency.set(num, (frequency.get(num) ?? 0) + 1);
}
const buckets: number[][] = Array.from(
{ length: nums.length + 1 },
() => []
);
for (const [num, count] of frequency) {
buckets[count].push(num);
}
const result: number[] = [];
for (let count = buckets.length - 1; count >= 0; count--) {
for (const num of buckets[count]) {
result.push(num);
if (result.length === k) {
return result;
}
}
}
return result;
}
Hãy đi từng bước.
Step 1: Tạo Frequency Map
Ban đầu:
frequency = {}
Đọc 1 đầu tiên:
1 → 1
1 thứ hai:
1 → 2
1 thứ ba:
1 → 3
Sau đó là 2:
1 → 3
2 → 1
Một 2 nữa:
1 → 3
2 → 2
Cuối cùng 3:
1 → 3
2 → 2
3 → 1
Done.
Step 2: Đưa Values vào Buckets
Tiếp theo:
buckets[count].push(num);
Ví dụ:
1 → 3
thì:
buckets[3].push(1)
2 → 2
thì:
buckets[2].push(2)
Và:
3 → 1
thành:
buckets[1].push(3)
Cuối cùng:
0: []
1: [3]
2: [2]
3: [1]
Step 3: Đọc từ Frequency cao nhất
Chúng ta cần most frequent values.
Vì vậy không bắt đầu từ 0.
Bắt đầu từ cuối:
3 → [1]
2 → [2]
1 → [3]
Lấy 1:
result = [1]
Còn thiếu một value.
Tiếp tục:
result = [1, 2]
Bây giờ:
result.length === k
nên return.
Done! 🎉
Điều thú vị ở đây là gì?
Mình thích solution này vì data structure thứ hai thay đổi cách nhìn cùng một information.
Map:
value → frequency
Buckets:
frequency → values
Information không đổi.
Nhưng direction thay đổi.
Và thế là lấy most frequent values trở nên rất dễ.
Chỉ cần đọc buckets từ cuối về đầu.
Complexity
Mỗi number được đếm một lần.
Mỗi unique number được đưa vào một bucket.
Sau đó duyệt buckets.
Time: O(n)
Space: O(n)
👀 Hãy View View nó
Ở bài này, data thay đổi representation nhiều lần.
Đầu tiên:
nums
↓
frequency Map
Sau đó:
frequency Map
↓
buckets
Cuối cùng:
buckets
↓
result
Nếu chỉ nhìn final implementation, rất dễ tự hỏi:
Tại sao lại cần một Map rồi lại thêm buckets nữa?
Khi nhìn runtime, chúng ta thấy data đổi hình dạng từng bước:
[1, 1, 1, 2, 2, 3]
↓ count
1 → 3
2 → 2
3 → 1
↓ bucket
1: [3]
2: [2]
3: [1]
↓ highest first
[1, 2]
Không có magic nào ở đây cả.
Chúng ta chỉ:
Tổ chức lại information thành một hình dạng khiến answer dễ lấy hơn.
Nhìn như vậy thì idea trở nên rõ hơn rất nhiều. 🔢😸
👉 Selection Sort
Cuối cùng, hãy sort thêm một lần nữa!
Trước đây chúng ta đã xem Bubble Sort.
Lần này là Selection Sort.
Giả sử:
[5, 3, 4, 1, 2]
và muốn:
[1, 2, 3, 4, 5]
Selection Sort có một idea rất simple:
Tìm value nhỏ nhất trong phần còn lại rồi đưa nó lên đầu.
Sau đó repeat.
First Pass
Ban đầu:
[5, 3, 4, 1, 2]
↑
i
Tạm giả sử value đầu tiên là nhỏ nhất:
minIndex = 0
Sau đó scan sang phải.
5 vs 3
3 nhỏ hơn.
Nên:
minIndex = 1
Tiếp theo:
3 vs 4
Không đổi.
Tiếp:
3 vs 1
1 nhỏ hơn.
minIndex = 3
Cuối cùng:
1 vs 2
1 vẫn nhỏ nhất.
Vậy smallest value nằm ở index 3.
Swap:
[5, 3, 4, 1, 2]
↑ ↑
i min
↓
[1, 3, 4, 5, 2]
Position đầu tiên đã hoàn thành.
[1 | 3, 4, 5, 2]
↑
sorted
Repeat
Bây giờ bắt đầu từ index 1.
[1 | 3, 4, 5, 2]
↑
i
Tìm smallest value trong:
[3, 4, 5, 2]
Đó là 2.
Swap:
[1, 2 | 4, 5, 3]
Lặp lại.
Smallest value còn lại tiếp theo là 3.
Tiếp tục...
Cuối cùng:
[1, 2, 3, 4, 5]
Sorted! 🎉
Implementation
function selectionSort(nums: number[]): number[] {
for (let i = 0; i < nums.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
}
}
return nums;
}
Có ba index cần theo dõi:
i
minIndex
j
j đi qua phần unsorted để tìm value nhỏ nhất.
Tại sao gọi là Selection Sort?
Bởi vì mỗi pass sẽ:
select smallest value còn lại.
Find smallest
↓
Select it
↓
Move it to the front
↓
Repeat
Đó gần như là toàn bộ algorithm.
Complexity
Với mỗi position, chúng ta scan phần còn lại.
Vì vậy:
Time: O(n²)
Sort trực tiếp trên array hiện tại:
Space: O(1)
Nếu phải sort một huge production dataset, có lẽ mình sẽ không chọn Selection Sort. 😹
Nhưng với tư cách learning algorithm, nó rất dễ nhìn.
👀 Hãy View View nó
implementation có nested loops:
for (let i = 0; i < nums.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < nums.length; j++) {
Nếu chỉ đọc code, rất dễ mất dấu:
Phần nào đã sorted?
i đang ở đâu?
j đã scan tới đâu?
minIndex hiện tại trỏ vào value nào?
Khi nào swap xảy ra?
Khi visualize, pattern cơ bản trở nên rất rõ:
[5, 3, 4, 1, 2]
↑
smallest
[1 | 3, 4, 5, 2]
↑
smallest
[1, 2 | 4, 5, 3]
Algorithm liên tục mở rộng vùng đã hoàn thành từ trái sang phải.
sorted | unsorted
Ban đầu gần như tất cả đều unsorted.
Sau mỗi pass:
[1 | 3, 4, 5, 2]
[1, 2 | 4, 5, 3]
[1, 2, 3 | 5, 4]
sorted area tăng thêm một position.
Đó là Selection Sort.
Chọn smallest value còn lại.
Đặt nó vào position tiếp theo.
Repeat. 🍥😸
🧠 Cuối cùng chúng ta đã học được gì?
Ba bài này trông hoàn toàn khác nhau.
Nhưng mỗi bài dạy một cách suy nghĩ rất hữu ích.
Trapping Rain Water
Dùng information từ hai phía để quyết định:
Phía nào hiện tại đã có đủ information để mình xác định answer an toàn?
Which side do I know enough about right now?
Top K Frequent Elements
Đếm xong chưa chắc đã kết thúc.
Đôi khi cần hỏi:
Có thể tổ chức lại information thành một structure giúp answer dễ lấy hơn không?
Can I reorganize this information around what I actually need?
Selection Sort
Xác định answer một position tại một thời điểm.
What value belongs in this position next?
Vậy lần này chúng ta đã xem:
Two pointers
Frequency buckets
Selection
Ba mental model khác nhau.
Nhưng giống như những bài trước, phần khó thường không phải syntax.
Mà là changing state.
Pointer nào vừa di chuyển?
Maximum hiện tại là bao nhiêu?
Map đang chứa gì?
Bucket nào vừa thay đổi?
minIndex đang ở đâu?
Phần nào đã hoàn thành?
Giữ tất cả những thứ đó trong đầu khá mệt.
Vì vậy mình muốn nhìn thấy nó.
View View. 👀👀
🎯 Kết luận
Trong bài này, chúng ta đã xem:
- Trapping Rain Water với Two Pointers
- Top K Frequent Elements với frequency buckets
- Selection Sort
Và quan trọng nhất, chúng ta đã theo dõi state thay đổi khi mỗi algorithm chạy.
Trong Trapping Rain Water:
left → ← right
hai pointers tiến dần vào giữa, trong khi:
leftMax
rightMax
water
cũng thay đổi.
Trong Top K Frequent Elements, cùng một data thay đổi representation:
array
↓
frequency Map
↓
buckets
↓
result
Trong Selection Sort, chúng ta thấy sorted area tăng thêm một position sau mỗi pass.
Đó chính là kiểu quá trình mình muốn nhìn thấy khi tạo DSA View View.
https://dsa-view-view.vercel.app
Bạn có thể tự viết TypeScript implementation hoặc load một example có sẵn, chạy bằng input của riêng mình rồi di chuyển backward / forward trong runtime.
Nếu bạn cũng đang học DSA, hãy thử View View một trong ba bài này.
Đặc biệt khi bạn có cảm giác:
Mình hiểu từng dòng... nhưng tại sao toàn bộ algorithm vẫn khó hiểu vậy? 😿
Nhìn trực tiếp runtime có thể giúp những mảnh rời rạc đó kết nối với nhau.
Nếu có DSA problem nào bạn muốn mình viết tiếp, hãy để lại comment nhé!
Mình cũng còn rất nhiều algorithm muốn học. 😸
Cùng luyện cơ DSA thôi! 💪
Nếu bạn thích DSA View View, hãy cho project một star ⭐
https://github.com/nyaomaru/dsa-view-view
Hẹn gặp lại ở bài tiếp theo!
Bản tiếng Anh gốc:
https://dev.to/nyaomaru/learn-trapping-rain-water-top-k-frequent-and-selection-sort-with-step-by-step-visualization-in-dsa-1flg
All Rights Reserved
