703190. Check if array is sorted
Check if array is sorted
Slug: check-if-an-array-is-sorted0701
Difficulty: Easy
Id: 703190
Topic Tags: Arrays, Sorting, Data Structures, Algorithms
Company Tags: None
Summary
The problem involves checking whether a given array is sorted or not. This can be done in various ways such as comparing adjacent elements to check for any out-of-order pairs. The key concepts involved are arrays and sorting.
Detailed Explanation
To solve this problem, we need to iterate through the array and compare each element with its next one. If any pair of adjacent elements is found to be out of order (i.e., the second element is smaller than the first), then the array is not sorted. Otherwise, the array is considered sorted.
Here's a step-by-step breakdown of the solution:
- Initialize a variable
isSortedto true. - Iterate through the array starting from the second element (index 1).
- For each element, compare it with its previous one.
- If any pair is found to be out of order, set
isSortedto false and break the loop. - If the loop completes without finding any out-of-order pairs, then the array is sorted.
Time complexity: O(n), where n is the length of the array. This is because we are iterating through each element once.
Space complexity: O(1), since we are not using any extra space that scales with the input size.
Optimized Solutions
Java
public boolean isSorted(int[] arr) {
boolean isSorted = true;
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
isSorted = false;
break;
}
}
return isSorted;
}