Jobs

Interviews

Discussions

Matrix Diagonal Sum

Easy

Asked by:

More companies

38 views

Topics:

Arrays

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Constraints:

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

Try coding it in LeetCode

Matrix Diagonal Sum

Easy

Asked by:

38 views

Topics:

Arrays

Given a square matrix mat, return the sum of the matrix diagonals.

Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal.

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

Constraints:

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size (number of rows/columns) of the input matrix `mat`?
Can the elements within the matrix `mat` be negative, zero, or non-integer values?
Could you please clarify what should be returned if the input matrix `mat` is empty or null?
Is the input matrix `mat` guaranteed to be a square matrix (number of rows equals the number of columns)?
For the case where the matrix has an odd number of rows/columns, is it correct that the center element which lies on both diagonals should only be added to the sum once?

Brute Force Solution

Approach

The brute force method to find the sum of diagonals in a square grid means we'll go through the grid and check every possible cell that could be on either of the diagonals. We'll add the values of those cells together to get our final answer.

Here's how the algorithm would work step-by-step:

Start at the top-left corner of the grid.
See if this corner cell is part of the main diagonal (the one going from top-left to bottom-right). If it is, remember the number in that cell.
Also, see if the top-left corner is part of the other diagonal (the one going from top-right to bottom-left). If it is, and it's a different cell than the one we already looked at, remember that number too.
Move to the next cell in the grid, going row by row and column by column.
For each cell, repeat the checks: is it on the main diagonal? Is it on the other diagonal (and not the same cell as one we've already counted)? If so, remember the number.
Keep doing this until you've checked every single cell in the grid.
Finally, add up all the numbers you remembered from the diagonal cells to find the total diagonal sum.

Code Implementation

def matrix_diagonal_sum_brute_force(matrix):
    grid_size = len(matrix)
    diagonal_sum = 0

    for row_index in range(grid_size):
        for column_index in range(grid_size):
            # Check for main diagonal (top-left to bottom-right)
            if row_index == column_index:
                diagonal_sum += matrix[row_index][column_index]

            # Check for anti-diagonal (top-right to bottom-left), avoid double counting
            if row_index + column_index == grid_size - 1 and row_index != column_index:
                diagonal_sum += matrix[row_index][column_index]

    return diagonal_sum

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through each cell of the n x n matrix. For every cell, it performs constant time operations to determine if it lies on either of the diagonals. Since we visit each of the n x n cells in the grid to perform these checks, the total number of operations is proportional to n * n. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The described brute force method iterates through the matrix without using any auxiliary data structures. It only keeps track of the current cell being processed and a running sum. Thus, the space required does not depend on the size of the matrix (N), and it remains constant.

Optimal Solution

Approach

The goal is to sum the numbers found on the main and anti-diagonal of a square grid of numbers. The clever approach is to traverse the grid once and selectively add numbers to the running total. A simple adjustment avoids double-counting the center element if the grid's side length is odd.

Here's how the algorithm would work step-by-step:

Begin by setting your running total to zero.
Go through each position in the grid in a systematic way.
If a position is on the main diagonal, add its number to the running total.
If a position is on the anti-diagonal, add its number to the running total.
If the grid has an odd number of rows and columns, you'll have counted the very center number twice. Reduce your total by the value of the center position to correct for the over-counting.
The final result is the sum of all the numbers on the two diagonals without double counting.

Code Implementation

def matrix_diagonal_sum(matrix):
    grid_size = len(matrix)
    diagonal_sum = 0

    for row_index in range(grid_size):
        # Add the main diagonal element.
        diagonal_sum += matrix[row_index][row_index]

        # Add the anti-diagonal element.
        diagonal_sum += matrix[row_index][grid_size - 1 - row_index]

    # Correct for double counting if grid size is odd.
    if grid_size % 2 != 0:
        center_index = grid_size // 2
        diagonal_sum -= matrix[center_index][center_index]

    return diagonal_sum

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is iterating through the matrix. We visit each row (n rows), and within each row, we implicitly access an element based on row and column indexes to check if it's on the main or anti-diagonal. Therefore, the number of operations scales directly with the number of rows (n). The final adjustment for the center element is a constant time operation and does not affect the overall time complexity. Thus, the time complexity is O(n).

Space Complexity

O(1) – The algorithm only uses a few integer variables: one to store the running total and potentially a loop counter. The number of integer variables does not depend on the size of the input matrix. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or undefined input matrix	Return 0 or throw an IllegalArgumentException to avoid NullPointerException.
Empty matrix (matrix with zero rows)	Return 0 as there are no diagonal elements to sum.
Matrix with only one element (1x1 matrix)	Return the value of the single element, as it's on both diagonals.
Matrix with negative numbers	The solution should handle negative numbers correctly as the problem statement allows integer values.
Large matrix (e.g., 1000x1000) to test for performance	The solution should have O(n) time complexity where n is the size of one dimension, making it scalable.
Matrix with all elements being zero	The sum should be 0, handled correctly by the summation logic.
Matrix with extremely large integer values close to Integer.MAX_VALUE	Consider using long data type for the sum to prevent integer overflow.
Non-square matrix	The problem states it receives a 'square matrix' so either throw an error, or adjust to consider diagonals until we reach either row or col end if they are different

Null or undefined input matrix

How to Handle:

Return 0 or throw an IllegalArgumentException to avoid NullPointerException.

Empty matrix (matrix with zero rows)

How to Handle:

Return 0 as there are no diagonal elements to sum.

Matrix with only one element (1x1 matrix)

How to Handle:

Return the value of the single element, as it's on both diagonals.

Matrix with negative numbers

How to Handle:

The solution should handle negative numbers correctly as the problem statement allows integer values.

Large matrix (e.g., 1000x1000) to test for performance

How to Handle:

The solution should have O(n) time complexity where n is the size of one dimension, making it scalable.

Matrix with all elements being zero

How to Handle:

The sum should be 0, handled correctly by the summation logic.

Matrix with extremely large integer values close to Integer.MAX_VALUE

How to Handle:

Consider using long data type for the sum to prevent integer overflow.

Non-square matrix

How to Handle:

The problem states it receives a 'square matrix' so either throw an error, or adjust to consider diagonals until we reach either row or col end if they are different

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size (number of rows/columns) of the input matrix `mat`?
Can the elements within the matrix `mat` be negative, zero, or non-integer values?
Could you please clarify what should be returned if the input matrix `mat` is empty or null?
Is the input matrix `mat` guaranteed to be a square matrix (number of rows equals the number of columns)?
For the case where the matrix has an odd number of rows/columns, is it correct that the center element which lies on both diagonals should only be added to the sum once?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top-left corner of the grid.
See if this corner cell is part of the main diagonal (the one going from top-left to bottom-right). If it is, remember the number in that cell.
Also, see if the top-left corner is part of the other diagonal (the one going from top-right to bottom-left). If it is, and it's a different cell than the one we already looked at, remember that number too.
Move to the next cell in the grid, going row by row and column by column.
For each cell, repeat the checks: is it on the main diagonal? Is it on the other diagonal (and not the same cell as one we've already counted)? If so, remember the number.
Keep doing this until you've checked every single cell in the grid.
Finally, add up all the numbers you remembered from the diagonal cells to find the total diagonal sum.

Code Implementation

def matrix_diagonal_sum_brute_force(matrix):
    grid_size = len(matrix)
    diagonal_sum = 0

    for row_index in range(grid_size):
        for column_index in range(grid_size):
            # Check for main diagonal (top-left to bottom-right)
            if row_index == column_index:
                diagonal_sum += matrix[row_index][column_index]

            # Check for anti-diagonal (top-right to bottom-left), avoid double counting
            if row_index + column_index == grid_size - 1 and row_index != column_index:
                diagonal_sum += matrix[row_index][column_index]

    return diagonal_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin by setting your running total to zero.
Go through each position in the grid in a systematic way.
If a position is on the main diagonal, add its number to the running total.
If a position is on the anti-diagonal, add its number to the running total.
If the grid has an odd number of rows and columns, you'll have counted the very center number twice. Reduce your total by the value of the center position to correct for the over-counting.
The final result is the sum of all the numbers on the two diagonals without double counting.

Code Implementation

def matrix_diagonal_sum(matrix):
    grid_size = len(matrix)
    diagonal_sum = 0

    for row_index in range(grid_size):
        # Add the main diagonal element.
        diagonal_sum += matrix[row_index][row_index]

        # Add the anti-diagonal element.
        diagonal_sum += matrix[row_index][grid_size - 1 - row_index]

    # Correct for double counting if grid size is odd.
    if grid_size % 2 != 0:
        center_index = grid_size // 2
        diagonal_sum -= matrix[center_index][center_index]

    return diagonal_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or undefined input matrix	Return 0 or throw an IllegalArgumentException to avoid NullPointerException.
Empty matrix (matrix with zero rows)	Return 0 as there are no diagonal elements to sum.
Matrix with only one element (1x1 matrix)	Return the value of the single element, as it's on both diagonals.
Matrix with negative numbers	The solution should handle negative numbers correctly as the problem statement allows integer values.
Large matrix (e.g., 1000x1000) to test for performance	The solution should have O(n) time complexity where n is the size of one dimension, making it scalable.
Matrix with all elements being zero	The sum should be 0, handled correctly by the summation logic.
Matrix with extremely large integer values close to Integer.MAX_VALUE	Consider using long data type for the sum to prevent integer overflow.
Non-square matrix	The problem states it receives a 'square matrix' so either throw an error, or adjust to consider diagonals until we reach either row or col end if they are different

Null or undefined input matrix

How to Handle:

Return 0 or throw an IllegalArgumentException to avoid NullPointerException.

Empty matrix (matrix with zero rows)

How to Handle:

Return 0 as there are no diagonal elements to sum.

Matrix with only one element (1x1 matrix)

How to Handle:

Return the value of the single element, as it's on both diagonals.

Matrix with negative numbers

How to Handle:

The solution should handle negative numbers correctly as the problem statement allows integer values.

Large matrix (e.g., 1000x1000) to test for performance

How to Handle:

The solution should have O(n) time complexity where n is the size of one dimension, making it scalable.

Matrix with all elements being zero

How to Handle:

The sum should be 0, handled correctly by the summation logic.

Matrix with extremely large integer values close to Integer.MAX_VALUE

How to Handle:

Consider using long data type for the sum to prevent integer overflow.

Non-square matrix

How to Handle:

The problem states it receives a 'square matrix' so either throw an error, or adjust to consider diagonals until we reach either row or col end if they are different