Scale Engineer

Check if Array Is Sorted and Rotated

Easy
#1604Time: O(N^2). Sorting the array takes O(N log N). The outer loop runs N times (for each rotation), and the inner loop for comparison also runs N times. This results in a complexity of O(N log N + N*N), which simplifies to O(N^2).Space: O(N), where N is the number of elements in the array. This space is used to store the `sortedNums` array.2 companies
Data structures
Array
Companies
tcsSoundHound

Prompt

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.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.
 
 

 

 

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the problem's definition. It first creates a sorted version of the input array. Then, it generates every possible rotation of this sorted array and compares each one with the original input array. If any of the rotated versions match the input array, the function returns true; otherwise, it returns false after checking all possibilities.

Algorithm

  • Create a copy of the input array nums and sort it. Let's call this sortedNums.
  • Iterate through all possible rotation offsets, from 0 to n-1, where n is the length of the array.
  • For each rotation offset x, check if the original array nums is equal to the sortedNums array rotated by x.
  • To check for equality, iterate from i = 0 to n-1 and compare nums[i] with sortedNums[(i + x) % n].
  • If a match is found for any rotation x, return true immediately.
  • If the loops complete without finding any matching rotation, return false.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. The core idea is to verify if the given array nums can be produced by rotating a sorted version of itself.

  1. Sort a Copy: First, we create a new array, sortedNums, which is a sorted version of the input nums. This gives us the 'original sorted array' mentioned in the problem description.
  2. Generate and Compare Rotations: We then systematically generate all n possible rotations of sortedNums. A rotation by x positions means the element at index i in the sorted array moves to index (i + x) % n. For each of these n rotations, we compare it element-by-element with the original nums array.
  3. Return Result: If we find any rotation of sortedNums that is identical to nums, we've confirmed that nums is a sorted and rotated array, so we return true. If we exhaust all n possible rotations without finding a match, it means nums cannot be formed this way, and we return false.
import java.util.Arrays; class Solution {    public boolean check(int[] nums) {        int n = nums.length;        int[] sortedNums = new int[n];        System.arraycopy(nums, 0, sortedNums, 0, n);        Arrays.sort(sortedNums);         // Try all n possible rotation offsets        for (int x = 0; x < n; x++) {            boolean match = true;            // Check if this rotation matches the original array            for (int i = 0; i < n; i++) {                if (nums[i] != sortedNums[(i + x) % n]) {                    match = false;                    break;                }            }            if (match) {                return true;            }        }        return false;    }}

Complexity

Time

O(N^2). Sorting the array takes O(N log N). The outer loop runs N times (for each rotation), and the inner loop for comparison also runs N times. This results in a complexity of O(N log N + N*N), which simplifies to O(N^2).

Space

O(N), where N is the number of elements in the array. This space is used to store the `sortedNums` array.

Trade-offs

Pros

  • Easy to understand and implement as it directly follows the problem statement.

  • Guaranteed to be correct.

Cons

  • Highly inefficient with a time complexity of O(N^2), which is slow for larger arrays.

  • Requires O(N) extra space to store the sorted copy of the array.

Solutions

class Solution {public  boolean check(int[] nums) {    int cnt = 0;    for (int i = 0, n = nums.length; i < n; ++i) {      if (nums[i] > nums[(i + 1) % n]) {        ++cnt;      }    }    return cnt <= 1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem