Determine Whether Matrix Can Be Obtained By Rotation

🏠 ⬅️ ➡️

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]] Output: true Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]] Output: false Explanation: It is impossible to make mat equal to target by rotating mat.

Example 3:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]] Output: true Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.

Constraints:

  • n == mat.length == target.length
  • n == mat[i].length == target[i].length
  • 1 <= n <= 10
  • mat[i][j] and target[i][j] are either 0 or 1.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 2
    logical, dimension(n, n) :: mat, target, result

    ! Example 1
    mat(:, :) = reshape([0, 1, 1, 0], shape(mat))
    target(:, :) = reshape([1, 0, 0, 1], shape(target))
    write(*, '(L1)') solve(mat, target)

    ! Example 2
    mat(:, :) = reshape([0, 1, 1, 0], shape(mat))
    target(:, :) = reshape([1, 0, 0, 1], shape(target))
    write(*, '(L1)') solve(mat, target)

    ! Example 3
    mat(:, :) = reshape([0, 0, 0, 0, 0, 0, 1, 1, 1], shape(mat))
    target(:, :) = reshape([1, 1, 1, 0, 0, 0, 0, 1, 0], shape(target))
    write(*, '(L1)') solve(mat, target)

contains

    function solve(mat, target) result(res)
        implicit none
        logical, intent(in) :: mat(:, :), target(:, :)
        logical :: res

        integer :: i, j, k, l
        logical, dimension(size(mat, 1), size(mat, 2)) :: temp

        res = .false.

        do i = 1, size(mat, 1) - 1
            do j = 1, size(mat, 2) - 1
                if (mat(i, j) /= target(i, j)) then
                    cycle
                end if

                do k = 1, 3
                    temp = mat
                    call rotate(temp, k)

                    if (all(temp == target)) then
                        res = .true.
                        exit
                    end if
                end do

                if (res) then
                    exit
                end if
            end do

            if (res) then
                exit
            end if
        end do

    contains

        subroutine rotate(arr, dir)
            implicit none
            logical, intent(inout) :: arr(:, :)
            integer, intent(in) :: dir

            integer :: i, j
            logical, allocatable :: temp(:, :)

            allocate(temp(size(arr, 1), size(arr, 2)))

            select case (dir)
            case (1)
                do i = 1, size(arr, 1)
                    do j = 1, size(arr, 2)
                        temp(i, j) = arr(i, size(arr, 2) - j + 1)
                    end do
                end do
            case (2)
                do i = 1, size(arr, 1)
                    do j = 1, size(arr, 2)
                        temp(i, j) = arr(size(arr, 1) - i + 1, j)
                    end do
                end do
            case (3)
                do i = 1, size(arr, 1)
                    do j = 1, size(arr, 2)
                        temp(i, j) = arr(size(arr, 1) - j + 1, size(arr, 2) - i + 1)
                    end do
                end do
            end select

            arr(:, :) = temp(:, :)

        end subroutine rotate

    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: n, i, j, k
logical :: equal

! Read input
read(*,*) n

! Initialize matrices
integer, dimension(n,n) :: mat, target
do i = 1, n
    read(*,*) (mat(i,j), j = 1, n)
end do
do i = 1, n
    read(*,*) (target(i,j), j = 1, n)
end do

! Check if matrices are equal
equal = .true.
do i = 1, n
    do j = 1, n
        if (mat(i,j) .neq. target(i,j)) then
            equal = .false.
            exit
        end if
    end do
    if (.not. equal) exit
end do

! If matrices are equal, output "true" and exit
if (equal) then
    write(*,*) "true"
    stop
end if

! Otherwise, check if it is possible to make the matrices equal by rotating mat
! in 90-degree increments
equal = .true.
do k = 1, 4
    do i = 1, n
        do j = 1, n
            if (mat(i,j) .neq. target(n-j+1,i)) then
                equal = .false.
                exit
            end if
        end do
        if (.not. equal) exit
    end do
    if (equal) then
        write(*,*) "true"
        stop
    end if
end do

! If it is not possible to make the matrices equal by rotating mat, output "false"
write(*,*) "false"

end
🌐 Data from online sources 
import heapq

def minimumSize(nums, maxOperations):
    pq = [-num for num in nums] # Negative numbers to simulate max heap
    heapq.heapify(pq)
    while maxOperations > 0:
        maxBalls = -heapq.heappop(pq)
        heapq.heappush(pq, -maxBalls // 2)
        heapq.heappush(pq, -(maxBalls - (maxBalls // 2)))
        maxOperations -= 1
    return -pq[0]

The algorithm is based on using a priority queue (max heap) to store the number of balls in each bag. In each operation, we remove the largest (or maximum) number of balls from the queue, divide this number by 2, and push both divided parts back into the queue. This operation is performed for given maxOperations times, and then we return the maximum number of balls in the bag (i.e., the top of the max heap).

Since the priority queue maintains the order of elements, prioritizing the maximum number of balls, we can efficiently divide the balls in the largest bag in each operation, eventually minimizing the penalty after maxOperations.

🌐 Data from online sources 
#include <queue>
#include <vector>

int minimumSize(std::vector<int>& nums, int maxOperations) {
    std::priority_queue<int> pq(nums.begin(), nums.end());
    while (maxOperations > 0) {
        int maxBalls = pq.top();
        pq.pop();
        pq.push(maxBalls / 2);
        pq.push(maxBalls - (maxBalls / 2));
        maxOperations--;
    }
    return pq.top();
}

The algorithm is based on using a priority queue (max heap) to store the number of balls in each bag. In each operation, we remove the largest (or maximum) number of balls from the queue, divide this number by 2, and push both divided parts back into the queue. This operation is performed for given maxOperations times, and then we return the maximum number of balls in the bag (i.e., the top of the max heap).

Since the priority queue maintains the order of elements, prioritizing the maximum number of balls, we can efficiently divide the balls in the largest bag in each operation, eventually minimizing the penalty after maxOperations.