766. Toeplitz Matrix

Hello, reader 👋🏽 ! Welcome to day 15 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up a LeetCode problem: 766. Toeplitz Matrix which I got in a mock interview.

🤔 Problem Statement

• Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.

  Note: A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements. E.g.:

  • Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]], Output: true
  • Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,9,2]], Output: false

💬 Thought Process - Compare with next row element

• After observing we can figure out the pattern here: if element at position (i,j) equal to element at position (i+1, j+1) for every 0 <=i < m and 0 <= j <= n, where m = number of rows and n = number of columns.
• So that's exactly what we'll be doing. Refer to the image below for more clarity.

👩🏽‍💻 Solution - Compare with next row element

• Below is the code for the above compare with next row element approach:

  class Solution {
      public boolean isToeplitzMatrix(int[][] matrix) {
          int m = matrix.length, n = matrix[0].length;
  
          for(int i = 0; i<m-1; i++) {
              for(int j = 0; j<n; j++) {
                  int curr = matrix[i][j];
                  if(j+1 < n) {
                      int prev = matrix[i+1][j+1];
                      if(curr != prev) {
                          return false;
                      }
                  }
              }
          }
  
          return true;
      }
  }
  

  Time Complexity: O(m*n)
      - m = number of columns
      - n = number of rows
      - Since we are traversing all the nodes in the list.
  Space Complexity: O(1)
      - Since we only use temporary values to compare values in the cells.
  

💬 Thought Process - Map value to diagonalNum

• The time complexity of the above approach was the least we could do.
• But if you see we are accessing and traversing through half of the square multiple times.
• We can use extra space and group elements on the diagonal which we can get from the row and col number at each cell.
• E.g.:
  • cell at (0,0) belongs to diagonal 0-0 = 0
  • cell at (0,1) belongs to diagonal 0-1 = -1
  • cell at (0,2) belongs to diagonal 0-3 = -3
• So we can map this to a map. And when we come across the same diagonalNum we can check if the associated value from the map is same or not.
• If it does not exist, then we'll put a new key pair value associated with .

👩🏽‍💻 Solution - Map value to diagonalNum

• Below is the code for mapping value to Map value to diagonalNum approach:

  class Solution {
      public boolean isToeplitzMatrix(int[][] matrix) {
          Map<Integer, Integer> map = new HashMap();
  
          int m = matrix.length, n = matrix[0].length;
  
          for(int i = 0; i<m; i++) {
              for(int j = 0; j<n; j++) {
                  int curr = matrix[i][j];
                  int diagonalNum = i-j;
  
                  if(map.containsKey(diagonalNum)) {
                      int diagVal = map.get(diagonalNum);
                      if(diagVal != curr) {
                          return false;
                      }
                  }
                  else {
                      map.put(diagonalNum, curr);
                  }
              }
          }
          return true;
      }
  }
  

  Time Complexity: O(m*n)
      - m = number of columns
      - n = number of rows
      - Since we are traversing all the nodes in the list.
  Space Complexity: O(m+n)
      - m = number of columns
      - n = number of rows
      - At most the map will only hold m+n elements
  

You can find the code for this problem on GitHub repo: 766. Toeplitz Matrix.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!