Make Two Arrays Equal by Reversing Subarrays

🏠 ⬅️ ➡️

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can make arr equal to target or false otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3] Output: true Explanation: You can follow the next steps to convert arr to target: 1- Reverse subarray [2,4,1], arr becomes [1,4,2,3] 2- Reverse subarray [4,2], arr becomes [1,2,4,3] 3- Reverse subarray [4,3], arr becomes [1,2,3,4] There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7] Output: true Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11] Output: false Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

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

    integer, parameter :: n = 4
    integer, dimension(n) :: target = [1, 2, 3, 4]
    integer, dimension(n) :: arr = [2, 4, 1, 3]
    logical :: result

    print '(L1)', solve(target, arr)

contains

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

        integer :: i, j, k
        integer, allocatable :: tmp(:)

        if (size(target) /= size(arr)) then
            stop "Error: arrays must have same size"
        end if

        res = .false.

        ! check if arr is already equal to target
        if (all(target == arr)) then
            res = .true.
            return
        end if

        allocate(tmp(size(arr)))

        ! try to find a non-empty subarray in arr that we can reverse
        do i = 1, size(arr) - 1
            if (arr(i) /= arr(i+1)) then
                ! found a non-empty subarray, now check if we can reverse it
                do j = i + 1, size(arr)
                    if (arr(j) /= arr(j-1)) exit
                end do
                if (j > i + 1) then
                    ! reverse the subarray
                    do k = i + 1, (j - 1) / 2
                        tmp(k) = arr(j - k + i)
                        tmp(j - k + i) = arr(k)
                    end do
                    arr = tmp
                    deallocate(tmp)
                    allocate(tmp(size(arr)))
                    tmp = arr
                    arr = tmp
                    deallocate(tmp)
                    allocate(tmp(size(arr)))

                    ! check if arr is now equal to target
                    if (all(target == arr)) then
                        res = .true.
                        return
                    end if
                end if
            end if
        end do

        deallocate(tmp)

        res = .false.

    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module reversible_array
implicit none
private
public :: reversible_array

type :: reversible_array
    integer, allocatable :: arr(:)
    integer :: length
contains
    procedure, public :: reverse
    procedure, public :: is_equal
end type reversible_array

contains

subroutine reverse(this, start, end)
    class(reversible_array), intent(inout) :: this
    integer, intent(in) :: start, end
    integer :: i

    do i = start, (end + start) / 2
        this%arr(i) = this%arr(i) + this%arr(end + 1 - i)
        this%arr(end + 1 - i) = this%arr(i) - this%arr(end + 1 - i)
        this%arr(i) = this%arr(i) - this%arr(end + 1 - i)
    end do
end subroutine reverse

function is_equal(this, other) result(is_equal)
    class(reversible_array), intent(in) :: this, other
    logical :: is_equal
    integer :: i

    if (this%length /= other%length) then
        is_equal = .false.
        return
    end if

    do i = 1, this%length
        if (this%arr(i) /= other%arr(i)) then
            is_equal = .false.
            return
        end if
    end do

    is_equal = .true.
end function is_equal

end module reversible_array

program main
    use reversible_array
    implicit none
    integer, parameter :: n = 4
    integer, parameter :: target(n) = [1, 2, 3, 4]
    integer, parameter :: arr(n) = [2, 4, 1, 3]
    type(reversible_array) :: ra

    ra%arr = arr
    ra%length = n

    if (ra%is_equal(target)) then
        write (*,*) "True"
    else
        write (*,*) "False"
    end if

    call ra%reverse(1, 2)

    if (ra%is_equal(target)) then
        write (*,*) "True"
    else
        write (*,*) "False"
    end if

    call ra%reverse(3, 4)

    if (ra%is_equal(target)) then
        write (*,*) "True"
    else
        write (*,*) "False"
    end if

    call ra%reverse(1, 4)

    if (ra%is_equal(target)) then
        write (*,*) "True"
    else
        write (*,*) "False"
    end if
end program main
🌐 Data from online sources 
def numberOfSubstrings(s: str) -> int:
    res, i, count = 0, 0, [0, 0, 0]

    for j, ch in enumerate(s):
        count[ord(ch) - ord('a')] += 1

        while count[0] > 0 and count[1] > 0 and count[2] > 0:
            count[ord(s[i]) - ord('a')] -= 1
            i += 1

        res += i

    return res
  1. Initialize three pointers res, i (or left), and a count list, where res is the result of total numbers of substrings containing a, b, and c.
  2. Iterate through the string s, increment the count of the current character.
  3. Use a while loop inside the iteration to check if all characters' count values are greater than 0.
  4. If all are greater than 0, continuously decrease the count of the character at the current index i while incrementing the i.
  5. For each iteration, increase the result res by i (or left).
  6. Return the result res.

The algorithm uses a sliding window method to keep track of the substrings. The complexity is O(N), where N is the length of the string s.

🌐 Data from online sources 
int numberOfSubstrings(string s) {
    int res = 0, i = 0;
    vector<int> count(3, 0);

    for (int j = 0; j < s.length(); j++) {
        count[s[j] - 'a']++;

        while(count[0] > 0 && count[1] > 0 && count[2] > 0) {
            count[s[i++] - 'a']--;
        }

        res += i;
    }

    return res;
}
  1. Initialize three pointers res, i (or left), and a count list, where res is the result of total numbers of substrings containing a, b, and c.
  2. Iterate through the string s, increment the count of the current character.
  3. Use a while loop inside the iteration to check if all characters' count values are greater than 0.
  4. If all are greater than 0, continuously decrease the count of the character at the current index i while incrementing the i.
  5. For each iteration, increase the result res by i (or left).
  6. Return the result res.

The algorithm uses a sliding window method to keep track of the substrings. The complexity is O(N), where N is the length of the string s.