1752. Check if Array Is Sorted and Rotated

Description

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 B[i] == A[(i+x) % A.length] for every valid index i.

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 = 2 positions to begin on 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

Solutions

Solution 1: Single Pass

To satisfy the problem's requirement, there can be at most one element in array \(\textit{nums}\) whose value is greater than the next element, i.e., \(nums[i] \gt nums[i + 1]\). If there are more than one such elements, then array \(\textit{nums}\) cannot be obtained by rotation.

Note that the next element after the last element of array \(\textit{nums}\) is the first element of array \(\textit{nums}\).

The time complexity is \(O(n)\), where \(n\) is the length of array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3

class Solution:
    def check(self, nums: List[int]) -> bool:
        return sum(nums[i - 1] > x for i, x in enumerate(nums)) <= 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public boolean check(int[] nums) {
        int cnt = 0;
        for (int i = 0, n = nums.length; i < n; ++i) {
            if (nums[i] > nums[(i + 1) % n]) {
                ++cnt;
            }
        }
        return cnt <= 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    bool check(vector<int>& nums) {
        int cnt = 0;
        for (int i = 0, n = nums.size(); i < n; ++i) {
            cnt += nums[i] > (nums[(i + 1) % n]);
        }
        return cnt <= 1;
    }
};

1
2
3
4
5
6
7
8
9

func check(nums []int) bool {
    cnt := 0
    for i, x := range nums {
        if x > nums[(i+1)%len(nums)] {
            cnt++
        }
    }
    return cnt <= 1
}

1
2
3
4

function check(nums: number[]): boolean {
    const n = nums.length;
    return nums.reduce((cnt, x, i) => cnt + (x > nums[(i + 1) % n] ? 1 : 0), 0) <= 1;
}

1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn check(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let cnt = nums.iter().enumerate().fold(0, |cnt, (i, &x)| {
            cnt + if x > nums[(i + 1) % n] { 1 } else { 0 }
        });
        cnt <= 1
    }
}

1
2
3
4
5
6
7
8
9

bool check(int* nums, int numsSize) {
    int cnt = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > nums[(i + 1) % numsSize]) {
            cnt++;
        }
    }
    return cnt <= 1;
}

Comments