Check if the array is sorted

Intuition:

The simplest method to verify if an array is sorted involves comparing each element with its subsequent neighbor. If any element is found to be greater than the one that follows it, the array is determined to be unsorted.

Approach:

Start by focusing on the element at the first index. Compare this element with every subsequent element in the array.
If this element is greater than any of the following elements, the array is not sorted.
If the element is smaller than or equal to all subsequent elements, proceed to the next element.
Continue this process for every element in the array. If all the elements are in proper order, the array can be said sorted.

Edge Cases:

If the array has zero or one element (N = 0 or N = 1), it's sorted. Return True.

Dry Run:

Solution:

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

class Solution {
public:
    bool arraySortedOrNot(int arr[], int n) {
        // Iterate through each element
        for (int i = 0; i < n - 1; ++i) {
            
            // Compare with every subsequent element
            for (int j = i+1; j < n; ++j) {
                
                // If any element is out of order, return false
                if (arr[i] > arr[j]) {
                    return false;
                }
            }
        }
        // All elements are in order
        return true;
    }
};

// Driver code
int main() {
    // Creating an instance of solution class
    Solution solution;
    
    int n = 5;
    int arr[] = {1, 2, 3, 4, 5};
    
    // Function call to check if the array is sorted 
    bool sorted = solution.arraySortedOrNot(arr, n);
    if (sorted) {
        cout << "Array is sorted." << endl;
    } else {
        cout << "Array is not sorted." << endl;
    }
    return 0;
}
class Solution {
    public boolean arraySortedOrNot(int[] arr, int n) {
        // Iterate through each element
        for (int i = 0; i < arr.length - 1; i++) {
            
            // Compare with every subsequent element
            for (int j = i + 1; j < arr.length; j++) {
                
                // If any element is out of order, return false
                if (arr[i] > arr[j]) {
                    return false;
                }
            }
        }
        return true; // All elements are in order
    }
    
    // Main method 
    public static void main(String[] args) {
        // Creating an instance of solution class
        Solution solution = new Solution();
        
        int[] arr = {1, 2, 3, 4, 5};
        int n = arr.length;
        
        // Function call to check if the array is sorted
        boolean sorted = solution.arraySortedOrNot(arr, n);
        
        if (sorted) {
            System.out.println("Array is sorted.");
        } else {
            System.out.println("Array is not sorted.");
        }
    }
}
class Solution:
    def arraySortedOrNot(self, arr, n):
        # Iterate through each element
        for i in range(n - 1):
            # Compare with every subsequent element
            for j in range(i + 1, n):
                # If any element is out of order, return False
                if arr[i] > arr[j]:
                    return False
        # All elements are in order
        return True

# Driver code

# Creating an instance of solution class
solution = Solution()
arr = [1, 2, 3, 4, 5]
n = len(arr)

# Function call to check if the array is sorted
sorted = solution.arraySortedOrNot(arr, n)
if sorted:
    print("Array is sorted.")
else:
    print("Array is not sorted.")
class Solution {
    arraySortedOrNot(arr, n) {
        // Iterate through each element
        for (let i = 0; i < n - 1; i++) {
            // Compare with every subsequent element
            for (let j = i + 1; j < n; j++) {
                // If any element is out of order, return false
                if (arr[i] > arr[j]) {
                    return false;
                }
            }
        }
        // All elements are in order
        return true;
    }
}

// Driver code
// Creating an instance of solution class
let solution = new Solution();
let arr = [1, 2, 3, 4, 5];
let n = arr.length;

// Function call to check if the array is sorted 
let sorted = solution.arraySortedOrNot(arr, n);
if (sorted) {
    console.log("Array is sorted.");
} else {
    console.log("Array is not sorted.");
}

Complexity Analysis:

Time Complexity: O(N²)
Compare each element with all the elements that come after it. This involves a nested loop: the outer loop runs N times (traversing every single element of the array with N elements) and the inner the loop runs up to N-1 times.

Space Complexity: O(1)
A constant amount of extra space is used because no additional data structures is needed.

Intuition:

A more efficient approach to verify if an array is sorted leverages a single pass through the array. By comparing each element directly with the next one, it's possible to immediately detect any deviation from the desired order. This method minimizes unnecessary comparisons and quickly identifies whether the array is sorted, as encountering just one instance where an element is greater than the next confirms that the array is not sorted. This approach is both time-efficient and straightforward.

Approach:

Start from the first element. Compare each element with the next element in the array.
If at any point the current element is greater than the next element, return False (the array is not sorted).
If all comparisons are valid (the current element is less than or equal to the next element), continue to the next pair. If the end of the array is reached without finding any out-of-order elements, return True.

Dry Run

Solution

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

class Solution {
public:
    // Function to check if an array is sorted
    bool arraySortedOrNot(int arr[], int n) {
        // Iterate through the array
        for (int i = 0; i < n - 1; i++) {
            
            // Compare each element with the next one
            if (arr[i] > arr[i + 1]) {
                /* If any element is greater than the next one, 
                the array is not sorted */
                return false;
            }
        }
        
        // If no such pair is found, array is sorted
        return true; 
    }
};

// Driver code
int main() {
    // Creating an instance of solution class
    Solution solution;
    
    int n = 5;
    int arr[] = {1, 2, 3, 4, 5};
    
    // Function call to check if the array is sorted 
    bool sorted = solution.arraySortedOrNot(arr, n);
    if (sorted) {
        cout << "Array is sorted." << endl;
    } else {
        cout << "Array is not sorted." << endl;
    }
    return 0;
}
class Solution {
    // Function to check if an array is sorted
    public boolean arraySortedOrNot(int[] arr, int n) {
        // Iterate through the array
        for (int i = 0; i < n - 1; i++) {
            
            // Compare each element with the next one
            if (arr[i] > arr[i + 1]) {
                
                /* If any element is greater than the next 
                one, the array is not sorted */
                return false; 
            }
        }
        return true; // If no such pair is found, array is sorted
    }
    
    // Main method 
    public static void main(String[] args) {
        // Creating an instance of solution class
        Solution solution = new Solution();
        
        int[] arr = {1, 2, 3, 4, 5};
        int n = arr.length;
        
        // Function call to check if the array is sorted
        boolean sorted = solution.arraySortedOrNot(arr, n);
        
        if (sorted) {
            System.out.println("Array is sorted.");
        } else {
            System.out.println("Array is not sorted.");
        }
    }
}
class Solution:
    # Function to check if an array is sorted
    def arraySortedOrNot(self, arr, n):
        # Iterate through the array
        for i in range(n - 1):
            
            # Compare each element with the next one
            if arr[i] > arr[i + 1]:
                
            # If any element is greater than the next one,
            # the array is not sorted  
                return False  
                
        # If no such pair is found, array is sorted
        return True  

# Driver code

# Creating an instance of solution class
solution = Solution()
arr = [1, 2, 3, 4, 5]
n = len(arr)

# Function call to check if the array is sorted
sorted = solution.arraySortedOrNot(arr, n)
if sorted:
    print("Array is sorted.")
else:
    print("Array is not sorted.")
class Solution {
    // Function to check if an array is sorted
    arraySortedOrNot(arr, n) {
        // Iterate through the array
        for (let i = 0; i < n - 1; i++) {
            
            // Compare each element with the next one
            if (arr[i] > arr[i + 1]) {
            /* If any element is greater than the next one, 
            the array is not sorted */
                return false; 
            }
        }
        
        // If no such pair is found, array is sorted
        return true; 
    }
}

// Driver code
// Creating an instance of solution class
let solution = new Solution();
let arr = [1, 2, 3, 4, 5];
let n = arr.length;

// Function call to check if the array is sorted 
let sorted = solution.arraySortedOrNot(arr, n);
if (sorted) {
    console.log("Array is sorted.");
} else {
    console.log("Array is not sorted.");
}

Complexity Analysis:

Time Complexity: O(N)
Perform a single traversal through the array, making a constant-time comparison for each element.

Space Complexity: O(1)
A constant amount of extra space for variables is used, independent of the input size.

Problem List

Examples:

Constraints

Company Tags

Editorial

Intuition:

Approach:

Edge Cases:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run

Solution

Complexity Analysis:

Notes

Code