💬 Discord
Sign In
NeetCode #63LC-1752EasyArrays & Hashing
← Back to All Problems

#63 · #1752 · Check if Array Is Sorted and Rotated(检查数组是否经排序和轮转得到)

📌 Problem Statement & Constraints

Given an array nums, return true if it was originally sorted in non-decreasing order and then rotated some number of positions (including zero). Constraints: 1 <= nums.length <= 100, 1 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. A rotation of a sorted array has at most one descent, where nums[i] > nums[i + 1].
  2. Count descents across the array, treating it as circular by also comparing the last element with the first.
  3. If the total number of descents is at most 1, the array is a valid rotation.
  4. The circular comparison is the part candidates miss: [2, 1, 3, 4] has one linear descent but the wrap-around also descends, giving two, so it is not a rotation.

💻 Benchmark Python3 Implementation

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)
        descents = 0
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:    # circular comparison
                descents += 1
        return descents <= 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): a single counter.

⚠️ Interview Pitfalls & Follow-ups

  • Only scanning 0..n-2: the wrap-around comparison from the last element back to the first is required to detect arrays like [2, 1, 3, 4].
  • Requiring exactly one descent: a fully sorted array has zero descents and is a valid rotation (by zero positions).
  • Using >=: duplicates are allowed, so equal neighbours are not descents. The comparison must be strict.