Đây là bài toán tìm phần tử nhỏ nhất và lớn nhất trong một mảng cho trước. Nếu sử dụng phương pháp sắp xếp (sorting), chúng ta có thể giải quyết nó cực kỳ dễ dàng. Tuy nhiên, nếu có thêm các điều kiện ràng buộc như không được dùng sắp xếp, hoặc phải giải với độ phức tạp thời gian $O(n)$ và độ phức tạp không gian $O(1)$, chúng ta cần tìm một phương pháp khác.
Nếu sắp xếp mảng theo thứ tự tự nhiên, số đầu tiên sẽ là số nhỏ nhất và số cuối cùng sẽ là số lớn nhất. Tuy nhiên, rất khó để đạt được độ phức tạp $O(n)$ nếu dùng cách này, vì hầu như không có thuật toán sắp xếp nào xử lý được ở mức $O(n)$. Trong đoạn mã dưới đây, hàm Arrays.sort sử dụng thuật toán TimSort với độ phức tạp thời gian là $O(n log n)$.
public static void printMinMaxNumbersBySort(int[] numbers) {
  Arrays.sort(numbers);
  System.out.println(String.format("%d là số nhỏ nhất", numbers[0]));
  System.out.println(String.format("%d là số lớn nhất", numbers[numbers.length - 1]));
}
Nếu yêu cầu bài toán là độ phức tạp thời gian $O(n)$ và không gian $O(1)$, chúng ta có thể giải quyết như sau:
public static void printMinMaxNumbers(int[] numbers) {
  int largest = Integer.MIN_VALUE;
  int smallest = Integer.MAX_VALUE;
  for (int number : numbers) {
      if (number > largest) {
          largest = number;
      } 
      if (number < smallest) { // Sử dụng if riêng biệt để đảm bảo kiểm tra cả hai
          smallest = number;
      }
  }

  System.out.println(String.format("%d là số nhỏ nhất", smallest));
  System.out.println(String.format("%d là số lớn nhất", largest));
}

Các câu hỏi mở rộng có thể gặp:

1. Ngoài cách trên, có thể giải bài này với độ phức tạp $O(log n)$ không?

Câu trả lời là "KHÔNG". Để đạt được $O(log n)$, chúng ta thường phải chia đôi mảng liên tiếp, nhưng điều đó vô nghĩa với một mảng chưa được sắp xếp. Việc chia đôi chỉ có tác dụng khi mảng đã được sắp xếp sẵn. Và nếu mảng đã sắp xếp, bạn chỉ cần lấy phần tử đầu và cuối, khi đó độ phức tạp chỉ còn là $O(1)$.

2. Trong đoạn mã trên, có bao nhiêu phần tử được duyệt? Vòng lặp for chạy bao nhiêu lần?

Câu trả lời hiển nhiên là toàn bộ phần tử đều được duyệt. Nếu gọi số lượng phần tử là $N$, vòng lặp sẽ lặp lại đúng $N$ lần.

3. Bạn có thể tìm số lớn nhất và số lớn thứ hai không?

Tất nhiên là có. Cách tìm số lớn thứ hai gần như tương tự với quy trình trên. Thay vì biến tìm số nhỏ nhất, ta dùng một biến để lưu số lớn thứ hai và thay đổi điều kiện so sánh.

Tìm số lớn thứ hai trong mảng:

public static void printSecondMaxNumbers(int[] numbers) {
  int largest = Integer.MIN_VALUE;
  int secondLargest = Integer.MIN_VALUE;
  
  for (int number : numbers) {
      if (number > largest) {
          secondLargest = largest;
          largest = number;
      } else if (number > secondLargest && number != largest) {
          secondLargest = number;
      }
  }

  System.out.println(String.format("%d là số lớn thứ hai", secondLargest));
  System.out.println(String.format("%d là số lớn nhất", largest));
}
Mẹo nhỏ: Trong thực tế, khi tìm cả Min và Max cùng lúc trong một vòng lặp, độ phức tạp vẫn là $O(n)$ nhưng bạn có thể tối ưu số lần so sánh bằng cách so sánh các cặp phần tử với nhau trước.
Nguồn bài viết ryukato.github.io