Pattern visualizer
Check if Array is Sorted and Rotated
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. 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..
Count the falling pairs on a circular pass
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.
1FUNCTION checkSortedRotated(nums)2 n <- LENGTH(nums)3 drops <- 04 FOR i <- 0 TO n - 15 j <- (i + 1) MOD n6 IF nums[i] > nums[j]7 drops <- drops + 18 IF drops <= 19 RETURN TRUE10 RETURN FALSE
← / → step · space play · Home restart