Check if Array Is Sorted and Rotated - Practice Coding Problems

Check if Array Is Sorted and Rotated - Problem

Array Easy

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that B[i] == A[(i+x) % A.length] for every valid index i.

Input & Output

Example 1 — Sorted and Rotated

$ Input: nums = [2,1,3,4]

› Output: true

💡 Note: The array [1,2,3,4] was rotated by 3 positions to get [2,1,3,4]. Original: [1,2,3,4] → Rotate right by 3 → [2,1,3,4]. Only one break point at position 0→1.

Example 2 — Not Sorted Even After Rotation

$ Input: nums = [3,4,5,1,2]

› Output: true

💡 Note: Original sorted array [1,2,3,4,5] was rotated. Only one break point where 5 > 1, so it's valid.

Example 3 — Multiple Break Points

$ Input: nums = [2,1,3,4,5,10,6,7,8]

› Output: false

💡 Note: Multiple break points: 2>1, 10>6. No rotation can make this array sorted.

Constraints

1 ≤ nums.length ≤ 100
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array that might be sorted and rotated

Find Break Points

Count where order decreases in circular fashion

Validate

Return true if at most 1 break point exists

Key Takeaway

🎯 Key Insight: A sorted rotated array has at most one position where the order breaks in circular fashion

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is that a sorted rotated array has at most one break point where nums[i] > nums[i+1] in circular order. Best approach is to count these break points in O(n) time. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Rotations	O(n²)	O(n)	Try every possible rotation position and check if any results in a sorted array
Count Break Points	O(n)	O(1)	Count how many times the order breaks in the circular array

Brute Force - Try All Rotations — Algorithm Steps

Step 1: Try each rotation position from 0 to n-1
Step 2: For each position, check if the rotated array is sorted
Step 3: Return true if any rotation is sorted, false otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with given array

Try Rotations

Test each possible rotation position

Check Sorted

Return true if any rotation is sorted

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int n) {
    // Try each rotation position
    for (int rotation = 0; rotation < n; rotation++) {
        // Check if this rotation is sorted
        bool is_sorted = true;
        for (int i = 1; i < n; i++) {
            int curr = nums[(i + rotation) % n];
            int prev = nums[(i - 1 + rotation) % n];
            if (curr < prev) {
                is_sorted = false;
                break;
            }
        }
        
        if (is_sorted) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    bool result = solution(nums, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loop checks if array is sorted in O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Creates temporary array for each rotation attempt

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Rotations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler