Skip to content

Diagonal

LeWiz24 edited this page Aug 21, 2024 · 4 revisions

"TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • Time to complete: 10 mins
  • 🛠️ Topics: Matrices, Diagonals

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the function?

    • A: The input is an n x n matrix grid.
  • Q: What is the expected output of the function?

    • A: The function should return an integer representing the sum of all elements on the primary diagonal and the secondary diagonal, excluding any element that is counted twice.
  • Q: What are the primary and secondary diagonals?

    • A:
      • The primary diagonal consists of elements from the top-left to the bottom-right of the matrix (i.e., grid[i][i] for all i).
      • The secondary diagonal consists of elements from the top-right to the bottom-left of the matrix (i.e., grid[i][n-1-i] for all i).
  • Q: What if the matrix has only one element?

    • A: If the matrix is 1 x 1, the function should return the value of that single element.
  • Q: How should the function handle the center element in an odd-sized matrix?

    • A: In an odd-sized matrix, the center element is part of both diagonals, so it should only be counted once.

P-lan

  • The function diagonal_sum() should take a 2D n x n matrix grid and return the sum of the primary and secondary diagonals. The center element should be counted only once if it is part of both diagonals.
HAPPY CASE
Input: [    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
Expected Output: 25

Input: [    [1, 1, 1, 1],
    [1, 1, 1, 1],
    [1, 1, 1, 1],
    [1, 1, 1, 1]
]
Expected Output: 8

EDGE CASE
Input: [    [5]
]
Expected Output: 5

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the matrix to sum the elements on the primary diagonal and the secondary diagonal, avoiding double counting the center element if n is odd.

1. Initialize `total_sum` to 0.
2. Get the size of the matrix `n`.
3. Iterate through the matrix with index `i` from 0 to `n-1`.
   - Add `grid[i][i]` to `total_sum` (primary diagonal).
   - If `i` is not the center element, add `grid[i][n-1-i]` to `total_sum` (secondary diagonal).
4. Return `total_sum`

⚠️ Common Mistakes

  • Double counting the center element if n is odd.
  • Misindexing elements on the secondary diagonal.

I-mplement

Implement the code to solve the algorithm.

def diagonal_sum(grid):
    n = len(grid)
    total_sum = 0
    
    for i in range(n):
        total_sum += grid[i][i]  # Primary diagonal
        if i != n - 1 - i:       # Check to avoid double counting the center element
            total_sum += grid[i][n - 1 - i]  # Secondary diagonal
    
    return total_sum
Clone this wiki locally