1. Tích của mảng ngoại trừ chính nó (Product of Array Except Self)

Bài toán yêu cầu tính toán một mảng kết quả answer sao cho answer[i] bằng tích của tất cả các phần tử trong mảng đầu vào ngoại trừ phần tử tại vị trí i. Ràng buộc quan trọng là không được sử dụng phép chia và thuật toán phải chạy trong độ phức tạp thời gian O(n).

Giải pháp tối ưu không gian O(1)

Để đạt được độ phức tạp không gian hằng số (không tính mảng kết quả), chúng ta có thể tận dụng mảng kết quả để lưu trữ các giá trị tích lũy tạm thời. Quá trình thực hiện chia làm hai lượt duyệt:

1. Lượt duyệt xuôi: Tính tích của tất cả các phần tử bên trái của chỉ số hiện tại.
2. Lượt duyệt ngược: Tính tích của tất cả các phần tử bên phải và nhân trực tiếp vào giá trị đã có trong mảng kết quả.

class Solution {
    public int[] productExceptSelf(int[] data) {
        int size = data.length;
        int[] output = new int[size];

        // Bước 1: Tính tích các phần tử bên trái (Prefix Product)
        output[0] = 1;
        for (int i = 1; i < size; i++) {
            output[i] = output[i - 1] * data[i - 1];
        }

        // Bước 2: Tính tích các phần tử bên phải (Suffix Product) và cập nhật kết quả
        int rightMultiplier = 1;
        for (int i = size - 1; i >= 0; i--) {
            output[i] = output[i] * rightMultiplier;
            rightMultiplier *= data[i];
        }

        return output;
    }
}

2. Đặt các hàng và cột trong ma trận thành số không (Set Matrix Zeroes)

Cho một ma trận kích thước m x n, nếu một phần tử bằng 0, ta phải đặt toàn bộ hàng và cột chứa phần tử đó về 0. Thử thách ở đây là thực hiện thuật toán ngay trên ma trận gốc (in-place) để tiết kiệm không gian bộ nhớ.

Phương pháp sử dụng mảng đánh dấu O(m + n)

Cách tiếp cận đơn giản nhất là sử dụng hai mảng phụ để ghi nhớ các hàng và cột cần xóa. Sau đó, duyệt lại ma trận một lần nữa để cập nhật giá trị.

class Solution {
    public void setZeroes(int[][] grid) {
        int rowCount = grid.length;
        int colCount = grid[0].length;
        boolean[] targetRows = new boolean[rowCount];
        boolean[] targetCols = new boolean[colCount];

        for (int r = 0; r < rowCount; r++) {
            for (int c = 0; c < colCount; c++) {
                if (grid[r][c] == 0) {
                    targetRows[r] = true;
                    targetCols[c] = true;
                }
            }
        }

        for (int r = 0; r < rowCount; r++) {
            for (int c = 0; c < colCount; c++) {
                if (targetRows[r] || targetCols[c]) {
                    grid[r][c] = 0;
                }
            }
        }
    }
}

Phương pháp tối ưu không gian O(1)

Để không sử dụng thêm mảng phụ, ta có thể dùng chính hàng đầu tiên và cột đầu tiên của ma trận làm nơi lưu trữ trạng thái đánh dấu. Tuy nhiên, cần hai biến cờ hiệu để kiểm tra xem bản thân hàng đầu tiên và cột đầu tiên có chứa số 0 ban đầu hay không.

class Solution {
    public void setZeroes(int[][] matrix) {
        int R = matrix.length;
        int C = matrix[0].length;
        boolean firstRowHasZero = false;
        boolean firstColHasZero = false;

        // Kiểm tra cột đầu tiên
        for (int i = 0; i < R; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // Kiểm tra hàng đầu tiên
        for (int j = 0; j < C; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Sử dụng hàng/cột đầu tiên làm mảng đánh dấu cho phần còn lại
        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Cập nhật các ô dựa trên đánh dấu
        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Xử lý nốt hàng và cột đầu tiên
        if (firstColHasZero) {
            for (int i = 0; i < R; i++) matrix[i][0] = 0;
        }
        if (firstRowHasZero) {
            for (int j = 0; j < C; j++) matrix[0][j] = 0;
        }
    }
}