Check if an Array Is Sorted
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
- 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-109 ≤ nums[i] ≤ 109
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.
- Input
- nums = [2, 5, 4, 9]
- Output
- false
- Explanation
- The step from 5 to 4 goes down. One such step is enough to make the array unsorted, even though 9 at the end is the largest value, so the answer is
false.
+16 hidden tests on Submit
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.
If an array is not sorted, where in it can you see that? Do you need to compare elements that are far apart?
It is enough to compare each element with the one right after it. Equal neighbours are allowed; only a step down breaks the order.
Loop over the neighbouring pairs and return
falseat the first pair where the left value is greater than the right one. If no such pair exists, returntrue.
Solution
An array is sorted exactly when no element is larger than the one right after it. You never need to compare elements that are far apart: if every neighbouring pair is in order, the whole array is. That turns the check into one pass over n-1 pairs that can stop at the first step down.
Sort a copy and compare
Intuition
A sorted array is the one that sorting would not change. So make a copy of nums, sort the copy, and check whether it matches the original position by position. If every position matches, nums was already in order.
For [2, 5, 4, 9], the sorted copy is [2, 4, 5, 9]. Position 1 holds 5 in the original and 4 in the copy, so the answer is false. For [1, 3, 3, 7], the copy is identical and the answer is true.
This is correct, but it does more than the question asks. Sorting costs O(n log n), about 6 × 10^4 comparisons for 5000 numbers, and the copy takes O(n) memory. It also always reads the whole array, even when the very first pair is already out of order.
Algorithm
- Copy
numsso the original stays unchanged. - Sort the copy in increasing numeric order.
- Compare the copy with
numsposition by position. - Return
trueif every position matches,falseotherwise.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsCompare each pair of neighbours
Intuition
You do not need the sorted version to know whether the array is sorted. An array is in non-decreasing order exactly when each element is at most the one right after it. Because ≤ chains (a ≤ b and b ≤ c give a ≤ c), checking the n-1 neighbouring pairs covers every pair of positions.
Walk i from 1 to n-1 and compare nums[i-1] with nums[i]. For [2, 5, 4, 9], the pair (2, 5) is fine and the pair (5, 4) steps down, so you return false right there without looking at 9. Equal neighbours pass, because only > fails.
Each pair is compared once, so the time is O(n), and the loop index is the only extra memory, O(1). Compare the two values directly rather than subtracting them: with values up to 10^9, a difference can overflow a 32-bit int.
Algorithm
- Loop
ifrom 1 ton-1. - If
nums[i-1] > nums[i], returnfalse. - 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
The loop is short, so the bugs sit at its edges and in the comparison.
- Treating equal neighbours as a failure. Testing
nums[i-1] >= nums[i]rejects[1, 3, 3, 7]. Only a strict step down (>) breaks the order. - Reading past the end. A loop from
0ton-1that comparesnums[i]withnums[i+1]must stop one early, or it reads outside the array. Starting ati = 1and comparing withi-1avoids the problem. - Subtracting instead of comparing.
nums[i] - nums[i-1] >= 0looks the same, but10^9 - (-10^9) = 2 × 10^9does not fit in a 32-bit int and wraps to a negative number, so[-1000000000, 1000000000]is reported unsorted. The same overflow breaks a qsort comparator written asx - y. - Sorting numbers as text. In JavaScript,
sort()with no compare function puts10before9, so a sort-and-compare check gives wrong answers.
Frequently asked questions4
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.
Why is checking neighbours enough?
The order relation chains: if a ≤ b and b ≤ c, then a ≤ c. So when every adjacent pair is in order, every pair of positions is in order too. Conversely, any unsorted array has at least one adjacent pair where the value goes down.
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, and it gives the right answer, but it costs O(n log n) time and O(n) extra memory for the copy. The neighbour check is faster, needs no copy, and can return at the first step down without reading the rest.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def isSorted(nums):
# Write code hereCase 1
Case 2
Input
nums = [1, 3, 3, 7]
Expected
true