Skip to main content
CodePeet

Check if an Array is Sorted

Try it yourself
EasyProblem

Description

Given an array arr, return true if it is sorted in non-decreasing order, each element at least as big as the one before it, and false otherwise. Equal neighbours are allowed.

Examples

Example 1

Input: arr = [1, 2, 2, 5]

Output: true

Explanation: Each element is at least the one before it; 2 and 2 are equal, which is allowed.

Example 2

Input: arr = [3, 1, 2]

Output: false

Explanation: 3 is bigger than the 1 after it.

Example 3

Input: arr = [7]

Output: true

Explanation: A single element is sorted.

Example 4

Input: arr = [1, 3, 2, 4]

Output: false

Explanation: 3 then 2 is out of order, even though the ends are fine.

Constraints

  • 1 ≤ arr.length ≤ 10^5
  • -10^9 ≤ arr[i] ≤ 10^9

Editorial

Approach - Compare Each Pair of Neighbours

Intuition

An array is sorted when each element is at least the one before it. If every neighbouring pair is in order, the whole array is: a ≤ b and b ≤ c give a ≤ c, all the way along. So one pass over the neighbours decides it, and the first pair out of order settles it as false.

Equal neighbours are fine, so a pair breaks the order only when the first is strictly bigger. Comparing with a sorted copy gives the same answer, but sorting costs O(n log n) and a second array.

Step-by-Step Explanation

Let's trace Example 4, arr = [1, 3, 2, 4]:

  1. 1 then 3: in order.
  2. 3 then 2: the first is bigger, so this pair is out of order.
  3. Return false; the rest doesn't matter.

Neighbour by Neighbour — Each element compared with the one before it until a pair is out of order.

Algorithm

  1. For each i from 1 to the end: if arr[i - 1] > arr[i], return false.
  2. Return true.

Code

class Solution {
public:
    bool isSorted(vector<int>& arr) {
        for (int i = 1; i < (int) arr.size(); i++) {
            if (arr[i - 1] > arr[i]) return false;  // a neighbour pair out of order
        }
        return true;
    }
};

from typing import List

class Solution:
    def isSorted(self, arr: List[int]) -> bool:
        for i in range(1, len(arr)):
            if arr[i - 1] > arr[i]:         # a neighbour pair out of order
                return False
        return True

class Solution {
    public boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) return false;  // a neighbour pair out of order
        }
        return true;
    }
}

var isSorted = function(arr) {
    for (let i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) return false;  // a neighbour pair out of order
    }
    return true;
};

Complexity Analysis

Time Complexity: O(n)

Each neighbouring pair is compared once.

Space Complexity: O(1)

Only the index.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Rejecting equal neighbours. arr[i - 1] >= arr[i]

On arr = [1, 2, 2, 5] it returns false; the answer is true. Non-decreasing allows equal neighbours: [1, 2, 2, 5] is sorted. Only a pair where the first is bigger breaks it, so the test is >, not >=.

Skipping the last pair. range(1, len(arr) - 1)

On arr = [1, 2, 4, 3] it returns true; the answer is false. range(1, len(arr) - 1) stops before the last index, so the last two elements are never compared, and an array that's only out of order at the end passes.

Comparing the ends only. return arr[0] <= arr[-1]

On arr = [1, 3, 2, 4] it returns true; the answer is false. The first element being at most the last says nothing about the middle: [1, 3, 2, 4] passes that test. Every neighbouring pair has to be in order.

Where This Pattern Is Taught

This problem practises one pass over an array, comparing each element with the one before it. It's taught in Introduction to Arrays.