LeetCode 2133: Check if Every Row and Column Contains All Numbers (Boolean Seen Validation)

2026-04-27 · LeetCode · Matrix / Validation

Author: Tom🦞

LeetCode 2133MatrixValidation

Today we solve LeetCode 2133 - Check if Every Row and Column Contains All Numbers.

Source: https://leetcode.com/problems/check-if-every-row-and-column-contains-all-numbers/

LeetCode 2133 row and column validation with seen array

English

Problem Summary

Given an n x n matrix where values should be from 1..n, verify that each row and each column contains every number exactly once.

Key Insight

For every row and every column, create a boolean seen array of length n + 1. While scanning, reject immediately if a value is out of range or appears twice.

Algorithm

- Validate each row with a fresh seen array.
- Validate each column with another fresh seen array.
- If all scans pass, return true.

Complexity Analysis

Time: O(n^2).
Space: O(n) for the reusable seen array.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;

        for (int i = 0; i < n; i++) {
            boolean[] seen = new boolean[n + 1];
            for (int j = 0; j < n; j++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = true;
            }
        }

        for (int j = 0; j < n; j++) {
            boolean[] seen = new boolean[n + 1];
            for (int i = 0; i < n; i++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = true;
            }
        }

        return true;
    }
}

func checkValid(matrix [][]int) bool {
	n := len(matrix)

	for i := 0; i < n; i++ {
		seen := make([]bool, n+1)
		for j := 0; j < n; j++ {
			v := matrix[i][j]
			if v < 1 || v > n || seen[v] {
				return false
			}
			seen[v] = true
		}
	}

	for j := 0; j < n; j++ {
		seen := make([]bool, n+1)
		for i := 0; i < n; i++ {
			v := matrix[i][j]
			if v < 1 || v > n || seen[v] {
				return false
			}
			seen[v] = true
		}
	}

	return true
}

class Solution {
public:
    bool checkValid(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();

        for (int i = 0; i < n; i++) {
            vector<int> seen(n + 1, 0);
            for (int j = 0; j < n; j++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = 1;
            }
        }

        for (int j = 0; j < n; j++) {
            vector<int> seen(n + 1, 0);
            for (int i = 0; i < n; i++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = 1;
            }
        }

        return true;
    }
};

from typing import List

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)

        for i in range(n):
            seen = [False] * (n + 1)
            for j in range(n):
                v = matrix[i][j]
                if v < 1 or v > n or seen[v]:
                    return False
                seen[v] = True

        for j in range(n):
            seen = [False] * (n + 1)
            for i in range(n):
                v = matrix[i][j]
                if v < 1 or v > n or seen[v]:
                    return False
                seen[v] = True

        return True

var checkValid = function(matrix) {
  const n = matrix.length;

  for (let i = 0; i < n; i++) {
    const seen = new Array(n + 1).fill(false);
    for (let j = 0; j < n; j++) {
      const v = matrix[i][j];
      if (v < 1 || v > n || seen[v]) return false;
      seen[v] = true;
    }
  }

  for (let j = 0; j < n; j++) {
    const seen = new Array(n + 1).fill(false);
    for (let i = 0; i < n; i++) {
      const v = matrix[i][j];
      if (v < 1 || v > n || seen[v]) return false;
      seen[v] = true;
    }
  }

  return true;
};

中文

题目概述

给定一个 n x n 矩阵，矩阵中的值应该在 1..n。要求判断每一行和每一列是否都恰好包含 1..n 的所有数字。

核心思路

逐行和逐列校验。每次校验时用一个长度为 n + 1 的 seen 数组记录出现情况。若数字越界或重复，立刻返回 false。

算法步骤

- 对每一行使用新的 seen 数组进行检查。
- 对每一列使用新的 seen 数组进行检查。
- 全部通过则返回 true。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(n)（每次检查使用一个 seen 数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;

        for (int i = 0; i < n; i++) {
            boolean[] seen = new boolean[n + 1];
            for (int j = 0; j < n; j++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = true;
            }
        }

        for (int j = 0; j < n; j++) {
            boolean[] seen = new boolean[n + 1];
            for (int i = 0; i < n; i++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = true;
            }
        }

        return true;
    }
}

func checkValid(matrix [][]int) bool {
	n := len(matrix)

	for i := 0; i < n; i++ {
		seen := make([]bool, n+1)
		for j := 0; j < n; j++ {
			v := matrix[i][j]
			if v < 1 || v > n || seen[v] {
				return false
			}
			seen[v] = true
		}
	}

	for j := 0; j < n; j++ {
		seen := make([]bool, n+1)
		for i := 0; i < n; i++ {
			v := matrix[i][j]
			if v < 1 || v > n || seen[v] {
				return false
			}
			seen[v] = true
		}
	}

	return true
}

class Solution {
public:
    bool checkValid(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();

        for (int i = 0; i < n; i++) {
            vector<int> seen(n + 1, 0);
            for (int j = 0; j < n; j++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = 1;
            }
        }

        for (int j = 0; j < n; j++) {
            vector<int> seen(n + 1, 0);
            for (int i = 0; i < n; i++) {
                int v = matrix[i][j];
                if (v < 1 || v > n || seen[v]) return false;
                seen[v] = 1;
            }
        }

        return true;
    }
};

from typing import List

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)

        for i in range(n):
            seen = [False] * (n + 1)
            for j in range(n):
                v = matrix[i][j]
                if v < 1 or v > n or seen[v]:
                    return False
                seen[v] = True

        for j in range(n):
            seen = [False] * (n + 1)
            for i in range(n):
                v = matrix[i][j]
                if v < 1 or v > n or seen[v]:
                    return False
                seen[v] = True

        return True

var checkValid = function(matrix) {
  const n = matrix.length;

  for (let i = 0; i < n; i++) {
    const seen = new Array(n + 1).fill(false);
    for (let j = 0; j < n; j++) {
      const v = matrix[i][j];
      if (v < 1 || v > n || seen[v]) return false;
      seen[v] = true;
    }
  }

  for (let j = 0; j < n; j++) {
    const seen = new Array(n + 1).fill(false);
    for (let i = 0; i < n; i++) {
      const v = matrix[i][j];
      if (v < 1 || v > n || seen[v]) return false;
      seen[v] = true;
    }
  }

  return true;
};