Problem Statement: Given an array of size n, write a program to check if the given array is sorted in (ascending / Increasing / Non-decreasing) order or not. If the array is sorted then return True, Else return False.

**Example 1:**
Input: N = 5, array[] = {1,2,3,4,5}
Output: True.
Explanation: The given array is sorted i.e Every element in the array is smaller than or equals to its next values, So the answer is True.

**Example 2:**
Input: N = 5, array[] = {5,4,6,7,8}
Output: False.
Explanation: The given array is Not sorted i.e Every element in the array is not smaller than or equal to its next values, So the answer is False.
Here element 5 is not smaller than or equal to its future elements.

1. Brute Force Approach

Algorithm

• The idea is pretty simple here, We will start with the element at the 0th index, and will compare it with all of its future elements that are present in the array.
• If the picked element is smaller than or equal to all of its future values then we will move to the next Index/element until the whole array is traversed.
• If any of the picked elements is greater than its future elements, Then simply we will return False.
• If the size of the array is Zero or One i.e ( N = 0 or N = 1 ) or the entire array is traversed successfully then we will simply return True.

class Solution {
    // Function to check if the array is sorted
    public boolean isSorted(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // If any element is smaller than the previous one, return false
                if (arr[j] < arr[i]) 
                    return false;
            }
        }
        return true; // Return true if no unsorted elements are found
    }
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int n = 5;
        Solution obj = new Solution();
        
        boolean ans = obj.isSorted(arr, n);
        
        // Output result
        if (ans) 
            System.out.println("True");
        else 
            System.out.println("False");
    }
}

Complexity Analysis

Time Complexity: O(N2), as it uses two nested loops to compare every pair of elements in the array.

Space Complexity: O(1), as no extra space is used apart from a few variables.

2. Optimal Approach