Check if an Array Is Sorted

Q: Is an array with equal elements sorted?

In non-decreasing order, yes: [4, 4, 4] is sorted because no element is larger than the next. If a problem asks for strictly increasing order instead, change the test to reject equal neighbours as well.

Q: Can I sort a copy and compare it with the original?

Yes, it gives the right answer, but it costs O(n log n) time and O(n) extra memory. The neighbour check needs no copy and can stop at the first step down.

BeginnerArrays and strings

+10

You get an array of integers nums. Return true if it is in non-decreasing order, meaning every element is less than or equal to the one after it, and false otherwise. Equal neighbours are fine: [2, 2, 3] counts as sorted. An array with one element is sorted.

Function

isSorted(nums: integer-array) → boolean

numsinteger-array: the array of integers to check
Returnsboolean: true when every element is at most the next one, false otherwise

Constraints

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Examples

Input: nums = [1, 3, 3, 7]
Output: true
Explanation: Each step goes up or stays level: 1 to 3, 3 to 3, 3 to 7. The repeated 3 is allowed, so the answer is true.

Follow-up

How would you check an array that may be sorted in either direction, increasing or decreasing, still in one pass?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

An array is sorted exactly when no element is larger than the one right after it. So one pass over the n-1 neighbouring pairs decides it, and the pass can stop at the first step down.

Sort a copy and compare

Intuition

A sorted array is the one that sorting would not change: sort a copy and compare it with nums position by position. For [2, 5, 4, 9] the copy [2, 4, 5, 9] differs at position 1, so the answer is false.

Sorting costs O(n log n), about 6 × 10^4 comparisons for 5000 numbers, plus O(n) memory for the copy, and it reads the whole array even when the first pair is already out of order.

Algorithm

Copy nums so the original stays unchanged.
Sort the copy in increasing numeric order.
Compare the copy with nums position by position.
Return true if every position matches, false otherwise.

def isSorted(nums):
    # sorted returns a new list, so nums itself is left as it was.
    return sorted(nums) == nums

Compare each pair of neighbours

Intuition

Because ≤ chains (a ≤ b and b ≤ c give a ≤ c), the n-1 neighbouring pairs cover every pair of positions, and an unsorted array always has a neighbouring pair that goes down. So walk i from 1 to n-1 and return false at the first nums[i-1] > nums[i]. For [2, 5, 4, 9] that is the pair (5, 4), and 9 is never read. Equal neighbours pass, because only > fails.

Each pair is compared once: O(n) time and O(1) memory.

Algorithm

Loop i from 1 to n-1.
If nums[i-1] > nums[i], return false.
If the loop finishes, return true. A single element skips the loop and is sorted.

def isSorted(nums):
    for i in range(1, len(nums)):
        # One step down anywhere breaks the order.
        if nums[i - 1] > nums[i]:
            return False
    return True

Pitfalls and edge cases

Treating equal neighbours as a failure. Testing nums[i-1] >= nums[i] rejects [1, 3, 3, 7].
Reading past the end. A loop from 0 to n-1 that compares nums[i] with nums[i+1] reads outside the array on its last step. Start at i = 1 and compare with i-1.
Subtracting instead of comparing. nums[i] - nums[i-1] >= 0 overflows a 32-bit int on [-1000000000, 1000000000]: 2 × 10^9 wraps negative and the array is reported unsorted. A qsort comparator written as x - y breaks the same way.
Sorting numbers as text. In JavaScript, sort() with no compare function puts 10 before 9, so sort-and-compare gives wrong answers.

Frequently asked questions3

How do you check if an array is sorted?

Compare each element with the next one. If any element is greater than its right neighbour, the array is not sorted and you can stop; if you reach the end without finding one, it is. That takes O(n) time and O(1) extra space.

Is an array with equal elements sorted?

In non-decreasing order, yes: [4, 4, 4] is sorted because no element is larger than the next. If a problem asks for strictly increasing order instead, change the test to reject equal neighbours as well.

Can I sort a copy and compare it with the original?

Yes, it gives the right answer, but it costs O(n log n) time and O(n) extra memory. The neighbour check needs no copy and can stop at the first step down.

def isSorted(nums):
    # Write code here

Test #1

Test #2

Argument

nums = [1, 3, 3, 7]

Expected Output

true