Check if an array is sorted or not using recursive approach!
Find out if an array is sorted or not using recursive approach.
Table of contents
Problem Statement:
You will have given an array. You need to find out if the array is sorted in ascending order or not. Remember equal values are allowed.
Approach:
Let's follow the below algorithm:
If the length of the array is 0 or 1, return true. (Base Condition)
Check if the last two values of the array are sorted. Make a recursive call with a decrement in the length of the array. If values are not sorted return false.
If all values will be sorted, then the length of the array will be 1 and the base condition will hit.
Solution:
The following code is in JavaScript:
function isArraySorted(arr, n) {
/*
* base case
* 1. if array length is (0||1)
* that means we don't need to validate.
* 2. if array already checked all values using recursive call.
*/
if (n == 1 || n == 0){
return true;
}
/*
* 1. if first value is greater than second from last.
* 2. Equal values are allowed.
*/
if (arr[n - 1] < arr[n - 2]){
return false;
}
/*
* Make recursive call
*/
return isArraySorted(arr, n - 1);
}
let sampleArray = [10, 20, 20, 40, 80, 90];
let length = sampleArray.length;
let ans = isArraySorted(sampleArray, length);
console.log({ ans });
console.log('--------------');
sampleArray = [10, 20, 20, 100, 80, 90];
length = sampleArray.length;
ans = isArraySorted(sampleArray, length);
console.log({ ans });
Output:
You will able to see the following output in the console.
{ ans: true }
--------------
{ ans: false }
Time Complexity: O(n) Auxiliary Space: O(n) for Recursion Call Stack.
Happy Codings ๐ง๐ผโ๐ป
ย