Skip to main content

Check if Array is Sorted

Problem Statement:​

Given an array arr[], check whether it is sorted in non-decreasing order. Return true if it is sorted otherwise false.

  • Example:

    Examples:

    Input: arr[] = [10, 20, 30, 40, 50]
    Output: true
    Explanation: The given array is sorted.
    Input: arr[] = [90, 80, 100, 70, 40, 30]
    Output: false
    Explanation: The given array is not sorted.

✅ Solution: Brute Force – Single Pass​

class Solution {
  public:
    bool isSorted(vector<int>& arr) {
        // Traverse the array from index 1 to end
        for(int i = 1; i < arr.size(); i++){
            // If any previous element is greater, it's not sorted
            if(arr[i - 1] > arr[i]){
                return false;
            }
        }
        // If no such pair is found, the array is sorted
        return true;
    }
};

📝 How It Works​

  • The function iterates from the second element to the last.
  • For each element, it compares it with its previous one.
  • If at any point the current element is less than the previous one, it returns false (not sorted in non-decreasing order).
  • If the loop completes without finding such a pair, it returns true.

🧩 Key Formula / Recurrence​

  • There’s no recurrence – just a linear scan with the check:

    if arr[i-1] > arr[i] → not sorted

⏱️ Time & Space Complexity​

ComplexityValue
TimeO(N)
SpaceO(1)

⚠️ Edge Cases​

  • Empty array [] → considered sorted ✅
  • Single-element array [42] → sorted ✅
  • All elements equal [3, 3, 3] → sorted ✅
  • Strictly decreasing [5, 4, 3] → not sorted ❌

💡 Other Approaches​

ApproachTimeNotes
STL is_sorted()O(N)Use return is_sorted(arr.begin(), arr.end()); for cleaner code
Compare to sorted copyO(N log N)Make a sorted version and compare – inefficient for this task ❌

🔁 Related Problems​

  • Check if array is strictly increasing
  • Count the number of unsorted pairs in an array
  • Sort an array using minimum swaps

🛠️ Other Notes​

  • This is an ideal use-case for a simple scan, no need for recursion or extra space.
  • This is stable for arrays with duplicates and works well for real-time checks like verifying if logs, scores, or timestamps are in order.
💬

Discussion & Doubts