Problem

Given an array of integer write a recursive solution to check if array is sorted.

Examples

Example 1:

Input: arr = [1, 2, 3, 4, 5]
Output: true

Example 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

Java
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
    }
}
Python
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

Java
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
    }    
}
Python
# 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.