Задача: 1253. Reconstruct a 2-Row Binary Matrix
Сложность: medium

Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower.
Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив.

Пример:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]

👨‍💻 Алгоритм:

1⃣Инициализируйте две строки матрицы длины n с нулями.

2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower.
Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower.

3⃣Проверьте, что остатки upper и lower равны нулю.
Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.

😎 Решение:

class Solution {
    fun reconstructMatrix(upper: Int, lower: Int, colsum: IntArray): List<List<Int>> {
        var upper = upper
        var lower = lower
        val n = colsum.size
        val top = IntArray(n)
        val bottom = IntArray(n)

        for (i in colsum.indices) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    top[i] = 1
                    bottom[i] = 1
                    upper--
                    lower--
                } else {
                    return emptyList()
                }
            }
        }

        for (i in colsum.indices) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1
                        upper--
                    } else {
                        return emptyList()
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1
                        lower--
                    } else {
                        return emptyList()
                    }
                }
            }
        }

        if (upper == 0 && lower == 0) {
            return listOf(top.toList(), bottom.toList())
        } else {
            return emptyList()
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний