Validate matrix complete

Question

Given a matrix, write a function to validate whether it is a complete matrix, meaning all rows except possibly the last are of the same length, and the last row has all its elements filled from the left to the right without any gaps. The function should return a boolean value indicating whether the matrix is complete.

Codemia · Accepted Answer

To determine if a matrix is complete, we need to identify its structure: all rows except possibly the last must have the same length, and the last row must be filled from left to right without any gaps. This is a clear case for a single pass through the matrix, which suggests a linear traversal pattern. We can utilize a two-pointer or single-pass strategy to check row lengths and validate contents in one go. The identifiable patterns here are:
1. Consistency in row lengths (except for the last row).
2. Complete filling of the last row from the left.

1. Initialize a variable to store the expected length of rows based on the first row of the matrix.
2. Iterate through each row of the matrix:
   - For each row, check if its length matches the expected length.
   - If it's the last row, ensure that it is filled completely from the left without any gaps.
3. If any row violates the length condition or if the last row has gaps, return False. Otherwise, return True.

**Example:** For the input matrix:
```
[
 [1, 2, 3],
 [4, 5, 6],
 [7, 8]
]
```
- The first two rows have a length of 3, but the last row has a length of 2. So, it is not complete, and the function should return False.

Here is the Python solution for the problem:
```python
def is_complete_matrix(matrix):
    if not matrix:
        return True  # An empty matrix is considered complete

expected_length = len(matrix[0])
    for i in range(len(matrix)):
        row_length = len(matrix[i])
        if i < len(matrix) - 1:
            # For all rows except the last, check if they match expected length
            if row_length != expected_length:
                return False
        else:
            # For the last row, check if filled from left to right
            if row_length > expected_length:
                return False
            for j in range(row_length):
                if matrix[i][j] is None:
                    return False  # There should be no gaps in the last row
    return True
```
This implementation directly checks the conditions while iterating through the matrix.

The time complexity of the solution is O(n), where n is the number of rows in the matrix. This is because we perform a single traversal through the matrix to validate row lengths and contents. The space complexity is O(1) since we only use a fixed amount of extra space for variables, regardless of the input matrix size. Thus, the solution is efficient in both time and space.

1. **Empty Matrix:** An empty matrix should return True as it technically has no rows to violate the completeness rule.
2. **Single Row Matrix:** A matrix with only one row should return True regardless of its length.
3. **Matrix with Gaps in Last Row:** If the last row has gaps (e.g., [1, 2, None]), it should return False.
4. **Uniform Rows Then Gaps:** For example, [[1, 2], [3, 4], [5]], should return False because the last row is shorter than the expected length. 
5. **All Rows Same Length, Last Row Not Full:** For example, [[1, 2, 3], [4, 5, 6], [7, None, None]], should return False as the last row has gaps.

Validate matrix complete

Figma

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Figma Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string