LeetCode 1752 - Check if Array Is Sorted and Rotated

LeetCode Problem 1752

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem is asking us to determine whether a given array nums could be the result of taking a sorted array in non-decreasing order and then rotating it by some number of positions. A non-decreasing array is one where each element is greater than or equal to the previous one. Rotating an array means taking some prefix of elements and moving them to the end while keeping the order of elements intact.

The input nums is an array of integers, potentially containing duplicates, with length between 1 and 100 and values between 1 and 100. The expected output is a boolean: true if nums could be a rotated sorted array, and false otherwise.

Important edge cases include arrays of length 1 (which are trivially considered sorted and rotated), arrays that are already sorted without any rotation, arrays where all elements are equal, and arrays with multiple places where order decreases (which would make rotation impossible).

The problem guarantees that the array contains integers within a small range, allowing us to consider linear-time solutions without performance concerns.

Approaches

A brute-force approach would be to try every possible rotation of the array and check if it is sorted. For each rotation, we would generate the rotated array and iterate through it to see if it is in non-decreasing order. While this works for small arrays, it has O(n²) time complexity, which is unnecessary even for the problem constraints.

The key insight is that a sorted and rotated array will have at most one place where the array "wraps around", i.e., where an element is greater than the next element. If we count the number of such decreases in the array, it should be either 0 (array is fully sorted and not rotated) or 1 (array is sorted and rotated once). If there is more than one decrease, it is impossible for the array to be a rotated sorted array.

This insight allows an optimal solution in a single pass: iterate through the array once, counting decreases, including the wrap-around between the last and first elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Generate all rotations and check if sorted
Optimal	O(n)	O(1)	Single pass counting decreases (including wrap-around)

Algorithm Walkthrough

1. Initialize a counter count to 0. This will track the number of times an element is greater than the following element.
2. Iterate through the array from the first element to the last element. For each index i, compare nums[i] to nums[(i + 1) % n]. Using modulo ensures the comparison wraps around to the first element.
3. If nums[i] > nums[(i + 1) % n], increment count. This identifies a point where the sorted order is violated, representing the potential "rotation point."
4. After completing the iteration, check if count is less than or equal to 1. If so, return true because the array could be sorted and rotated. Otherwise, return false.

Why it works: A non-decreasing array has elements in order with no decreases. A rotated version introduces at most one decrease at the rotation point. Any additional decrease indicates that the array could not have been a sorted array rotated.

Python Solution

from typing import List

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

The implementation initializes a counter, iterates through all elements including the wrap-around, and immediately returns False if more than one decrease is found. If the loop completes without exceeding one decrease, it returns True.

Go Solution

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

In Go, we handle the array similarly. Slices in Go are zero-indexed and use modulo arithmetic to wrap around. The early return ensures efficiency for larger arrays, though the constraints are small.

Worked Examples

Example 1: nums = [3,4,5,1,2]

i	nums[i]	nums[(i+1)%n]	nums[i] > next?	count
0	3	4	No	0
1	4	5	No	0
2	5	1	Yes	1
3	1	2	No	1
4	2	3	No	1

Count = 1, return True.

Example 2: nums = [2,1,3,4]

i	nums[i]	nums[(i+1)%n]	nums[i] > next?	count
0	2	1	Yes	1
1	1	3	No	1
2	3	4	No	1
3	4	2	Yes	2

Count = 2, return False.

Example 3: nums = [1,2,3]

i	nums[i]	nums[(i+1)%n]	nums[i] > next?	count
0	1	2	No	0
1	2	3	No	0
2	3	1	Yes	1

Count = 1, return True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate once over the array of length n, performing constant-time operations.
Space	O(1)	Only a single counter is used, no additional data structures are needed.

Because n ≤ 100, this solution is efficient and does not require optimization.

Test Cases

# Provided examples
assert Solution().check([3,4,5,1,2]) == True  # rotated sorted array
assert Solution().check([2,1,3,4]) == False   # cannot form sorted array
assert Solution().check([1,2,3]) == True      # already sorted

# Edge cases
assert Solution().check([1]) == True          # single element
assert Solution().check([1,1,1]) == True      # all duplicates
assert Solution().check([2,2,2,1,2]) == True  # duplicates with one rotation point
assert Solution().check([2,3,4,5,1,2,3]) == False  # multiple decrease points
assert Solution().check([1,3,2]) == False     # one inversion in middle, not wrap-around

Test	Why
[3,4,5,1,2]	Rotated sorted array, single wrap-around
[2,1,3,4]	Multiple decreases, cannot be rotated sorted
[1,2,3]	Already sorted, no rotation
[1]	Single element edge case
[1,1,1]	All elements equal, no rotation needed
[2,2,2,1,2]	Rotation with duplicates, single decrease
[2,3,4,5,1,2,3]	Multiple decreases, invalid
[1,3,2]	Non-rotatable inversion in middle

Edge Cases

A single-element array is trivially considered sorted and rotated, as no rotation changes the order. The implementation correctly handles this by iterating once and finding zero decreases.

Arrays with all elements equal are also edge cases because every comparison nums[i] > nums[i+1] is false. Our implementation counts zero decreases, returning True.

Arrays with multiple decreasing points or inversions, especially when duplicates exist, could cause naive implementations to fail. By counting decreases and using the wrap-around comparison, the solution correctly identifies whether the array could be a rotated sorted array.