Introduction

Check Sorted Array means:

  • verifying whether array elements
  • are arranged in increasing order

A sorted array satisfies:

arr[i] <= arr[i+1]

Example:

Input:
1 2 3 4 5

Output:
True

Explanation:

Every element is smaller than or equal to the next element.

This problem is one of the most important applications of:

Recursion on Arrays

Constraints

1 <= Array Size <= 10^5

Approach 1 : Iterative Solution

Explanations:

Explanation:

The idea is:

  • compare adjacent elements
  • verify sorted order

Steps:

  1. Traverse array.
  2. Compare current and next element.
  3. If incorrect order found:
    return false.
  4. Otherwise array is sorted.

This approach:

  • is simple
  • avoids recursion

Dry Run

Array:
1 2 3 4 5

Compare:
1 <= 2

Compare:
2 <= 3

Compare:
3 <= 4

Compare:
4 <= 5

Array is sorted.

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :Array is traversed once.

Space Complexity:- O(1)
Explanation :
No extra space is used.

Approach 2 : Recursive Solution

Explanations:

Explanation:

This is the most important recursion-based solution.

The idea is:

  • compare current element
  • with next element
  • recursively check remaining array

Base Case:

  • when index reaches end

Recursive Case:

  • check current pair
  • recurse for next index

Dry Run

Array:
1 2 3 4 5

Check:
1 <= 2

Check:
2 <= 3

Check:
3 <= 4

Check:
4 <= 5

Reached end.
Array is sorted.

Practice :

Complexity Analysis :

Time Complexity:- O(n)
Explanation :
Recursive calls run n times.

Space Complexity:- O(n)
Explanation :
Recursion stack is used.

Why This Problem is Important

This problem builds the foundation for:

  • Recursion on arrays
  • Recursive traversal
  • Array validation
  • Recursive thinking
  • Sorting concepts

Real-World Applications

Sorted array checking concepts are used in:

  • Database validation
  • Search optimizations
  • Data verification
  • Sorting algorithms
  • Analytics systems

Common Beginner Mistakes

  • Missing base case
  • Wrong comparison operator
  • Index out of bounds
  • Infinite recursion
  • Incorrect recursion flow

Interview Tip

Interviewers often expect:

  • recursion understanding
  • correct base case
  • recursive traversal logic
  • iterative vs recursive comparison

Always explain:

  • base condition
  • recursive step
  • adjacent comparison logic

Related Questions

  • Sum of Array Elements
  • Binary Search
  • Recursion Basics
  • Check Palindrome
  • Sorted Linked List

Final Takeaway

The Check Sorted Array problem is one of the most important beginner recursion array problems.

It teaches:

  • recursion on arrays
  • recursive traversal
  • array validation
  • recursive thinking

Understanding this problem builds a strong foundation for:

  • advanced recursion problems
  • sorting algorithms
  • interview-level data structure questions.