Check if an Array is Sorted
Table of Contents + −
This one looks easy, right? But the interviewer is not really asking “can you check sorting”. They want to see if you can scan an array cleanly in one go, without doing any extra work. So let us talk it through the way you would in the room.
🔍 The Problem
You are given an array of numbers. You have to tell whether it is sorted in non-decreasing order. Non-decreasing means each element is greater than or equal to the one before it. So equal neighbours are fine. For example, [2, 2, 3] is still sorted.
Here is what that looks like:
Input: [1, 2, 2, 5, 9]Output: true
Input: [1, 4, 3, 6]Output: false (4 comes before 3, so it breaks)🐢 The Simple (But Wasteful) Approach
The first idea that pops into many heads is this. Sort a copy of the array. Then check if the copy matches the original. If they match, it was already sorted.
It works. But sorting costs O(n log n) time. And you also use extra space for the copy. That is a lot of effort just to answer a yes or no question. The interviewer will gently ask, “can you do better?”
⚡ The Optimal Approach: One Pass
Here is the smarter way. You do not need to sort anything. Just walk through the array once. At each step, compare the current element with the one right before it. If you ever find an element that is smaller than its previous neighbour, the order is broken. So you return false right away. If you reach the end without breaking, it is sorted.
This is one pass. So it is O(n) time and no extra space.
Steps to check if an array is sorted:
- Start from the second element (index 1).
- Compare it with the element just before it.
- If the current element is smaller than the previous one, return false.
- Move to the next element and repeat.
- If the loop finishes without returning, return true.
def is_sorted(arr): # walk from the second element to the end for i in range(1, len(arr)): # an element smaller than its previous one breaks the order if arr[i] < arr[i - 1]: return False return True
a = [1, 2, 2, 5, 9]b = [1, 4, 3, 6]
print(is_sorted(a))print(is_sorted(b))The output of the above code will be:
TrueFalse⏱️ Time and Space Complexity
Here is how the two approaches stack up:
| Approach | Time | Space |
|---|---|---|
| Sort a copy and compare | O(n log n) | O(n) |
| One pass (optimal) | O(n) | O(1) |
Tip
In an interview, mention that you can stop and return false the moment you find the first broken pair. You do not have to scan the whole array. This early exit is what makes the one-pass solution feel clean and fast.
🧩 Key Takeaways
- ✅ You only need a single pass. Compare each element with the one before it.
- ✅ Non-decreasing order allows equal neighbours. So use “smaller than” for the broken check, not “less than or equal”.
- ✅ The one-pass method is O(n) time and O(1) space. That is far better than sorting a copy.
- ✅ Return false as soon as you find the first out-of-order pair. No need to keep going.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
What does 'non-decreasing order' allow that 'strictly increasing' does not?
Why: Non-decreasing means each element is greater than or equal to the previous one, so equal neighbours like [2, 2] are fine.
- 2
What is the time complexity of the one-pass approach?
Why: You visit each element at most once, so the work grows linearly with the array size.
- 3
When can you stop scanning and return false?
Why: As soon as you find one pair that is out of order, the array cannot be sorted, so you exit early.
- 4
Why is sorting a copy and comparing considered wasteful here?
Why: Sorting costs O(n log n) time plus O(n) space, which is far more than the O(n) time and O(1) space the single pass needs.