algoadvance

Leetcode 1752. Check if Array Is Sorted and Rotated

Problem Statement

You are given an array nums of n distinct integers. A permutation of the array is called a sorted and rotated if it is possible to rotate the array in such a way that it becomes non-decreasing.

Return true if the array is sorted and rotated, otherwise return false.

Example:

• Example 1:
  • Input: nums = [3, 4, 5, 1, 2]
  • Output: true
  • Explanation: [1, 2, 3, 4, 5] is sorted and rotated by 3 positions to get [3, 4, 5, 1, 2].
• Example 2:
  • Input: nums = [2, 1, 3, 4]
  • Output: false
  • Explanation: There is no way to rotate the array to get a non-decreasing array.
• Example 3:
  • Input: nums = [1, 2, 3]
  • Output: true
  • Explanation: [1, 2, 3] is already non-decreasing.

Clarifying Questions

1. Can the array be empty?
   • No, as per the problem definition, the array will always have at least one element.
2. What is the range of array length n?
   • Constraint not explicitly given in the problem, but usually, problems assume 1 <= n <= 10^4.

Strategy

To determine whether the array is sorted and rotated:

1. Non-Decreasing Count: Traverse the array and count the number of times the order goes from increasing to decreasing.
2. Check Boundary: Ensure that if more than one such transition occurs, return false.
3. Rotation Point: If there is exactly one transition, check the boundary condition to confirm it’s going from the largest to smallest value.

Code

#include <vector>
using namespace std;

bool check(vector<int>& nums) {
    int count = 0; // To count the number of rotations
    int n = nums.size();
    
    for (int i = 0; i < n; ++i) {
        // Check if there is a decrease in the order
        if (nums[i] > nums[(i + 1) % n]) {
            count++;
        }
    }
    
    // Array is sorted and rotated if there is at most one decrease in the order
    return count <= 1;
}

Explanation

1. Count Decreases: We loop through the array and check if nums[i] is greater than the next element nums[(i + 1) % n]. Using modulo ensures that we seamlessly check the boundary condition from the last element to the first.
2. Boundary Condition: We use modulo to handle the checking from the last element back to the first element.
3. If count is more than 1 at the end of the loop, it means there are multiple places where the sorted order is broken, thus the array is neither sorted nor properly rotated.

Time Complexity

• The time complexity is O(n), where n is the number of elements in the array, as we only need to traverse the array once.
• The space complexity is O(1) as we are only using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?