Check if Array Is Sorted and Rotated

Easy
1108.

Check if Array Is Sorted and Rotated

Check if Array Is Sorted and Rotated is an easy coding problem on arrays and sorting, asked in Amazon, Google and Microsoft interviews.

Return true if nums could have been produced by taking an array sorted in non-decreasing order and rotating it by some number of positions (possibly zero); otherwise return false.

Rotating an array a by x positions gives the array b with b[i] = a[(i + x) % a.length]. The array may contain duplicates.

Example 1

Input
nums = [6,8,9,2,4]
Output
true
Explanation
[2,4,6,8,9] rotated by 2 positions.

Example 2

Input
nums = [5,3,4,1]
Output
false
Explanation
The order breaks at 5 → 3 and again at 4 → 1.

Example 3

Input
nums = [7,7,7]
Output
true

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var check = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if Array Is Sorted and Rotated — Problem & Solution

Check if Array Is Sorted and Rotated solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Check if Array Is Sorted and Rotated is an easy coding problem on arrays and sorting, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return true if nums could have been produced by taking an array sorted in non-decreasing order and rotating it by some number of positions (possibly zero); otherwise return false.

Rotating an array a by x positions gives the array b with b[i] = a[(i + x) % a.length]. The array may contain duplicates.

Example 1

Input: nums = [6,8,9,2,4]
Output: true
Explanation: [2,4,6,8,9] rotated by 2 positions.

Example 2

Input: nums = [5,3,4,1]
Output: false
Explanation: The order breaks at 5 → 3 and again at 4 → 1.

Example 3

Input: nums = [7,7,7]
Output: true

Constraints

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

Hints for Check if Array Is Sorted and Rotated

  1. Hint 1

    A sorted array has no place where a value is followed by a smaller one.

  2. Hint 2

    Rotating it creates at most one such drop — at the seam — if you also compare the last element with the first.

  3. Hint 3

    Count indices i where nums[i] > nums[(i + 1) % n]; the answer is whether the count is at most 1.

How to solve Check if Array Is Sorted and Rotated

Read the array as a circle. A rotated sorted array, read around the circle, goes down at most once — where the end of the original array meets its start.

Approach

  1. Count the indices i with nums[i] > nums[(i + 1) % n].
  2. Return true if the count is 0 or 1.

Why it works

Rotation does not change the circular order, and a sorted array read circularly has at most one drop (from its last element back to its first). Conversely, if there is at most one circular drop, starting the reading just after it gives a non-decreasing array, which rotates into nums. With zero drops all values are equal, which is sorted too.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Include the wrap-around pair (last, first); without it [2,1,3,4] would look like one drop and pass.
  • Duplicates are allowed, so compare with >, not >=.
  • A rotation by zero is allowed: an already sorted array is true.

Reference solution

Python

from typing import List

def check(nums: List[int]) -> bool:
    n = len(nums)
    drops = sum(1 for i in range(n) if nums[i] > nums[(i + 1) % n])
    return drops <= 1

Java

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

C++

bool check(vector<int>& nums) {
    int n = nums.size(), drops = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] > nums[(i + 1) % n]) drops++;
    }
    return drops <= 1;
}

JavaScript

var check = function(nums) {
    var n = nums.length, drops = 0;
    for (var i = 0; i < n; i++) {
        if (nums[i] > nums[(i + 1) % n]) drops++;
    }
    return drops <= 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms