DSA Tracker

Visualize

Check if Array Is Sorted and Rotated

Count the falling pairs on a circular pass

time O(n)space O(1)

Rotating a sorted array moves a block from the front to the back, and that leaves exactly one seam where a large value sits directly before a small one. Everywhere else the values still rise. So the array is a rotated sorted array precisely when at most one neighbouring pair falls — one seam means it was rotated, zero seams means it was already sorted, and two or more seams cannot be produced by any single rotation. The pass must be circular: the pair made of the last element and the first is a real neighbour once the array is thought of as a ring, and forgetting it accepts arrays that end high and start low. Equal neighbours do not count as a fall, because duplicates are legal in sorted order, which is why the comparison is strictly greater-than.

Details

Animated on: nums = [5, 6, 8, 1, 2, 3, 4, 4]. Decide whether the array is a sorted array that has been rotated some number of positions (zero rotations counts). Answer: true.

Problem:Check if Array Is Sorted and RotatedEasy

Count the falling pairs on a circular pass

step 1 / 10

5
[0]
6
[1]
8
[2]
1
[3]
2
[4]
3
[5]
4
[6]
4
[7]

A sorted array rotated some number of times has exactly ONE place where the values fall instead of rise — the seam where the end wrapped around to the front. An array that was never rotated has zero such places. So the whole question is: counting circularly, how many neighbouring pairs go DOWN? Anything above one and the 8 values cannot be a rotation of a sorted list.

  • i=0· arr[0] = 5
Pseudocode
1FUNCTION checkSortedRotated(nums)
2  n <- LENGTH(nums)
3  drops <- 0
4  FOR i <- 0 TO n - 1
5    j <- (i + 1) MOD n
6    IF nums[i] > nums[j]
7      drops <- drops + 1
8  IF drops <= 1
9    RETURN TRUE
10  RETURN FALSE

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. A sorted array rotated some number of times has exactly ONE place where the values fall instead of rise — the seam where the end wrapped around to the front. An array that was never rotated has zero such places. So the whole question is: counting circularly, how many neighbouring pairs go DOWN? Anything above one and the 8 values cannot be a rotation of a sorted list.
  2. Compare nums[0]=5 against its neighbour nums[1]=6. 5 < 6, the values rise as a sorted run should, so drops stays 0.
  3. Compare nums[1]=6 against its neighbour nums[2]=8. 6 < 8, the values rise as a sorted run should, so drops stays 0.
  4. Compare nums[2]=8 against its neighbour nums[3]=1. 8 > 1, so the values fall here: drops <- 1. This is a candidate seam.
  5. Compare nums[3]=1 against its neighbour nums[4]=2. 1 < 2, the values rise as a sorted run should, so drops stays 1.
  6. Compare nums[4]=2 against its neighbour nums[5]=3. 2 < 3, the values rise as a sorted run should, so drops stays 1.
  7. Compare nums[5]=3 against its neighbour nums[6]=4. 3 < 4, the values rise as a sorted run should, so drops stays 1.
  8. Compare nums[6]=4 against its neighbour nums[7]=4. 4 and 4 are EQUAL, which is not a fall — duplicates are allowed in a sorted array, so this pair costs nothing and drops stays 1. Writing >= here would wrongly reject a valid array.
  9. Compare the WRAP pair nums[7]=4 and nums[0]=5 — the circle closing, which is the pair a plain left-to-right scan forgets. 4 < 5, the values rise as a sorted run should, so drops stays 1.
  10. One circular pass over 8 elements found 1 falling pair (at index 2), so the answer is TRUE. Cutting at that single seam and swapping the two halves rebuilds the sorted order [1, 2, 3, 4, 4, 5, 6, 8]. No sorting and no extra memory were needed — just one number.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Check if Array Is Sorted and Rotated in the editorAll Arrays problemsBack to roadmap