Problem#
Given an array of integer write a recursive solution to check if array is sorted.
Examples#
Example 1:
1
2
|
Input: arr = [1, 2, 3, 4, 5]
Output: true
|
Example 2:
1
2
|
Input: arr = [1, 3, 2, 4, 5]
Output: false
|
Solution#
Method 1 - Iterative#
Here is the approach:
- Traverse the array from the beginning to the end.
- Compare each element with the next one to ensure the current element is less than or equal to the next element.
- If any element is greater than the next one, return
false.
- If the loop completes successfully, return
true.
Code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
public class Solution {
// Iterative solution
public boolean isSortedIterative(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
// Recursive solution
public boolean isSortedRecursive(int[] arr) {
return isSortedRecursiveHelper(arr, 0);
}
private boolean isSortedRecursiveHelper(int[] arr, int index) {
if (index >= arr.length - 1) {
return true;
}
if (arr[index] > arr[index + 1]) {
return false;
}
return isSortedRecursiveHelper(arr, index + 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr1 = {1, 2, 3, 4, 5};
System.out.println("Is array sorted (Iterative): "
+ solution.isSortedIterative(arr1)); // Output: true
int[] arr2 = {1, 3, 2, 4, 5};
System.out.println("Is array sorted (Iterative): "
+ solution.isSortedIterative(arr2)); // Output: false
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def is_sorted_iterative(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
# Example usage
arr1 = [1, 2, 3, 4, 5]
print(
f"Is array {arr1} sorted (Iterative): {is_sorted_iterative(arr1)}"
) # Output: true
arr2 = [1, 3, 2, 4, 5]
print(
f"Is array {arr2} sorted (Iterative): {is_sorted_iterative(arr2)}"
) # Output: false
|
Complexity#
- ⏰ Time complexity:
O(n), where n is the number of elements in the array, as we traverse the array once.
- 🧺 Space complexity:
O(1), as we use a constant amount of extra space.
Method 2 - Recursive#
Here is the approach:
- Use recursion to compare each element with the next one.
- Check if the first element is less than or equal to the second element, and recursively check the rest of the array.
- Base case: If the array has only one element or is empty, return
true.
Code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public class Solution {
// Recursive solution
public boolean isSortedRecursive(int[] arr) {
return isSortedRecursiveHelper(arr, 0);
}
private boolean isSortedRecursiveHelper(int[] arr, int index) {
if (index >= arr.length - 1) {
return true;
}
if (arr[index] > arr[index + 1]) {
return false;
}
return isSortedRecursiveHelper(arr, index + 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr1 = {1, 2, 3, 4, 5};
System.out.println("Is array sorted (Recursive): "
+ solution.isSortedRecursive(arr1)); // Output: true
int[] arr2 = {1, 3, 2, 4, 5};
System.out.println("Is array sorted (Recursive): "
+ solution.isSortedRecursive(arr2)); // Output: false
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
# Recursive solution
def is_sorted_recursive(arr, index=0):
if index >= len(arr) - 1:
return True
if arr[index] > arr[index + 1]:
return False
return is_sorted_recursive(arr, index + 1)
# Example usage
arr1 = [1, 2, 3, 4, 5]
print(
f"Is array {arr1} sorted (Recursive): {is_sorted_recursive(arr1)}"
) # Output: true
arr2 = [1, 3, 2, 4, 5]
print(
f"Is array {arr2} sorted (Recursive): {is_sorted_recursive(arr2)}"
) # Output: false
|
Complexity#
- ⏰ Time complexity:
O(n)
- 🧺 Space complexity:
O(n), due to the recursive call stack.