1752. Check if Array Is Sorted and Rotated

Time: O(n)

Space: O(1)

Intuition

Check if array is sorted and rotated. An array is sorted-rotated if it has at most one "inversion" (arr[i] > arr[i+1]) and arr[last] <= arr[0].

Algorithm

1Count positions where arr[i] > arr[(i+1)%n].
2Return count <= 1.

Common Pitfalls

•Wrap-around check: arr[n-1] <= arr[0] is also required. Total inversions <= 1 means <= 1 rotation point.

1752.cs

// Approach: Count positions where nums[i] > nums[(i+1)%n]; sorted+rotated has at most 1 such drop.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool Check(int[] nums)
    {
        int n = nums.Length;
        int cnt = 0;

        for (int i = 0; i < n; i++)
        {
            if (nums[i] > nums[(i + 1) % n])
                cnt++;
        }

        return cnt > 1 ? false : true;
    }
}

Was this solution helpful?