Leetcode 2133: Check if Every Row and Column Contains All Numbers

In this problem, we are trying to find out in a 2-dimension if every number from 1 to n is in each row and each column:

An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive).
Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.

Two examples that we can use for testing:

Examples

How do we solve this effectively? Here, I am trying to do O(n²), but also would like to return an answer in one pass.

In my solution, I set 2 n*n boolean arrays, rows and cols:

rows[i][x] is true if we have seen the number (x+1) in the row i.
cols[j][x] is true if we have seen the number (x+1) in the column j.

By filling these arrays as we go, we are trying to identify if there is any row or any column that has 2 values that are the same. If we find such example, we return false. We can show easily that if this doesn’t happen, then by the end of the array traversal, both arrays are full and we return true then.

Algorithm ideas