Problem Statement
Given an integer array nums, return true if it is sorted in non-decreasing order. Otherwise, return false.
Example 1
Input: nums = [1, 2, 2, 4, 5]
Output: true
Explanation: Every element is greater than or equal to the previous element, so the array is sorted.
Example 2
Input: nums = [1, 3, 2, 4]
Output: false
Explanation: nums[2] = 2 is smaller than nums[1] = 3, so the sorted order breaks.
Brute Force Approach
In a sorted array, an earlier element cannot be greater than any element appearing after it.
Check every pair of indices where the first index is smaller than the second. If an earlier value is greater than a later value, the required order is violated.
Algorithm
Store the number of elements in
n, as it defines the range for comparing every possible pair of positions.Use
firstto move from index0ton - 2, since each element needs to be compared only with the elements appearing after it.For every
first, letsecondtraverse fromfirst + 1ton - 1. This covers every pair where the earlier index comes before the later one.Compare
nums[first]withnums[second]. If the earlier value is greater, returnfalsebecause this pair violates the required non-decreasing order.Return
trueafter all pairs have been checked without finding any violation.
Dry Run
Check if Array is Sorted Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: bool isSorted(const vector<int>& nums) { int n = nums.size(); // Compare each value with every element that comes after it. for (int first = 0; first < n - 1; first++) { for (int second = first + 1; second < n; second++) { // An earlier value cannot be greater in a sorted array. if (nums[first] > nums[second]) { return false; } } } return true; }};int main() { vector<int> nums = {1, 2, 2, 4}; Solution solution; bool answer = solution.isSorted(nums); cout << (answer ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: O(N²), where N represents the number of elements. In the worst case, every possible pair is compared.
Space Complexity: O(1), because no additional data structure is used.
Optimal Approach
Checking every possible pair is unnecessary.
A violation in non-decreasing order can be detected by comparing each element with the element immediately before it. If the current value is smaller, the array is not sorted.
Algorithm
Start traversing from index
1, since every current element can be checked against the element immediately before it.Compare
nums[index]withnums[index - 1]to verify that the current adjacent pair follows non-decreasing order.If
nums[index] < nums[index - 1], returnfalseimmediately because even one such adjacent pair is enough to prove that the array is not sorted.Continue checking the remaining adjacent pairs as long as their order stays valid.
Return
trueafter the traversal finishes, since reaching the end without finding a violation confirms that the complete array is sorted.
Dry Run
Check if Array is Sorted Optimal Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: bool isSorted(const vector<int>& nums) { // Each value only needs to be checked against its previous one. for (int index = 1; index < nums.size(); index++) { // A smaller current value breaks the non-decreasing order. if (nums[index] < nums[index - 1]) { return false; } } return true; }};int main() { vector<int> nums = {1, 2, 2, 4}; Solution solution; bool answer = solution.isSorted(nums); cout << (answer ? "true" : "false") << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements. Each adjacent pair is checked at most once.
Space Complexity: O(1), because no additional data structure is required.
Interview follow-up Questions
Yes. Adjacent elements may be equal. For example, [1, 2, 2, 4] is sorted in non-decreasing order.
Be the first to add a comment.