Check if the Array is Sorted II
EasyCompare each neighbour pair
Problem
Given an array nums of n integers, return true if the array nums is sorted in non-decreasing order or else false.
Check each neighbour pair — if none is out of order, it's sorted.
The idea
An array is non-decreasing exactly when every element is at most the one after it, so a single pass comparing adjacent pairs settles it. Return false the moment a pair is out of order — there is nothing later that can fix it.
The trick
- Only adjacent pairs matter; the ordering property is transitive.
- Arrays of length 0 or 1 are sorted by definition.
i
i-1
1
2
2
4
5
0
1
2
3
4
Step 1 of 5. 1 ≤ 2 ✓ Values: 1, 2, 2, 4, 5. Pointers: i at index 1, i-1 at index 0.
1/5
Optimal
timeO(n)spaceO(1)
1for i in 1..n-1:2 if nums[i] < nums[i-1]: return false3return trueInput
- array
- [1, 2, 2, 4, 5]
Memory
- i
- = 1 [2]
- i-1
- = 0 [1]
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 2, 3]
- Output:
- true
- Explanation:
- Every element is <= the next one.
Example 2
- Input:
- nums = [3, 1, 2]
- Output:
- false
- Explanation:
- 3 is bigger than the 1 after it.
Example 3
- Input:
- nums = [5]
- Output:
- true
- Explanation:
- A single element is always sorted.
Constraints
- 1 <= n <= 100
- 1 <= nums[i] <= 100
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.