1253. Reconstruct a 2-Row Binary Matrix

leetcode medium

#array#csharp#leetcode#matrix#medium#string

Task

Даны следующие сведения о матрице с 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]]

C# solution

matched/original

public class Solution {
    public IList<IList<int>> 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 List<IList<int>>();
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1;
                        upper--;
                    } else {
                        return new List<IList<int>>();
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1;
                        lower--;
                    } else {
                        return new List<IList<int>>();
                    }
                }
            }
        }
        if (upper == 0 && lower == 0) {
            return new List<IList<int>> { top, bottom };
        } else {
            return new List<IList<int>>();
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> ReconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<int>& top = new int[n];
        vector<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 List<vector<int>>();
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    if (upper > 0) {
                        top[i] = 1;
                        upper--;
                    } else {
                        return new List<vector<int>>();
                    }
                } else {
                    if (lower > 0) {
                        bottom[i] = 1;
                        lower--;
                    } else {
                        return new List<vector<int>>();
                    }
                }
            }
        }
        if (upper == 0 && lower == 0) {
            return new List<vector<int>> { top, bottom };
        } else {
            return new List<vector<int>>();
        }
    }
}

Java solution

matched/original

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<>();
        }
    }
}

Python solution

matched/original

def reconstructMatrix(upper, lower, colsum):
    n = len(colsum)
    top = [0] * n
    bottom = [0] * n
    
    for i in range(n):
        if colsum[i] == 2:
            if upper > 0 and lower > 0:
                top[i] = 1
                bottom[i] = 1
                upper -= 1
                lower -= 1
            else:
                return []
    
    for i in range(n):
        if colsum[i] == 1:
            if upper > lower:
                if upper > 0:
                    top[i] = 1
                    upper -= 1
                else:
                    return []
            else:
                if lower > 0:
                    bottom[i] = 1
                    lower -= 1
                else:
                    return []

    if upper == 0 and lower == 0:
        return [top, bottom]
    else:
        return []

Explanation

Algorithm

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

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

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

Проверьте, что остатки upper и lower равны нулю.

Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.

😎