Check if an Array is Sorted in Python | DSA Interview Guide
Check if an Array is Sorted in Python | DSA Interview Guide
Mohan Pardhi
6/25/20263 min read
Check if an Array is Sorted in Python | DSA Interview Guide
Introduction
Arrays are one of the most important data structures in programming and Data Structures & Algorithms (DSA). Before performing many operations such as Binary Search, Merge Operations, or Optimization Techniques, it is often necessary to verify whether an array is sorted.
In coding interviews, a common beginner-level question is:
"Given an array, determine whether it is sorted in non-decreasing order."
Although this problem appears simple, it tests your understanding of array traversal, comparison logic, time complexity, and edge cases.
In this article, we'll learn:
What a sorted array is
Different approaches to check if an array is sorted
Python implementations
Time and space complexity analysis
Interview tips
Companies that ask this question
What Does It Mean for an Array to Be Sorted?
An array is considered sorted in ascending order if every element is greater than or equal to the previous element.
Example 1: Sorted Array
arr = [1, 2, 3, 4, 5]
Here:
1 <= 2 <= 3 <= 4 <= 5
Therefore, the array is sorted.
Example 2: Sorted with Duplicates
arr = [1, 2, 2, 3, 5]
Since duplicates are allowed:
1 <= 2 <= 2 <= 3 <= 5
This array is also sorted.
Example 3: Unsorted Array
arr = [1, 3, 2, 5, 4]
Notice:
3 > 2
The order breaks, so the array is not sorted.
Approach 1: Linear Traversal (Recommended)
The simplest and most efficient approach is to compare every element with its next element.
If at any point:
arr[i] > arr[i + 1]
the array is not sorted.
Otherwise, it is sorted.
Algorithm
Traverse the array from index 0 to n-2.
Compare current element with next element.
If current element is greater than next element:
Return False.
If traversal completes:
Return True.
Python Code
def is_sorted(arr): n = len(arr) for i in range(n - 1): if arr[i] > arr[i + 1]: return False return True arr = [1, 2, 3, 4, 5] if is_sorted(arr): print("Array is sorted") else: print("Array is not sorted")
Output
Array is sorted
Dry Run Example
Consider:
arr = [10, 20, 30, 25, 40]
Iteration 1
10 <= 20
Valid
Iteration 2
20 <= 30
Valid
Iteration 3
30 > 25
Order breaks.
Return:
False
Approach 2: Compare with Sorted Version
Another approach is to create a sorted copy and compare it with the original array.
Python Code
def is_sorted(arr): return arr == sorted(arr)
Example
arr = [1, 2, 3, 4, 5] print(is_sorted(arr))
Output
True
Why This Is Not Preferred in Interviews?
Although concise, this method:
Creates a new array.
Requires sorting.
Uses extra memory.
Complexity
Sorting requires:
O(n log n)
while the previous method takes:
O(n)
Hence interviewers usually expect the linear traversal approach.
Approach 3: Using Python all()
Python provides the built-in all() function.
Python Code
def is_sorted(arr): return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))
Example
arr = [1, 2, 3, 4, 5] print(is_sorted(arr))
Output
True
This is elegant and often appreciated in Python-specific interviews.
Time and Space Complexity
Approach 1 (Linear Traversal)
Complexity TypeValueTime ComplexityO(n)Space ComplexityO(1)
Approach 2 (Sorting)
Complexity TypeValueTime ComplexityO(n log n)Space ComplexityO(n)
Approach 3 (all())
Complexity TypeValueTime ComplexityO(n)Space ComplexityO(1)
Edge Cases to Consider
Empty Array
[]
An empty array is considered sorted.
Single Element Array
[10]
A single element array is always sorted.
Array with Duplicates
[1, 1, 2, 2, 3]
Still sorted.
Descending Array
[5, 4, 3, 2, 1]
Not sorted in ascending order.
Interview Question Variations
Once you understand this problem, interviewers may ask follow-up questions:
1. Check if Array is Sorted in Descending Order
Example:
[9, 7, 5, 2]
2. Check if Array is Strictly Increasing
Example:
[1, 2, 3, 4]
Valid
[1, 2, 2, 4]
Invalid
3. Check if Array Can Become Sorted After One Swap
Example:
[1, 5, 3, 4, 2]
4. Check if Array is Rotated Sorted
Example:
[4, 5, 1, 2, 3]
This is a popular interview variant.
Companies That Ask This Question
This question frequently appears in:
Google
Amazon
Microsoft
Adobe
Walmart Global Tech
Infosys
TCS Digital
Accenture
Cognizant
Wipro
Capgemini
Zoho
Paytm
Flipkart
PhonePe
ServiceNow
Freshworks
It is commonly asked during:
Online Assessments
Coding Rounds
Campus Placements
DSA Screening Interviews
More often, it appears as a building block for larger array problems rather than as a standalone question.
Interview Tips
Tip 1
Always discuss the brute-force and optimal approaches.
Tip 2
Mention time complexity before writing code.
Tip 3
Handle edge cases:
[] [10] [1,1,1]
Tip 4
Prefer the O(n) traversal solution during interviews.
Tip 5
Explain your thought process clearly instead of jumping directly into coding.
Complete Interview-Ready Solution
def is_sorted(arr): for i in range(len(arr) - 1): if arr[i] > arr[i + 1]: return False return True arr = [1, 2, 3, 4, 5] print(is_sorted(arr))
Output
True
Conclusion
Checking whether an array is sorted is one of the most fundamental DSA problems. While the problem is straightforward, it teaches important concepts such as array traversal, comparison logic, optimization, and complexity analysis.
For interviews, the best solution is to traverse the array once and verify that every element is less than or equal to the next element. This approach achieves:
Time Complexity: O(n)
Space Complexity: O(1)
Mastering such foundational problems creates a strong base for solving advanced array questions that frequently appear in coding interviews at top product and service-based companies.