Задача: 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 равны нулю.
Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.

😎 Решение:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        int[] top = new int[n];
        int[] bottom = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    top[i] = 1;
                    bottom[i] = 1;
                    upper--;
                    lower--;
                } else {
                    return new ArrayList<>();
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1;
                        upper--;
                    } else {
                        return new ArrayList<>();
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1;
                        lower--;
                    } else {
                        return new ArrayList<>();
                    }
                }
            }
        }
        
        if (upper == 0 && lower == 0) {
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> topRow = new ArrayList<>();
            List<Integer> bottomRow = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                topRow.add(top[i]);
                bottomRow.add(bottom[i]);
            }
            result.add(topRow);
            result.add(bottomRow);
            return result;
        } else {
            return new ArrayList<>();
        }
    }
}

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