Flipping an Image

🏠 ⬅️ ➡️

Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed.

  • For example, flipping [1,1,0] horizontally results in [0,1,1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.

  • For example, inverting [0,1,1] results in [1,0,0].

Example 1:

Input: image = [[1,1,0],[1,0,1],[0,0,0]] Output: [[1,0,0],[0,1,0],[1,1,1]] Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]]. Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]] Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]] Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]. Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Constraints:

  • n == image.length
  • n == image[i].length
  • 1 <= n <= 20
  • images[i][j] is either 0 or 1.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer :: i, j
    logical :: image(n, n)

    ! Example 1
    image(:, :) = .false.
    image(1, :) = .true.
    image(2, :) = .true.
    image(3, :) = .false.
    call print_result(image)

    ! Example 2
    image(:, :) = .false.
    image(1, :) = .true.
    image(2, :) = .false.
    image(3, :) = .true.
    call print_result(image)

contains

    subroutine print_result(image)
        implicit none
        logical, intent(in) :: image(n, n)
        character(len=n) :: line

        do i = 1, n
            write (line, '(*(L1))') image(i, :)
            print *, trim(adjustl(line))
        end do
    end subroutine print_result
end program main
❌ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: i, j, n
integer, dimension(:, :), allocatable :: image, flipped_image, inverted_image

! Read input
read(*,*) n
allocate(image(n, n))
do i = 1, n
    read(*,*) image(i, :)
end do

! Flip the image horizontally
flipped_image = image
do i = 1, n
    flipped_image(i, :) = flipped_image(i, :)[::-1]
end do

! Invert the image
inverted_image = flipped_image
do i = 1, n
    do j = 1, n
        if (inverted_image(i, j) == 0) then
            inverted_image(i, j) = 1
        else
            inverted_image(i, j) = 0
        end if
    end do
end do

! Output result
do i = 1, n
    write(*,*) inverted_image(i, :)
end do

end
🌐 Data from online sources 
def pruneTree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if root.val == 0 and not root.left and not root.right:
        return None
    return root

The algorithm uses a depth first search approach to traverse the given binary tree recursively. When traversing the tree, the function checks if a node has a value of 1 or has any child nodes with a value of 1.

In the base case, if the current node is null, return null.

For each node, the algorithm first checks its left and right subtrees using height-depth traversal through recursion. After checking its left and right subtrees, if the current node has a value of 0 and has no left or right child nodes, the function returns null, effectively pruning the subtree. If any part of the subtree has a value of 1, then the recursion returns the root of that subtree.

In the end, the algorithm returns the root of the pruned binary tree.

🌐 Data from online sources 
TreeNode* pruneTree(TreeNode* root) {
    if (!root) return nullptr;
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (root->val == 0 && !root->left && !root->right) return nullptr;
    return root;
}

The algorithm uses a depth first search approach to traverse the given binary tree recursively. When traversing the tree, the function checks if a node has a value of 1 or has any child nodes with a value of 1.

In the base case, if the current node is null, return null.

For each node, the algorithm first checks its left and right subtrees using height-depth traversal through recursion. After checking its left and right subtrees, if the current node has a value of 0 and has no left or right child nodes, the function returns null, effectively pruning the subtree. If any part of the subtree has a value of 1, then the recursion returns the root of that subtree.

In the end, the algorithm returns the root of the pruned binary tree.