Пошук найбільшої нульової підматриці

Вам задано матрицю з n рядків та m стовпців. Знайдіть найбільшу підматрицю, що складається лише з нулів (підматриця — це прямокутна область матриці).

Коли підходить цей алгоритм?

• Чи шукаєте ви найбільшу за площею прямокутну (вирівняну по осях) підматрицю з однакових елементів (нулів)?
• Чи можна звести задачу до серії гістограм по рядках, де для кожного рядка треба знайти найбільший прямокутник? (якщо ні → потрібен інший підхід до геометрії області)
• Чи влаштовує складність $O(nm)$ зі застосуванням стека для найбільшого прямокутника в гістограмі?

Алгоритм

Елементи матриці позначатимемо як a[i][j], де i = 0...n - 1, j = 0... m - 1. Для простоти вважатимемо всі ненульові елементи рівними 1.

Крок 1: Допоміжна динаміка

Спочатку обчислимо таку допоміжну матрицю: d[i][j] — найближчий рядок, у якому є 1 над a[i][j]. Формально кажучи, d[i][j] — це найбільший номер рядка (від 0 до i - 1), у якому в j-му стовпці є елемент, рівний 1. Проходячи зліва-вгорі вправо-вниз, коли ми стоїмо в рядку i, ми знаємо значення з попереднього рядка, тож достатньо оновити лише елементи зі значенням 1. Ми можемо зберігати значення у простому масиві d[i], i = 1...m - 1, бо в подальшому алгоритмі ми оброблятимемо матрицю по одному рядку за раз і потребуватимемо лише значень поточного рядка.

C++

vector<int> d(m, -1);
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        if (a[i][j] == 1) {
            d[j] = i;
        }
    }
}

Python

# d[j] — найближчий зверху рядок, у якому в j-му стовпці стоїть 1 (інакше -1).
d = [-1] * m
for i in range(n):
    for j in range(m):
        if a[i][j] == 1:
            d[j] = i

TypeScript

// d[j] — найближчий зверху рядок, у якому в j-му стовпці стоїть 1 (інакше -1).
const d: number[] = new Array(m).fill(-1);
for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
        if (a[i][j] === 1) {
            d[j] = i;
        }
    }
}

Go

// d[j] — найближчий зверху рядок, у якому в j-му стовпці стоїть 1 (інакше -1).
d := make([]int, m)
for j := range d {
    d[j] = -1
}
for i := 0; i < n; i++ {
    for j := 0; j < m; j++ {
        if a[i][j] == 1 {
            d[j] = i
        }
    }
}

Крок 2: Розв'язання задачі

Ми можемо розв'язати задачу за $O(n m^2)$, проходячи по рядках і розглядаючи кожну можливу пару лівого та правого стовпців підматриці. Низом прямокутника буде поточний рядок, а за допомогою d[i][j] ми можемо знайти верхній рядок. Однак можна піти далі й суттєво покращити складність розв'язку.

Зрозуміло, що шукана нульова підматриця обмежена з усіх чотирьох боків якимись одиницями, які заважають їй збільшуватися в розмірі та покращувати відповідь. Тому ми не пропустимо відповідь, якщо діятимемо так: для кожної комірки j у рядку i (нижній рядок потенційної нульової підматриці) ми матимемо d[i][j] як верхній рядок поточної нульової підматриці. Тепер залишається визначити оптимальні ліву та праву межі нульової підматриці, тобто максимально розширити цю підматрицю вліво та вправо від j-го стовпця.

Що означає максимально розширити вліво? Це означає знайти індекс k1, для якого d[i][k1] > d[i][j], і водночас k1 — найближчий ліворуч від індексу j. Зрозуміло, що тоді k1 + 1 дає номер лівого стовпця шуканої нульової підматриці. Якщо ж такого індексу взагалі немає, то покладемо k1 = -1 (це означає, що нам вдалося розширити поточну нульову підматрицю вліво аж до межі матриці a).

Симетрично можна визначити індекс k2 для правої межі: це найближчий праворуч від j індекс такий, що d[i][k2] > d[i][j] (або m, якщо такого індексу немає).

Отже, індекси k1 та k2, якщо ми навчимося ефективно їх шукати, дадуть нам усю необхідну інформацію про поточну нульову підматрицю. Зокрема, її площа дорівнюватиме (i - d[i][j]) * (k2 - k1 - 1).

Як ефективно шукати ці індекси k1 та k2 при фіксованих i та j? Ми можемо робити це в середньому за $O(1)$.

Щоб досягти такої складності, можна скористатися стеком так. Спершу навчимося шукати індекс k1 і зберігати його значення для кожного індексу j у межах поточного рядка i в матриці d1[i][j]. Для цього ми переглядатимемо всі стовпці j зліва направо й зберігатимемо у стеку лише ті стовпці, у яких d[][] строго більше за d[i][j]. Зрозуміло, що при переході від стовпця j до наступного стовпця необхідно оновити вміст стека. Коли на вершині стека є невідповідний елемент (тобто d[][] <= d[i][j]), виштовхуємо його. Легко зрозуміти, що достатньо видаляти зі стека лише з його вершини і з жодного іншого місця (бо стек міститиме зростаючу за d послідовність стовпців).

Значення d1[i][j] для кожного j дорівнюватиме значенню, яке в той момент лежить на вершині стека.

Динаміка d2[i][j] для пошуку індексів k2 розглядається аналогічно, лише потрібно переглядати стовпці справа наліво.

Зрозуміло, що оскільки на кожному рядку до стека додається рівно m елементів, видалень також не може бути більше, тож сума складностей буде лінійною, отже остаточна складність алгоритму — $O(nm)$.

Слід також зауважити, що цей алгоритм споживає $O(m)$ пам'яті (не рахуючи вхідних даних — матриці a[][]).

Реалізація

C++

int zero_matrix(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();

    int ans = 0;
    vector<int> d(m, -1), d1(m), d2(m);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 1)
                d[j] = i;
        }

        for (int j = 0; j < m; ++j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d1[j] = st.empty() ? -1 : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d2[j] = st.empty() ? m : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = 0; j < m; ++j)
            ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
    }
    return ans;
}

Python

def zero_matrix(a: list[list[int]]) -> int:
    n = len(a)
    m = len(a[0])

    ans = 0
    d = [-1] * m   # верхня межа: рядок останньої 1 у стовпці
    d1 = [0] * m   # індекс k1 (ліва межа) для кожного стовпця
    d2 = [0] * m   # індекс k2 (права межа) для кожного стовпця
    st: list[int] = []  # стек індексів стовпців (звичайний list)
    for i in range(n):
        for j in range(m):
            if a[i][j] == 1:
                d[j] = i

        # Прохід зліва направо: знаходимо найближчий ліворуч стовпець із більшим d.
        st.clear()
        for j in range(m):
            while st and d[st[-1]] <= d[j]:
                st.pop()
            d1[j] = -1 if not st else st[-1]
            st.append(j)

        # Прохід справа наліво: знаходимо найближчий праворуч стовпець із більшим d.
        st.clear()
        for j in range(m - 1, -1, -1):
            while st and d[st[-1]] <= d[j]:
                st.pop()
            d2[j] = m if not st else st[-1]
            st.append(j)

        for j in range(m):
            ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1))
    return ans

TypeScript

function zeroMatrix(a: number[][]): number {
    const n = a.length;
    const m = a[0].length;

    let ans = 0;
    const d: number[] = new Array(m).fill(-1); // верхня межа: рядок останньої 1 у стовпці
    const d1: number[] = new Array(m).fill(0); // індекс k1 (ліва межа)
    const d2: number[] = new Array(m).fill(0); // індекс k2 (права межа)
    const st: number[] = []; // стек індексів стовпців (масив)
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (a[i][j] === 1)
                d[j] = i;
        }

        // Прохід зліва направо: найближчий ліворуч стовпець із більшим d.
        st.length = 0;
        for (let j = 0; j < m; ++j) {
            while (st.length > 0 && d[st[st.length - 1]] <= d[j])
                st.pop();
            d1[j] = st.length === 0 ? -1 : st[st.length - 1];
            st.push(j);
        }

        // Прохід справа наліво: найближчий праворуч стовпець із більшим d.
        st.length = 0;
        for (let j = m - 1; j >= 0; --j) {
            while (st.length > 0 && d[st[st.length - 1]] <= d[j])
                st.pop();
            d2[j] = st.length === 0 ? m : st[st.length - 1];
            st.push(j);
        }

        for (let j = 0; j < m; ++j)
            ans = Math.max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
    }
    return ans;
}

Go

func zeroMatrix(a [][]int) int {
    n := len(a)
    m := len(a[0])

    ans := 0
    d := make([]int, m)  // верхня межа: рядок останньої 1 у стовпці
    d1 := make([]int, m) // індекс k1 (ліва межа)
    d2 := make([]int, m) // індекс k2 (права межа)
    for j := range d {
        d[j] = -1
    }
    st := []int{} // стек індексів стовпців (слайс)
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if a[i][j] == 1 {
                d[j] = i
            }
        }

        // Прохід зліва направо: найближчий ліворуч стовпець із більшим d.
        st = st[:0]
        for j := 0; j < m; j++ {
            for len(st) > 0 && d[st[len(st)-1]] <= d[j] {
                st = st[:len(st)-1]
            }
            if len(st) == 0 {
                d1[j] = -1
            } else {
                d1[j] = st[len(st)-1]
            }
            st = append(st, j)
        }

        // Прохід справа наліво: найближчий праворуч стовпець із більшим d.
        st = st[:0]
        for j := m - 1; j >= 0; j-- {
            for len(st) > 0 && d[st[len(st)-1]] <= d[j] {
                st = st[:len(st)-1]
            }
            if len(st) == 0 {
                d2[j] = m
            } else {
                d2[j] = st[len(st)-1]
            }
            st = append(st, j)
        }

        for j := 0; j < m; j++ {
            if area := (i - d[j]) * (d2[j] - d1[j] - 1); area > ans {
                ans = area
            }
        }
    }
    return ans
}

Відеоматеріали