Array Transformation

🏠 ⬅️ ➡️

Given an initial array arr, every day you produce a new array using the array of the previous day.

On the i-th day, you do the following operations on the array of day i-1 to produce the array of day i:

  1. If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
  2. If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
  3. The first and last elements never change.

After some days, the array does not change. Return that final array.

Example 1:

Input: arr = [6,2,3,4] Output: [6,3,3,4] Explanation: On the first day, the array is changed from [6,2,3,4] to [6,3,3,4]. No more operations can be done to this array.

Example 2:

Input: arr = [1,6,3,4,3,5] Output: [1,4,4,4,4,5] Explanation: On the first day, the array is changed from [1,6,3,4,3,5] to [1,5,4,3,4,5]. On the second day, the array is changed from [1,5,4,3,4,5] to [1,4,4,4,4,5]. No more operations can be done to this array.

Constraints:

  • 3 <= arr.length <= 100
  • 1 <= arr[i] <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 100
    integer :: i, j, k
    integer :: arr(n)
    logical :: changed

    ! Example 1
    arr = [6, 2, 3, 4]
    call solve(arr)
    write(*,*) "Example 1:"
    write(*,'(10I3)') arr

    ! Example 2
    arr = [1, 6, 3, 4, 3, 5]
    call solve(arr)
    write(*,*) "Example 2:"
    write(*,'(10I3)') arr

contains

    subroutine solve(arr)
        implicit none
        integer, intent(inout) :: arr(:)
        integer :: i, j, k
        logical :: changed

        do while (changed)
            changed = .false.
            do i = 2, size(arr)-1
                if (arr(i) < arr(i-1) .and. arr(i) < arr(i+1)) then
                    arr(i) = arr(i) + 1
                    changed = .true.
                end if
                if (arr(i) > arr(i-1) .and. arr(i) > arr(i+1)) then
                    arr(i) = arr(i) - 1
                    changed = .true.
                end if
            end do
        end do
    end subroutine solve

end program main
✅ Compiled
✅ Executed
❌ Correct 
module example

implicit none

contains

function solve(arr) result(final_arr)

integer, intent(in) :: arr(:)
integer :: final_arr(size(arr))

integer :: i, j

final_arr = arr

do i = 2, size(arr) - 1
    do j = i - 1, i + 1
        if (final_arr(i) < final_arr(j)) then
            final_arr(i) = final_arr(i) + 1
        end if
    end do
end do

do i = 2, size(arr) - 1
    do j = i - 1, i + 1
        if (final_arr(i) > final_arr(j)) then
            final_arr(i) = final_arr(i) - 1
        end if
    end do
end do

end function solve

end module example

program main

use example

implicit none

integer, parameter :: n = 6
integer :: arr(n) = [6, 2, 3, 4, 3, 5]
integer :: final_arr(n)

final_arr = solve(arr)

write (*, *) final_arr

end program main
🌐 Data from online sources 
def sumEvenGrandparent(root, parent=None, grandparent=None):
    if not root:
        return 0
    sum = 0
    if grandparent and grandparent.val % 2 == 0:
        sum += root.val
    sum += sumEvenGrandparent(root.left, root, parent) + sumEvenGrandparent(root.right, root, parent)
    return sum

We perform a depth-first search traversal of the binary tree. For each node, we maintain the current node's parent and grandparent in the traversal. While traversing the tree, we check if the current node's grandparent has an even value. If yes, we add the current node's value to the sum. The algorithm is the same for all languages, with only syntax differences.

🌐 Data from online sources 
int sumEvenGrandparent(TreeNode* root, TreeNode* parent = nullptr, TreeNode* grandparent = nullptr) {
    if (!root) return 0;
    int sum = 0;
    if (grandparent && grandparent->val % 2 == 0) {
        sum += root->val;
    }
    sum += sumEvenGrandparent(root->left, root, parent) + sumEvenGrandparent(root->right, root, parent);
    return sum;
}

We perform a depth-first search traversal of the binary tree. For each node, we maintain the current node's parent and grandparent in the traversal. While traversing the tree, we check if the current node's grandparent has an even value. If yes, we add the current node's value to the sum. The algorithm is the same for all languages, with only syntax differences.