Leetcode – Check if Array Is Sorted and Rotated Solution

Spread the love

Leetcode is a widely-used platform for practicing coding problems and preparing for technical interviews. It provides a wide array of problems from various domains like arrays, strings, linked lists, and more. The problem “Check if Array Is Sorted and Rotated” is a fascinating array problem that tests one’s ability to think logically and to optimize. This article will break down the problem, walk through different approaches to solve it, and compare their performances.

Problem Statement

The goal of the “Check if Array Is Sorted and Rotated” problem is to determine if a given array of unique integers is sorted in ascending order and then possibly rotated.

Input:

  • An array of unique integers, nums (1 ≤ ∣nums∣ ≤ 100), where 1 ≤ nums[i] ≤100.

Output:

  • Return True if the array is sorted and rotated, otherwise return False.

Example:

Input: nums = [3, 4, 5, 1, 2]

Output: True

Input: nums = [2, 1, 3, 4]

Output: False

Brute-Force Approach

A brute-force solution involves generating all possible rotations of the array and checking if any of them are sorted.

Here’s a Python implementation for the same:

def check(nums):
    n = len(nums)
    for i in range(n):
        rotated = nums[i:] + nums[:i]
        if sorted(rotated) == rotated:
            return True
    return False

Time and Space Complexity Analysis

The time complexity for this solution is O(n^2 log⁡n) due to the sorting involved for each rotation, and the space complexity is O(n) due to storage for the rotated array. This approach is inefficient for larger arrays.

Optimized Approach

A more optimized approach involves finding the position where the rotation happened (if at all) and then checking whether the array is sorted apart from this rotation.

Here’s how to implement it in Python:

def check(nums):
    n = len(nums)
    rotation_point = 0

    for i in range(1, n):
        if nums[i] < nums[i - 1]:
            if rotation_point:
                return False
            rotation_point = i

    return not rotation_point or nums[0] >= nums[-1]

Time and Space Complexity Analysis

The time complexity for this solution is O(n), where n is the size of the array. The space complexity is O(1), as we are using only constant extra space.

Testing the Solution

You should always test your code against various test cases to make sure it’s working as expected:

assert check([3, 4, 5, 1, 2]) == True
assert check([2, 1, 3, 4]) == False
assert check([1, 2, 3, 4, 5]) == True
assert check([1]) == True

Conclusion

The “Check if Array Is Sorted and Rotated” problem is a good exercise in array manipulation and logical reasoning. Initially, it may seem straightforward, but upon deeper inspection, the problem tests your understanding of array properties and your ability to write optimized code.

Leave a Reply