algoadvance

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.

An array is said to be rotated if one could rotate some pivot index and get the original array in sorted order.

For example, array [3, 4, 5, 1, 2] is considered rotated at pivot index 2 because it becomes sorted array [1, 2, 3, 4, 5] after rotating left twice.

Clarifying Questions

  1. What is the range and type of elements in the nums array?
    • The elements in the array can be any integers, and the array’s length will be between 1 and 100.
  2. Will the array always have unique elements?
    • Yes, for the given problem, we assume all elements in the array are unique.
  3. Can the array be empty?
    • No, the constraints state the length will be at least 1.
  4. Are there any other conditions on the input array, like sorted or unsorted initially?
    • The array is unsorted initially but can be sorted and then rotated.

Strategy

  1. We need to determine if the array can be represented as a sorted array that has been rotated.
  2. We will count the number of “drops” in the array where the current element is greater than the next element.
  3. If there is more than one such drop, then it’s not possible to sort and rotate to get the input array.
  4. If there is exactly one drop, ensure the last element connects correctly to the first element to form a sorted array.
  5. If there’s zero drop, it means the array is sorted but not rotated, which still satisfies the condition.

Code

def check(nums):
    count_drops = 0
    n = len(nums)
    
    # Count the number of drops in the array
    for i in range(n):
        if nums[i] > nums[(i + 1) % n]:
            count_drops += 1
    
    # The array can be sorted and rotated if and only if there is at most one drop
    return count_drops <= 1

# Example usage
print(check([3, 4, 5, 1, 2]))  # Should return True
print(check([2, 1, 3, 4]))     # Should return False
print(check([1, 2, 3]))        # Should return True

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. We traverse the array once to count the drops, making the solution efficient.

Try our interview co-pilot at AlgoAdvance.com