Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Check Whether an Array Is Sorted

Verify nondecreasing order by checking each adjacent pair once.

EasyArraysPattern: array traversal

Problem statement

Return true when an integer array is sorted in nondecreasing order. Equal neighboring values are allowed.

[1, 2, 2, 5] is sorted. [1, 4, 3] is not.

Constraints & requirements

INPUT
An integer array
RETURN
true for nondecreasing order
EDGE
Empty and one-value arrays are sorted

Examples 3 test cases

  1. Example 1 Equal neighbours

    Input
    [1, 2, 2, 5]
    Output
    true

    Confirms nondecreasing order allows equality.

  2. Example 2 First inversion

    Input
    [3, 2, 4]
    Output
    false

    Finds a descending adjacent pair.

  3. Example 3 One value

    Input
    [6]
    Output
    true

    Checks the smallest nonempty input.

Hints Optional

Hints become more specific one step at a time.
01Look for proof of failure

The first descending adjacent pair is enough to return false.

02Start from the second value

Index 0 has no previous neighbor, so comparisons begin at index 1.

03Allow equal values

The array fails only when values[index] is smaller than values[index - 1].

How to think before coding

A brute-force check compares every earlier/later pair. Ask whether all of those comparisons are necessary: if every adjacent pair is ordered, transitivity orders every wider pair too. Therefore start at index 1, compare it with index 0, and return false at the first strict drop. Reaching the end is the proof for true; equality is not a failure.

Brute force and the improvement

Checking every earlier value against every later value costs O(n²) time and O(1) space. It repeats what adjacent comparisons establish. Sorting a copy and comparing it with the original costs O(n log n) time and O(n) space for the copy. Sorting the original alone cannot tell you whether it was sorted before the change.

Intuition

The entire array is sorted only if every neighboring pair is in the correct order. The first pair where values[i] is smaller than values[i - 1] proves that the answer is false.

Java solution

Java
public static boolean isSorted(int[] values) {
    // Null is not an array. An actual empty array is considered sorted.
    if (values == null) {
        return false;
    }

    for (int index = 1; index < values.length; index++) {
        // A strict drop breaks nondecreasing order; equality is allowed.
        if (values[index] < values[index - 1]) {
            return false; // One violation proves the answer; stop immediately.
        }
    }
    return true; // Every adjacent pair passed.
}

Dry run

Numbered illustrated dry run for Check Whether an Array Is Sorted; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For [1, 4, 3], compare adjacent pairs, not every possible pair.

Index Previous Current Decision
1 1 4 No decrease: continue
2 4 3 Decrease: return false immediately

For [1, 2, 2, 5], all comparisons pass. The equal pair 2, 2 is valid.

Complexity

Time is O(n) in the worst case and extra space is O(1). The method can return early when it finds a violation.

Common mistake

Use < rather than <= when duplicates are valid in nondecreasing order.

Practice next

Next lessonRemove Duplicates from a Sorted Array

Use sorted order to compact repeated values.

Back to Arrays →