Problem Statement
Write a JavaScript function to check if a given array is sorted.
Example
Input: [1, 2, 3, 4, 5]
Output: true
Input: [1, 3, 2, 4, 5]
Output: false
Explanation: In the first example, the array is sorted in ascending order, so the function returns true. In the second example, the array is not sorted (3 is greater than 2), so the function returns false.
Approaches
Brute Force Approach
Idea
In this approach, we manually check if every adjacent pair of elements in the array is sorted in non-decreasing order.
Steps
- Loop through the array from the first element to the second-last element.
- For each element, compare it with the next element.
- If the current element is greater than the next element, return
false (array is not sorted).
- If the loop completes without returning
false, return true (array is sorted).
Time Complexity
- O(n), where n is the length of the array. We traverse the array once.
Space Complexity
- O(1), no extra space is used except for a few variables.
Example Code
Dry Run
For arr = [1, 2, 3, 4, 5]:
- Compare
1 and 2: 1 is not greater than 2.
- Compare
2 and 3: 2 is not greater than 3.
- Compare
3 and 4: 3 is not greater than 4.
- Compare
4 and 5: 4 is not greater than 5.
- The loop completes and returns
true (array is sorted).
For arr = [1, 3, 2, 4, 5]:
- Compare
1 and 3: 1 is not greater than 3.
- Compare
3 and 2: 3 is greater than 2, so return false (array is not sorted).
Efficient Approach Using the every() Method
Idea
The every() method tests whether all elements in the array pass the provided test function. We can check if every element is less than or equal to the next one.
Steps
- Use the
every() function to test if each element is smaller than or equal to its successor.
- If every comparison is true, the array is sorted.
Time Complexity
- O(n), as the
every() method internally iterates through the array once.
Space Complexity
- O(1), no extra space is used.
Example Code
Dry Run
For arr = [1, 2, 3, 4, 5]:
- The
every() function checks if every element is greater than or equal to the previous one.
- Since all elements satisfy this condition, it returns
true.
For arr = [1, 3, 2, 4, 5]:
- The
every() function finds that 2 is smaller than 3, so it returns false.
Example Test Case
Efficient Approach using Recursion
Idea
We can use recursion to simplify the comparison process by breaking the array down and comparing one element at a time.
Steps
- Create a recursive function that compares the first two elements of the array.
- If the first element is greater than the second, return
false.
- Otherwise, recursively check the rest of the array.
- Base case: If the array has only one or zero elements left, it is considered sorted.
Time Complexity
- O(n), where n is the length of the array. We check each element once.
Space Complexity
- O(n) due to the recursive stack.
Example Code
Dry Run
For arr = [1, 2, 3, 4, 5]:
- Compare
1 and 2: 1 is not greater than 2. Recursively check [2, 3, 4, 5].
- Compare
2 and 3: 2 is not greater than 3. Recursively check [3, 4, 5].
- Compare
3 and 4: 3 is not greater than 4. Recursively check [4, 5].
- Compare
4 and 5: 4 is not greater than 5. Recursively check [5].
- Base case reached, return
true.
For arr = [1, 3, 2, 4, 5]:
- Compare
1 and 3: 1 is not greater than 3. Recursively check [3, 2, 4, 5].
- Compare
3 and 2: 3 is greater than 2, so return false.
Example Test Case
Complexity Analysis
Brute Force Approach
- Time Complexity: O(n), since we iterate through the array.
- Space Complexity: O(1), as no extra space is used.
Efficient Recursive Approach
- Time Complexity: O(n), as we still check every element.
- Space Complexity: O(n), due to the recursive call stack.
Conclusion
We have explored three approaches to check if an array is sorted:
-
Brute Force Approach:
- Time Complexity: O(n)
- Space Complexity: O(1)
- Pros: Simple implementation, constant space usage
- Cons: Less intuitive for complex conditions
-
Efficient Approach (using every()):
- Time Complexity: O(n)
- Space Complexity: O(1)
- Pros: Concise code, efficient for single pass
- Cons: May be less readable for beginners
-
Recursive Approach:
- Time Complexity: O(n)
- Space Complexity: O(n) due to call stack
- Pros: Clean and intuitive implementation
- Cons: Higher space complexity for large arrays
All three approaches offer O(n) time complexity, but they differ in space usage and implementation style. The brute force and reduce() methods use constant space, making them more space-efficient. The recursive approach, while using more space due to the call stack, provides a clean and intuitive solution.
Choose the approach that best fits your specific requirements:
- For simplicity and minimal space usage, go with the brute force approach.
- For a balance of conciseness and efficiency, use the reduce() method.
- If you prefer a more intuitive and clean implementation and space is not a concern, the recursive approach is suitable.