Code Implementation

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

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

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

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

Problem Description

You are given an array of integers nums. The task is to determine whether nums could become a non-decreasingly sorted array if it were rotated some number of times (possibly zero). In a rotation, the array is split into two parts and swapped, so the order is preserved but the starting point is changed.

The key constraints are:

• The array must be able to be rotated (possibly zero times) into a non-decreasing order.
• Each element must be used exactly once (no duplicates or omissions in the result).
• There is only one valid solution (True or False) for each input.

Thought Process

To solve this problem, let's first understand what it means for an array to be sorted and rotated:

• If an array is already sorted in non-decreasing order, it is valid (zero rotations).
• If we rotate a sorted array, the order is preserved except at the rotation point, where the last element may be less than the first element.
• So, a sorted and rotated array will have at most one place where the current element is greater than the next (a "drop" or "break" in the order).

The key insight: if there is more than one "drop" in the array, it cannot be rotated into a sorted array.

Solution Approach

Let's break down the steps:

1. Initialize a counter (count) to zero. This will track how many times an element is greater than its next element.
2. Loop through the array. For each index i, compare nums[i] with nums[(i+1) % n] (using modulo to wrap around to the first element at the end).
3. If nums[i] > nums[(i+1) % n], increment count.
4. If count ever becomes greater than 1, return False (the array cannot be rotated to sorted).
5. If the loop completes and count is 0 or 1, return True.

This works because:

• If there are zero drops, the array is already sorted.
• If there is exactly one, the array is sorted and rotated.
• More than one means it cannot be rotated into a sorted array.

Example Walkthrough

Let's walk through an example with nums = [3, 4, 5, 1, 2]:

• Compare 3 and 4: 3 < 4 (no drop)
• Compare 4 and 5: 4 < 5 (no drop)
• Compare 5 and 1: 5 > 1 (drop, count = 1)
• Compare 1 and 2: 1 < 2 (no drop)
• Compare 2 and 3 (wrap around): 2 < 3 (no drop)

Another example: nums = [2, 1, 3, 4]

• Compare 2 and 1: 2 > 1 (drop, count = 1)
• Compare 1 and 3: 1 < 3 (no drop)
• Compare 3 and 4: 3 < 4 (no drop)
• Compare 4 and 2 (wrap): 4 > 2 (drop, count = 2)

Time and Space Complexity

Brute-force approach:

• For each possible rotation (n in total), check if the rotated array is sorted (O(n) per check).
• Total time: O(n²).

• Single pass through the array: O(n) time.
• Only a few variables used: O(1) space.

The optimized solution is much more efficient, especially for large arrays.

Summary

This problem is elegantly solved by recognizing that a sorted and rotated array can have at most one "drop" in order. By counting these drops in a single pass, we avoid brute-force rotations and achieve an efficient O(n) time, O(1) space solution. The key insight is that the structure of a sorted and rotated array is simple and can be checked directly without actual rotation.