Check if Array is Sorted
Mahabharata — The Ordered Formation — Is Every Warrior Ranked Properly?
क्रम में है यह सेना? — देखो अंतिम जोड़ी। शेष क्रमबद्ध हो — और अंतिम दो भी॥
*Is this army in order? — Check the last pair. The rest must be sorted — and the last two as well.*
The Story
Check if an array is sorted in non-decreasing order using recursion.
For `arr=[1,2,3,4,5]`: true. For `arr=[1,3,2,4]`: false.
**Recursive approach:** - Base: n<=1 → sorted (single element or empty) - Recursive: arr[n-2] <= arr[n-1] AND sorted(arr, n-1)
```java boolean arraySortedOrNot(int[] arr, int n) { if (n <= 1) return true; // Base case return arr[n-2] <= arr[n-1] && // Last pair check arraySortedOrNot(arr, n-1); // Recurse on smaller array } ```
The recursion shrinks the problem from the end: "is this array of size n sorted?" = "is the last pair valid AND is the array of size n-1 sorted?".
Trace `[1,2,3]`: - sorted(arr,3): arr[1]=2<=arr[2]=3 ✓ && sorted(arr,2) - sorted(arr,2): arr[0]=1<=arr[1]=2 ✓ && sorted(arr,1) - sorted(arr,1): 1<=1 base → true - All return true ✓
Trace `[1,3,2]`: - sorted(arr,3): arr[1]=3<=arr[2]=2? No! → false immediately ✓
**Equivalent: check from the front:** ```java boolean sorted(int[] arr, int i) { if (i == arr.length-1) return true; return arr[i] <= arr[i+1] && sorted(arr, i+1); } ``` Same idea, just from the other end.
The Linear Scan
Single pass comparing consecutive elements. O(n), O(1) space.
boolean arraySortedOrNotIterative(int[] arr) {
for (int i=0;i<arr.length-1;i++)
if (arr[i]>arr[i+1]) return false;
return true;
}The End-Pair Recursion Wisdom
boolean arraySortedOrNot(int[] arr, int n) {
if (n <= 1) return true;
return arr[n - 2] <= arr[n - 1] && arraySortedOrNot(arr, n - 1);
}Step-by-Step Walkthrough
[3]: n=1 → true ✅ []: n=0 → true ✅
Deep Insight
**Short-circuit evaluation:** Java's `&&` short-circuits — if `arr[n-2] > arr[n-1]`, the recursive call is never made. This is important: it means we don't recurse further when a violation is found, giving O(1) in the best case (violation at end).
**O(n) call stack:** Each recursive call reduces n by 1. Stack depth = n-1.
**Tail recursion:** The recursive call is the last operation. Some languages optimize this to O(1) stack space, but Java doesn't do tail-call optimization.
**Pattern across rb-1 to rb-5:** These simple recursion problems all follow: base case + recursive relationship that shrinks the problem by 1.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Linear scan |
| Optimal | O(n) | O(n) | Call stack depth n |
Pattern Recognition
✅ Array sorted check → recursive end-pair ✅ Base: n<=1 → true ✅ Check last pair, recurse on n-1 ✅ Same logic works front-to-back with index i **LeetCode Trigger Phrases:** → "check if array is sorted" recursively → Validate ordering using recursion → Shrink-from-end recursion pattern
Bhagavad Gita 15.15
सर्वस्य चाहं हृदि सन्निविष्टो मत्तः स्मृतिर्ज्ञानमपोहनं च।
I am seated in the hearts of all. From Me come memory, knowledge, and their loss.
Connection: A sorted array maintains perfect order throughout — each element knows its place relative to the next. The recursive check verifies this dharmic order from the end inward: the last pair must respect the ordering, and so must everything before it. This mirrors the divine oversight described in the Gita — each element in its correct position, the whole reflecting cosmic order through the simple recursive principle that every adjacent pair maintains precedence.