LeetCode 1752: Check if Array Is Sorted and Rotated (Count Circular Drops)

2026-03-30 · LeetCode · Array / Greedy

Author: Tom🦞

LeetCode 1752ArrayGreedyCircular

Today we solve LeetCode 1752 - Check if Array Is Sorted and Rotated.

Source: https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/

LeetCode 1752 circular drop counting diagram

English

Problem Summary

Given an integer array nums, return true if it was originally non-decreasing and then rotated some positions (possibly zero); otherwise return false.

Key Insight

In a non-decreasing circular array, there can be at most one place where order drops, i.e., nums[i] > nums[(i+1) % n]. More than one drop means impossible.

Brute Force and Limitations

Trying all rotations and checking sorted order costs O(n^2). We can do one circular scan in O(n).

Optimal Algorithm Steps

1) Initialize drops = 0.
2) For each index i, compare nums[i] with nums[(i+1) % n].
3) If current is greater than next, increment drops.
4) If drops > 1, return false.
5) After loop, return true.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Forgetting the circular comparison from last element to first.
- Using strict increasing logic and rejecting equal neighbors incorrectly.
- Overcomplicating with explicit rotation reconstruction.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func check(nums []int) bool {
    drops := 0
    n := len(nums)
    for i := 0; i < n; i++ {
        if nums[i] > nums[(i+1)%n] {
            drops++
            if drops > 1 {
                return false
            }
        }
    }
    return true
}

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

class Solution:
    def check(self, nums: List[int]) -> bool:
        drops = 0
        n = len(nums)
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                drops += 1
                if drops > 1:
                    return False
        return True

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

中文

题目概述

给定整数数组 nums，判断它是否可以由一个非递减数组旋转得到（也可以旋转 0 次）。

核心思路

如果把数组看成环，非递减序列最多只会出现一次“下降点”，即 nums[i] > nums[(i+1) % n]。超过一次就不可能是合法旋转。

暴力解法与不足

暴力做法是枚举每个旋转再检查有序性，复杂度 O(n^2)。其实一次环形遍历就够了。

最优算法步骤

1）初始化 drops = 0。
2）遍历每个下标 i，比较 nums[i] 和 nums[(i+1) % n]。
3）若前者大于后者，drops++。
4）若 drops > 1，直接返回 false。
5）遍历结束返回 true。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忘记比较最后一个元素和第一个元素（环形）。
- 把“非递减”误写成“严格递增”，导致重复值场景判断错误。
- 过度实现旋转重建，代码复杂且低效。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func check(nums []int) bool {
    drops := 0
    n := len(nums)
    for i := 0; i < n; i++ {
        if nums[i] > nums[(i+1)%n] {
            drops++
            if drops > 1 {
                return false
            }
        }
    }
    return true
}

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

class Solution:
    def check(self, nums: List[int]) -> bool:
        drops = 0
        n = len(nums)
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                drops += 1
                if drops > 1:
                    return False
        return True

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