algoadvance

Leetcode 1752. Check if Array Is Sorted and Rotated

Problem Statement

You are given an array of distinct integers nums. You want to return true if the array is sorted in non-decreasing order and then rotated some number of positions (including zero). Otherwise, return false.

An array A is said to be sorted and rotated if there exists some positive integer k such that:

• After rotating A k positions, the array becomes sorted in non-decreasing order.

Clarifying Questions

1. What is the range of the array length?
   • The length of the array will be between 1 and 100, inclusive.
2. Can the array be empty?
   • No, the array will have at least one element.
3. What is the range of the array elements?
   • The elements in the array are distinct integers.
4. Is the rotation allowed to be zero, meaning the complete array can be non-rotated but just sorted?
   • Yes, an array which is simply sorted without rotation is considered sorted and rotated for k = 0.

Strategy

1. Identify the Sorted Part:
   • Traverse the array and count the number of places where the next element is smaller than the current element. This will help us identify if the array is rotated.
2. Check Valid Rotation:
   • If the count of elements where the next element is smaller than the current element is more than 1, it can’t be a valid rotation. If the count is exactly one, check if the remaining part of the array still respects the non-decreasing order.

Code

public class Solution {
    public boolean check(int[] nums) {
        int count = 0;
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            if (nums[i] > nums[(i + 1) % len]) {
                count++;
            }
            if (count > 1) {
                return false;
            }
        }
        
        return true;
    }
}

Explanation

1. Loop through the Array:
   • Traverse the array to find the number of places where the next element is smaller than the current element. Use modulo operation to consider the array as circular.
2. Count Check:
   • If the count is greater than 1, return false since it cannot be a valid rotated sorted array.
   • If the count is 0 or 1, return true indicating that the array is sorted and rotated.

Time Complexity

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

This solution should effectively determine if the given array is sorted and rotated as per the problem statement.

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?