DDSA Solutions

1752. Check if Array Is Sorted and Rotated

EasyView on LeetCode
Array
Time: O(n)
Space: O(1)

Problem Overview

Check if array is sorted and rotated.

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

  1. 1Count positions where arr[i] > arr[(i+1)%n].
  2. 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
C#
// 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?

Related Problems