OR in Matrix · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Matrices

Greedy

OR in Matrix

Reconstruct a binary matrix from the matrix of OR-values over all rows and columns.

Acceptance 0%

Start Practice

Problem Statement

You are given an $n \times m$ matrix $B$ consisting of $0 $and \$ 1$.

Interpret $B$ as the result of the following process on an unknown binary matrix $A$ of the same size:

If $B[i][j] = 1$ , then every cell in row $i$ and every cell in column $j$ of $A$ must be $1$.
If $B[i][j] = 0$ , then there must be at least one cell equal to $0 $in row$ i $and at least one cell equal to \$ 0 $in column$ j$.

Your task is to determine whether such a binary matrix $A$ exists. If it exists, output one valid matrix; otherwise, report that it is impossible.

This is the classic reconstruction task behind the "OR in Matrix" problem.

Input Format

The first line contains two integers $n$ and $m$ .
The next $n$ lines contain $m$ integers each, describing matrix $B$ .

The exact official limits are not repeated here; solve for a general $n \times m$ binary matrix.

Output Format

If no valid matrix exists, output NO.
Otherwise output YES followed by any valid $n \times m$ binary matrix $A`.

A valid matrix should satisfy all constraints implied by $B$ .

Constraints

$1 \le n, m$
$B[i][j] \in \{0,1\}$
Output any one valid solution if it exists.

Examples

Sample cases returned by the problem API.

Example 1

Input

2 2
1 1
1 1

Output

YES
1 1
1 1

Explanation

All entries in $B$ are 1, so the all-ones matrix is a valid reconstruction.

Example 2

Input

Output

NO

Explanation

The center cell is 0, so its row and column must each contain a 0. That would force additional zeros in $B$ , so this configuration cannot come from any valid binary matrix.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress