Toeplitz Matrix

🏠 ⬅️ ➡️

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

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

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true Explanation: In the above grid, the diagonals are: "[9] ", "[5, 5] ", "[1, 1, 1] ", "[2, 2, 2] ", "[3, 3] ", "[4] ". In each diagonal all elements are the same, so the answer is True.

Example 2:

Input: matrix = [[1,2],[2,2]] Output: false Explanation: The diagonal "[1, 2] " has different elements.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 20
  • 0 <= matrix[i][j] <= 99

Follow up:

  • What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
  • What if the matrix is so large that you can only load up a partial row into the memory at once?
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: m = 3, n = 4
    integer, dimension(m, n) :: matrix
    logical :: result

    ! Example 1
    matrix(:, :) = reshape([1, 2, 3, 4, &
                             5, 1, 2, 3, &
                             9, 5, 1, 2], shape(matrix))
    write(*, '(L1)') toeplitz(matrix)

    ! Example 2
    matrix(:, :) = reshape([1, 2, &
                             2, 2], shape(matrix))
    write(*, '(L1)') toeplitz(matrix)

contains

    function toeplitz(matrix) result(result)
        implicit none
        integer, intent(in) :: matrix(:, :)
        logical :: result
        integer :: i, j

        do i = 1, size(matrix, 1) - 1
            do j = 1, size(matrix, 2) - 1
                if (matrix(i, j) /= matrix(i + 1, j + 1)) then
                    result = .false.
                    return
                end if
            end do
        end do

        result = .true.
    end function toeplitz

end program main
❌ Compiled
❌ Executed
❌ Correct 
module toeplitz
implicit none
contains

function is_toeplitz(matrix) result(is_toeplitz)
integer, intent(in) :: matrix(:,:)
logical :: is_toeplitz
integer :: i, j, m, n

m = size(matrix, 1)
n = size(matrix, 2)

is_toeplitz = .true.

do i = 1, m - 1
    do j = 1, n
        if (matrix(i, j) .ne. matrix(i+1, j+1)) then
            is_toeplitz = .false.
            exit
        end if
    end do
    if (.not. is_toeplitz) exit
end do

end function is_toeplitz

end module toeplitz

program main
use toeplitz
implicit none

integer, parameter :: m = 3, n = 4
integer :: matrix(m, n) = reshape([1, 2, 3, 4, 5, 1, 2, 3, 9, 5, 1, 2], [m, n])

write (*, '(L1)') is_toeplitz(matrix)

end program main
🌐 Data from online sources 
class Node:
    def __init__(self, val=0, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head: Node) -> Node:
    if not head:
        return None

    curr = head
    while curr:
        if curr.child:
            insert = curr.child
            next_node = curr.next

            insert.prev = curr
            curr.next = insert
            curr.child = None

            while insert.next:
                insert = insert.next

            if next_node:
                next_node.prev = insert
                insert.next = next_node

        curr = curr.next

    return head

The basic idea of the algorithm is to traverse the doubly linked list and if a node has a child, we insert the child list between the current node and its next node. We do this by adjusting the previous and next pointers accordingly. After inserting the child list, we set the child pointer of the current node to null. We keep doing this for each node in the list.
🌐 Data from online sources 
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};

Node* flatten(Node* head) {
    if(!head) return nullptr;

    Node* curr = head;
    while(curr) {
        if(curr->child) {
            Node* insert = curr->child;
            Node* next = curr->next;

            insert->prev = curr;
            curr->next = insert;
            curr->child = nullptr;

            while(insert->next) insert = insert->next;

            if(next) {
                next->prev = insert;
                insert->next = next;
            }
        }
        curr = curr->next;
    }

    return head;
}

The basic idea of the algorithm is to traverse the doubly linked list and if a node has a child, we insert the child list between the current node and its next node. We do this by adjusting the previous and next pointers accordingly. After inserting the child list, we set the child pointer of the current node to null. We keep doing this for each node in the list.