Vì sao HashMap thường giúp giảm O(n²) xuống O(n) trong bài coding?

HashMap đổi thêm bộ nhớ để có lookup trung bình O(1).

• Thay vì với mỗi phần tử phải duyệt lại toàn bộ phần còn lại để tìm complement, duplicate hoặc frequency, ta lưu thông tin đã gặp vào map/set.

Ví dụ Two Sum brute force là O(n²) vì thử mọi cặp; dùng map value -> index thì mỗi số chỉ cần kiểm complement đã xuất hiện chưa, nên O(n).

• Trade-off là space O(n), và cần cẩn thận thứ tự thao tác: nhiều bài phải check trước rồi mới insert để tránh dùng lại cùng một phần tử.