Check if Array Is Sorted and Rotated

🏠 ⬅️ ➡️

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:

Input: nums = [3,4,5,1,2] Output: true Explanation: [1,2,3,4,5] is the original sorted array. You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4] Output: false Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3] Output: true Explanation: [1,2,3] is the original sorted array. You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
⚠️ Correct 
program main
    implicit none

    integer :: i, n
    logical :: result
    integer, allocatable :: nums(:)

    ! Example 1
    allocate(nums(5))
    nums = [3, 4, 5, 1, 2]
    result = check(nums)
    if (result) then
        write (*, '(a)') "Example 1: True"
    else
        write (*, '(a)') "Example 1: False"
    end if
    deallocate(nums)

    ! Example 2
    allocate(nums(4))
    nums = [2, 1, 3, 4]
    result = check(nums)
    if (result) then
        write (*, '(a)') "Example 2: True"
    else
        write (*, '(a)') "Example 2: False"
    end if
    deallocate(nums)

    ! Example 3
    allocate(nums(3))
    nums = [1, 2, 3]
    result = check(nums)
    if (result) then
        write (*, '(a)') "Example 3: True"
    else
        write (*, '(a)') "Example 3: False"
    end if
    deallocate(nums)

contains

    function check(nums) result(result)
        implicit none
        integer, intent(in) :: nums(:)
        logical :: result
        integer :: i, j, k, l, m, n

        ! Check if the array was originally sorted in non-decreasing order
        do i = 2, size(nums)
            if (nums(i) < nums(i-1)) then
                result = .false.
                return
            end if
        end do

        ! Check if the array was rotated some number of positions (including zero)
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(j) == nums(i)) then
                    result = .true.
                    return
                end if
            end do
        end do

        result = .false.

    end function check

end program main
❌ Compiled
❌ Executed
❌ Correct 
module rotated_sorted_array

implicit none

contains

function is_rotated_sorted_array(nums) result(is_sorted)

! Given an array `nums`, return `true` if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return `false`.

! There may be duplicates in the original array.

! An array `A` rotated by `x` positions results in an array `B` of the same length such that `A[i] == B[(i+x) % A.length]`.

! Example 1:

! Input: nums = [3,4,5,1,2]
! Output: true
! Explanation: [1,2,3,4,5] is the original sorted array.
! You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

! Example 2:

! Input: nums = [2,1,3,4]
! Output: false
! Explanation: There is no sorted array once rotated that can make nums.

! Example 3:

! Input: nums = [1,2,3]
! Output: true
! Explanation: [1,2,3] is the original sorted array.
! You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

! Constraints:

! 1 <= nums.length <= 100
! 1 <= nums[i] <= 100

implicit none

integer, intent(in) :: nums(:)
logical :: is_sorted

! Edge case: If the array has only one element, it is sorted.
if (size(nums) == 1) then
    is_sorted = .true.
    return
end if

! Initialize variables.
integer :: i, j, n
logical :: found_sorted_section

! Initialize the flag to indicate if a sorted section has been found.
found_sorted_section = .false.

! Loop through the array.
do i = 1, size(nums) - 1

    ! Check if the current element is greater than the next element.
    if (nums(i) > nums(i + 1)) then

        ! If a sorted section has not been found yet, set the flag.
        if (.not. found_sorted_section) then
            found_sorted_section = .true.
        else
            ! If a sorted section has already been found, return false.
            is_sorted = .false.
            return
        end if
    end if
end do

! If a sorted section has been found, check if the last element is greater than the first element.
if (found_sorted_section) then
    if (nums(1) > nums(size(nums))) then
        is_sorted = .false.
    else
        is_sorted = .true.
    end if
else
    is_sorted = .false.
end if

end function is_rotated_sorted_array

end module rotated_sorted_array

program test_rotated_sorted_array

use rotated_sorted_array, only : is_rotated_sorted_array

implicit none

! Test case 1:
print *, is_rotated_sorted_array([3, 4, 5, 1, 2])
! Output: true

! Test case 2:
print *, is_rotated_sorted_array([2, 1, 3, 4])
! Output: false

! Test case 3:
print *, is_rotated_sorted_array([1, 2, 3])
! Output: true

end program test_rotated_sorted_array
🌐 Data from online sources 
def check_arithmetic_subarrays(nums, l, r):
    results = []
    for i in range(len(l)):
        subarray = sorted(nums[l[i]:r[i] + 1])
        is_arithmetic = True
        diff = subarray[1] - subarray[0]
        for j in range(1, len(subarray) - 1):
            if subarray[j + 1] - subarray[j] != diff:
                is_arithmetic = False
                break
        results.append(is_arithmetic)
    return results

1. For each element `i` in arrays `l` and `r`, create a subarray from `nums` using the range `[l[i], r[i]]`.
  1. Sort the subarray.
  2. Check if the subarray is an arithmetic sequence, by iterating through the subarray and making sure the difference between consecutive elements is the same.
  3. If the subarray is an arithmetic sequence, add true to the result array, otherwise, add false.
  4. Repeat this process for all the elements in arrays l and r.
  5. Return the results array containing the answers for each query.
🌐 Data from online sources 
#include <vector>
#include <algorithm>
using namespace std;

vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
    vector<bool> results;
    for(int i = 0; i < l.size(); i++) {
        vector<int> subarray(nums.begin() + l[i], nums.begin() + r[i] + 1);
        sort(subarray.begin(), subarray.end());
        bool is_arithmetic = true;
        int diff = subarray[1] - subarray[0];
        for(int j = 1; j < subarray.size() - 1; j++) {
            if(subarray[j + 1] - subarray[j] != diff) {
                is_arithmetic = false;
                break;
            }
        }
        results.push_back(is_arithmetic);
    }
    return results;
}

1. For each element `i` in arrays `l` and `r`, create a subarray from `nums` using the range `[l[i], r[i]]`.
  1. Sort the subarray.
  2. Check if the subarray is an arithmetic sequence, by iterating through the subarray and making sure the difference between consecutive elements is the same.
  3. If the subarray is an arithmetic sequence, add true to the result array, otherwise, add false.
  4. Repeat this process for all the elements in arrays l and r.
  5. Return the results array containing the answers for each query.