☕ DSA Java Articles

Topics › Arrays › Easy

Check if the Array is Sorted II

Easy TUF ID 379 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums. Return true if nums was originally sorted in non-decreasing order and then rotated left or right by some number of positions (zero positions allowed), and false otherwise. Duplicates may appear.

Formally, nums is accepted if there is some shift in 0 .. n - 1 such that the sequence nums[shift], nums[shift + 1], ..., nums[(shift + n - 1) mod n] is non-decreasing.

This is the “II” in the title: the plain version only asks whether the array is sorted, and that check (isSorted in the Java file) is the warm-up for the rotated version. The rotated version is LeetCode 1752.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer.

Example 1

nums = [3, 4, 5, 1, 2]
answer = true           // [1, 2, 3, 4, 5] rotated left by 2 (or right by 3)

Example 2

nums = [2, 1, 3, 4]
answer = false          // no rotation of a sorted array gives this: it goes down twice (2->1 and, wrapping, 4->2)

Example 3

nums = [1, 2, 3]
answer = true           // rotation by zero counts

The warm-up: plain sortedness

An array is sorted in non-decreasing order when no element is smaller than its predecessor:

static boolean isSorted(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) return false;
    }
    return true;
}

Note the comparison is <, not <=: [1, 2, 2, 3] is sorted in the non-decreasing sense and must pass. Empty and one-element arrays pass trivially because the loop body never runs. Everything below builds on this one idea, a descent: a position i where nums[i] < nums[i - 1].

Approach 1: Brute force, try every rotation

Intuition. The definition says “some rotation is sorted”, so test all of them. For each shift, walk the array starting at shift and wrapping around with % n, and check for a descent. Instead of physically rotating (which would cost O(n) extra space or a lot of swapping), index arithmetic reads the rotated view in place.

Algorithm.

  1. An empty array is sorted; return true.
  2. For shift from 0 to n - 1:
    • Assume ok = true. For i from 1 to n - 1, compare nums[(shift + i) % n] with nums[(shift + i - 1) % n]; a descent sets ok = false and stops the inner loop.
    • If ok survived, return true.
  3. No rotation worked: return false.
static boolean bruteForce(int[] nums) {
    int n = nums.length;
    if (n == 0) return true;
    for (int shift = 0; shift < n; shift++) {
        boolean ok = true;
        for (int i = 1; i < n && ok; i++) {
            if (nums[(shift + i) % n] < nums[(shift + i - 1) % n]) ok = false;
        }
        if (ok) return true;
    }
    return false;
}

Complexity. Time O(n^2): n candidate shifts, each checked in O(n). Space O(1): no copy of the array is made.

For n = 10^5 that is 10^10 comparisons, far too many. The waste is obvious once you notice that almost every shift fails for the same reason: the array goes down somewhere in the middle, and only a shift that starts right at that drop has any chance.

Approach 2: Better, find the single descent and check the wrap

Intuition. Picture a sorted array rotated by k: [a_k, ..., a_{n-1}, a_0, ..., a_{k-1}]. Reading left to right it is non-decreasing, then at the seam it drops from a_{n-1} (the global maximum) to a_0 (the global minimum), then it is non-decreasing again. So a rotated sorted array has at most one descent when read left to right. But one descent is not enough on its own: [1, 3, 2] has a single descent (3 -> 2) and is not a rotation of anything sorted. The missing condition is the seam between the last and first element: the suffix’s last value must be ≤ the prefix’s first value, so that gluing the two sorted pieces back together is itself sorted.

Algorithm.

  1. Scan for descents. Record the index of the first one; if a second one appears, return false.
  2. No descent at all: the array is sorted; return true.
  3. Exactly one descent: return nums[n - 1] <= nums[0].
static boolean better(int[] nums) {
    int n = nums.length;
    int drop = -1;                               // index i with nums[i] < nums[i - 1]
    for (int i = 1; i < n; i++) {
        if (nums[i] < nums[i - 1]) {
            if (drop != -1) return false;        // a second descent cannot come from one rotation
            drop = i;
        }
    }
    if (drop == -1) return true;                 // already sorted: rotation by zero
    return nums[n - 1] <= nums[0];               // the edge from last back to first must not descend either
}

Complexity. Time O(n), one pass. Space O(1).

Why is nums[n - 1] <= nums[0] the right test and not something about nums[drop]? Because the rotation reassembles as nums[drop..n-1] followed by nums[0..drop-1]. Both pieces are already known to be sorted (there was only one descent), so the reassembled array is sorted exactly when the junction nums[n - 1] -> nums[0] is non-decreasing.

Approach 3: Optimal, count descents on the circle

Intuition. Approach 2 treats the junction between the last and first element as a special case. It does not have to be one. Think of the array as a circle: element i is followed by element (i + 1) % n, so the last element is followed by the first. On this circle, a rotation does nothing at all; it only changes where you start reading. A sorted array has exactly one descent on the circle (from its maximum back to its minimum), or zero if all values are equal. Therefore nums is a rotated sorted array if and only if its circular sequence has at most one descent.

Algorithm.

  1. For every i from 0 to n - 1, count the positions where nums[i] > nums[(i + 1) % n].
  2. Return whether the count is 0 or 1.
static boolean optimal(int[] nums) {
    int n = nums.length, drops = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] > nums[(i + 1) % n]) drops++;
    }
    return drops <= 1;
}

Dry run on nums = [3, 4, 5, 1, 2]:

i nums[i] nums[(i+1)%n] descent? drops
0 3 4 no 0
1 4 5 no 0
2 5 1 yes 1
3 1 2 no 1
4 2 3 no 1

drops = 1, answer true. On [2, 1, 3, 4] the pairs 2 -> 1 and 4 -> 2 both descend, drops = 2, answer false.

Complexity. Time O(n): n comparisons. Space O(1).

This is the version to remember. The same “count circular descents” trick also tells you the rotation amount for free: the original array begins right after the single descent (at index 3 in the dry run, where the 1 sits).

Edge cases and pitfalls