Introduction

Checking whether an array is sorted means verifying if the elements are arranged in increasing order.

Given an array of integers arr[]  of size n, the task is to determine whether the array is sorted in non-decreasing order.

This is a fundamental array problem that helps in understanding array traversal, adjacent comparisons, and validation techniques.

Example:

Input: arr[] = [1, 2, 3, 4, 5]Output: True
Explanation:
Each element is smaller than or equal to the next element.
Therefore, the array is sorted.

Input: arr[] = [2, 5, 1, 8, 9]
Output: False
Explanation:
5 is greater than 1.
Therefore, the array is not sorted.

Constraints

1 <= n <= 10^5
-10^9 <= arr[i] <= 10^9

Explanation

The simplest way to check whether an array is sorted is:

  1. Traverse the array
  2. Compare every element with the next element
  3. If any element is greater than the next element, the array is not sorted

This approach is simple and easy to understand.

Steps

  1. Traverse the array from index 0 to n-2.
  2. Compare current element with next element.
  3. If current element is greater:
    • return False
  4. If traversal completes successfully:
    • return True

Dry Run

Input Array: [1, 2, 3, 4, 5]Compare 1 and 2:
1 <= 2
Array remains sorted
Compare 2 and 3:
2 <= 3
Array remains sorted
Compare 3 and 4:
3 <= 4
Array remains sorted
Compare 4 and 5:
4 <= 5
Array remains sorted
No violation found.
Final Result: True

Brute Force Code (Python)

Complexity Analysis

Time Complexity: O(n)Explanation:
The array is traversed once.
Each adjacent pair is checked exactly one time.

Space Complexity: O(1)
Explanation:
No extra data structures are used.
Only a boolean variable is required.

Approach 2 : Optimized Solution

Explanation

The traversal solution itself is already the optimized solution because every adjacent pair may need to be checked once.

Therefore:

  • O(n) is the best possible time complexity.
  • Constant extra space is sufficient.

This makes the comparison approach both simple and optimal.

Steps

  1. Traverse the array.
  2. Compare current element with next element.
  3. If any element violates sorted order:
    • return False
  4. Otherwise:
    • return True

Dry Run

Input Array: [2, 5, 1, 8, 9]Compare 2 and 5:
2 <= 5
Array remains sorted
Compare 5 and 1:
5 > 1
Sorted order is violated
Final Result: False

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Every adjacent pair is checked once.

Space Complexity: O(1)
Explanation:
No extra array or data structure is required.

Edge Cases

  1. Array contains only one element
  2. Array contains duplicate elements
  3. Array contains negative numbers
  4. Array is already sorted
  5. Array is completely unsorted

Why This Problem is Important

This problem helps in understanding:

  1. Array traversal
  2. Adjacent comparisons
  3. Validation techniques
  4. Early termination logic
  5. Searching and sorting foundations

It is one of the most important beginner-level array problems.

Real-World Applications

Checking sorted arrays is used in:

  1. Binary Search validation
  2. Database indexing
  3. Ranking systems
  4. Data verification systems
  5. Sorted dataset processing

Common Mistakes

  1. Comparing wrong indices
  2. Forgetting edge cases
  3. Traversing beyond array bounds
  4. Not handling equal elements properly

Interview Tips

Interviewers often expect:

  1. An O(n) traversal solution
  2. Proper handling of duplicate elements
  3. Early termination optimization

Always explain why checking adjacent elements is sufficient.

Related Questions

  1. Binary Search
  2. Monotonic Array
  3. Find Peak Element
  4. Search Insert Position
  5. Rotate Sorted Array

Final Takeaway

Checking whether an array is sorted is an important beginner-level DSA problem that teaches traversal logic, adjacent comparisons, and validation techniques. Understanding this problem builds strong foundations for searching and optimization problems.