1752. Check if Array is Sorted and Rotated

#leetcode #dsa/arrays

Question

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.

Constraints:

Approach 1: Brute force

Algorithm

  1. Find the rotated number of positions x
  2. Create the original array without rotations
  3. Check if the original array is in ascending order

Code

class Solution {
public:
	bool check(vector<int>& nums) {
		// 1. Find the rotated number of positions x
		int x = 0;
		for (int i = 0 ; i < nums.size() - 1 ; i++) {
			if (nums[i+1] < nums[i]){
				x = i+1;
			}
		}

		// 2. Create the original array without rotations
		vector<int> originalNums(nums);
		for (int i = 0 ; i < nums.size() ; i++) {
			originalNums[i] = nums[(i+x) % nums.size()];
		}

		// 3. Check if the original Array is in ascending order
		for (int i = 0 ; i < nums.size() - 1 ; i++) { 
			if (nums[i+1] < nums[i]) { // only less than cuz duplicates
				return false;
			}
		}

		return true;
	}
}

Complexity Analysis

Approach 2: Optimal

Algorithm

  1. Count the number of pairs where the order is decreasing
  2. If this count is greater than 1, then the array could not have been increasing

Code

class Solution {
public:
	bool check(vector<int>& nums) {
		// 1. Count the number of pairs where the order is decreasing
		int count = 0;
		for (int i = 0 ; i < nums.size() - 1 ; i++) {
			if (nums[i+1] < nums[i]) count++;
		}
		
		// edge case: if the last element is greater than the first 
		if (nums[0] < nums[nums.size() - 1])
			count++;
		
		// 2. if the count is greater than 1, then the array could not have been increasing so return false
		return count > 1 ? false : true;
	}
};

Complexity Analysis