Problem Statement
Given an array nums
, return true
if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false
.
There may be duplicates in the original array.
Note: An array A
rotated by x
positions results in an array B
of the same length such that A[i] == B[(i+x) % A.length]
, where %
is the modulo operation.
Example 1:
Input: nums = [3,4,5,1,2] Output: true Explanation: [1,2,3,4,5] is the original sorted array. You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].
Example 2:
Input: nums = [2,1,3,4] Output: false Explanation: There is no sorted array once rotated that can make nums.
Example 3:
Input: nums = [1,2,3] Output: true Explanation: [1,2,3] is the original sorted array. You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.
Example 4:
Input: nums = [1,1,1] Output: true Explanation: [1,1,1] is the original sorted array. You can rotate any number of positions to make nums.
Example 5:
Input: nums = [2,1] Output: true Explanation: [1,2] is the original sorted array. You can rotate the array by x = 5 positions to begin on the element of value 2: [2,1].
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
Video Tutorial
You can find the detailed video tutorial hereThought Process
Simple problem, just need to find a pattern
- If always non-decreasing, true
- If it has one decreasing pivot, the last element needs to be less or equal than the first element
- If it has more than one decreasing pivot, false
Solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public boolean check(int[] nums) { | |
if (nums == null || nums.length == 0) { | |
return false; | |
} | |
if (nums.length == 1 || nums.length == 2) { | |
return true; | |
} | |
int decreasingCount = 0; | |
for (int i = 1; i < nums.length; i++) { | |
if (nums[i] < nums[i - 1]) { | |
if (decreasingCount != 0) { | |
return false; | |
} | |
decreasingCount++; | |
} | |
} | |
return decreasingCount == 0 ? true : nums[nums.length - 1] <= nums[0]; | |
} |
Space Complexity: O(1) no extra space is used
References
- None
No comments:
Post a Comment
Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!