Problem Statement

Given an array nums of n integers, return true if array nums is sorted else false.

Examples

Example 1

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

Explanation : For all i (1 <= i <= 4) it holds nums[i] <= nums[i+1], hence it is sorted and we return true.

Example 2

Input : nums = [1, 2, 1, 4, 5]
Output : false

Explanation : For i == 2 it does not hold nums[i] <= nums[i+1], hence it is not sorted and we return false.

Constraints

1 <= n <= 100
1 <= nums[i] <= 100

Approaches

1️⃣ Checking Consecutive Elements

Intuition:

To determine if an array is sorted in non-decreasing order using recursion, consider comparing each element with the one following it. If an element exceeds the next one, the array is not sorted. This comparison is then repeated for the entire array.

Approach:

1. If the array has 0 or 1 elements, it is already sorted. So, return true.
2. Use a helper function sort that takes the array and two pointers, left and right, to compare elements.
3. In the helper function, check if the array is sorted by comparing elements at the left and right pointers; if right reaches the end of the array, the array is sorted, so return true; if the element at left is greater than the element at right, return false because the array is not sorted; otherwise, move both pointers to the next elements and call the helper function recursively.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isSorted(vector<int>& nums) {
        // An array with 0 or 1 element is always considered sorted
        if (nums.size() <= 1) {
            return true;
        }
        // Check if the array is sorted starting from index 0 to 1
        return sort(nums, 0, 1);
    }

private:
    bool sort(vector<int>& nums, int left, int right) {
        // If we reach the end of the array
        // it means the array is sorted
        if (right >= nums.size()) {
            return true;
        }
        // If we find a pair where the left element is greater than the right 
        // the array is not sorted
        if (nums[left] > nums[right]) {
            return false;
        }
        // Move to the next pair of elements
        return sort(nums, left + 1, right + 1);
    }
};

// Main method for testing the isSorted function
int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5}; 
    bool result = solution.isSorted(nums); 
    cout << (result ? "Array is sorted" : "Array is not sorted") << endl; 
    return 0;
}

Complexity Analysis:

• Time Complexity O(N): The time complexity of this recursive solution is O(N) because the helper function makes a recursive call for each element in the array, moving from the beginning to the end of the array.
• Space Complexity O(N): The space complexity of this solution is O(N) Due to the recursion stack. Each recursive call adds a new frame to the call stack, and in the worst case, there will be n frames on the stack (one for each call).