Given an array of integers, determine whether it is sorted in non-decreasing order using recursion.
Return true if every element is less than or equal to the element after it. Otherwise, return false.
Example 1
Input: arr = [10, 20, 30, 40, 50]
Output: true
Explanation: Every consecutive pair of elements is in the correct increasing order, so the entire array is fully sorted.
Example 2
Input: arr = [10, 20, 15, 30]
Output: false
Explanation: The number 20 is greater than 15. Because this adjacent pair is out of order, the array is not sorted.
Approach
An array is sorted in non-decreasing order when every element is less than or equal to the element immediately after it.
This means we do not need to compare one element with every other element. We only need to verify each adjacent pair. If arr[index] > arr[index + 1] at any point, the ordering is broken and the array cannot be sorted.
Recursion checks one adjacent pair at a time. When the current pair is valid, the function moves to index + 1 and checks the next pair. If recursion reaches the last element without finding an invalid pair, all adjacent pairs are correctly ordered, so the array is sorted.
Algorithm
Define a recursive function with the array and an
index, whereindexrepresents the first element of the adjacent pair currently being checked.If the array has fewer than two elements, or
indexreaches the last element, returntruebecause no unchecked adjacent pair remains.Compare
arr[index]witharr[index + 1]. Ifarr[index] > arr[index + 1], returnfalseimmediately because this pair violates non-decreasing order.Otherwise, recursively call the function with
index + 1to verify the next adjacent pair.The final result returned by the recursion tells whether every adjacent pair in the array is correctly ordered.
Dry Run
check sorted array dry run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Checks adjacent pairs recursively // starting from the given index. bool checkSorted( vector<int>& arr, int index ) { int n = arr.size(); // No unchecked adjacent // pair remains. if (index >= n - 1) { return true; } // One invalid pair proves // the array is not sorted. if (arr[index] > arr[index + 1]) { return false; } // Move forward to check // the next adjacent pair. return checkSorted( arr, index + 1 ); }public: // Checks whether the complete array // is sorted in non-decreasing order. bool isSorted(vector<int>& arr) { int n = arr.size(); // Empty and single-element arrays // are sorted by default. if (n <= 1) { return true; } return checkSorted(arr, 0); }};int main() { vector<int> arr = {1, 2, 4, 3, 5}; Solution solution; cout << ( solution.isSorted(arr) ? "true" : "false" ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because in the worst case, the function checks every adjacent pair once.
Space Complexity: O(N), because recursive calls remain on the call stack until the last element is reached.
FAQs
Q1. Why is checking only adjacent elements enough?
If every adjacent pair satisfies arr[i] <= arr[i + 1], the ordering continues throughout the array, which guarantees that the complete array is non-decreasing.
Q2. Why do we return false as soon as one pair is out of order?
A single pair where arr[i] > arr[i + 1] is enough to prove that the array is not sorted, so there is no need to check the remaining elements.
Q3. Are duplicate elements allowed in a sorted array?
Yes. Since the required order is non-decreasing, equal adjacent values are allowed.
Q4. What happens for an empty array or an array with one element?
Both are considered sorted because there is no adjacent pair that can violate the required order.
Q5. How would the condition change for descending order?
For non-increasing order, return false when arr[index] < arr[index + 1].
Q6. Can this be solved without recursion?
Yes. An iterative traversal can check the same adjacent pairs in O(N) time while using O(1) auxiliary space.
Be the first to add a comment.