Jobs

Interviews

Discussions

Check if Array Is Sorted and Rotated

Easy

Google

3 views

Topics:

Arrays

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 B[i] == A[(i+x) % A.length] for every valid index i.

For example:

[3,4,5,1,2] should return true
[2,1,3,4] should return false
[1,2,3] should return true

Here are some edge cases to consider:

What should your code do if the array is empty?
What should your code do if the array has one element?
What should your code do if the array is already sorted?
What should your code do if the array has duplicate elements?

Check if Array Is Sorted and Rotated

Easy

Google

3 views

Topics:

Arrays

Note: An array A rotated by x positions results in an array B of the same length such that B[i] == A[(i+x) % A.length] for every valid index i.

For example:

[3,4,5,1,2] should return true
[2,1,3,4] should return false
[1,2,3] should return true

Here are some edge cases to consider:

What should your code do if the array is empty?
What should your code do if the array has one element?
What should your code do if the array is already sorted?
What should your code do if the array has duplicate elements?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values in the `nums` array? Can I expect negative numbers, zeros, or only positive integers?
Can the input array be empty or contain only one element? If so, what should the output be in these cases?
Are duplicate numbers allowed in the array? How should I handle cases with duplicates?
By 'strictly increasing,' do you mean each element must be strictly greater than the previous element, or is non-decreasing (greater than or equal to) acceptable?
If multiple rotations result in a sorted array, should I return true, or is there a specific criteria for choosing which rotation to consider?

Brute Force Solution

Approach

The brute force method to check if an arrangement of numbers is sorted and rotated involves trying out all possible rotation points. We examine each rotation to see if it results in a sorted sequence. If we find a sorted sequence after rotating, then the original arrangement satisfies the condition.

Here's how the algorithm would work step-by-step:

First, consider the arrangement as is, without any rotation, and check if it's sorted.
Next, imagine rotating the arrangement by one position to the right. Now, see if this new arrangement is sorted.
Keep rotating the arrangement by one position at a time, checking for sorted order each time.
Continue this until you've tried every possible rotation of the original arrangement.
If, at any point, you find an arrangement that's sorted, you can conclude that the original arrangement was sorted and rotated.
If you go through all possible rotations and none are sorted, then the original arrangement was not sorted and rotated.

Code Implementation

def check_if_array_is_sorted_and_rotated_brute_force(array):
    array_length = len(array)

    # Iterate through all possible rotations.
    for rotation_index in range(array_length):
        rotated_array = array[rotation_index:] + array[:rotation_index]

        # Check if the rotated array is sorted.
        is_sorted = True
        for index in range(array_length - 1):
            if rotated_array[index] > rotated_array[index + 1]:
                is_sorted = False
                break

        # If a sorted rotation is found, return True.
        if is_sorted:
            return True

    # If no sorted rotation is found, return False. This covers the non-rotated case as well
    return False

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through all n possible rotations of the array. For each rotation, the inner loop checks if the rotated array is sorted. The inner loop iterates through the array once, performing n-1 comparisons to determine if it is sorted. Therefore, we have n rotations each requiring O(n) comparisons, resulting in a total time complexity of O(n*n), which simplifies to O(n²).

Space Complexity

O(1) – The brute force method described only uses a few variables for iteration and comparison during the rotations. No additional data structures like arrays or hash maps are created to store intermediate results. Therefore, the space required remains constant regardless of the input array's size, N. This means the auxiliary space complexity is O(1).

Optimal Solution

Approach

To determine if an array is sorted and rotated, we aim to find the potential 'break' in the sorted order efficiently. We identify where the sorted order is disrupted, and then verify that sorting is consistent before and after that break. This avoids checking all possible rotation points.

Here's how the algorithm would work step-by-step:

First, find where the smooth sorted order of the numbers is disrupted. Look for a spot where a number is bigger than the number that comes after it.
If there's no disruption at all, the array is already sorted and we're done!
If there's more than one disruption, it means it can't be a rotated sorted array.
Next, we check if the number before the disruption is smaller than or equal to the last number in the series, and if the first number in the series is smaller than or equal to the number after the disruption. If so, the array is sorted and rotated.

Code Implementation

def is_sorted_and_rotated(numbers) -> bool:
    disruption_count = 0
    array_length = len(numbers)

    # Find disruptions in the sorted order
    for i in range(array_length):
        if numbers[i] > numbers[(i + 1) % array_length]:
            disruption_count += 1

    # Already sorted condition
    if disruption_count == 0:
        return True

    # More than one disruption means not rotated
    if disruption_count > 1:
        return False

    # Check rotation conditions
    if numbers[array_length - 1] <= numbers[0]:

        # This is the potential rotated point we expect
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array of size n to find a single disruption in the sorted order. This involves comparing adjacent elements, and the loop breaks as soon as more than one disruption is found. After the loop completes, there are a few constant-time comparisons between the first and last elements of the array and the elements around the disruption point. The dominant factor is the single pass through the array, therefore the time complexity is O(n).

Space Complexity

O(1) – The algorithm utilizes a fixed number of integer variables, such as for loop counters and to track the number of disruptions. The number of these variables does not depend on the size of the input array, N. Therefore, the auxiliary space required by the algorithm remains constant irrespective of the input size. This constant space usage translates to a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty array	Return true since an empty array can be considered sorted and rotated.
Array with one element	Return true since a single element array is trivially sorted and rotated.
Array already sorted in strictly increasing order	The algorithm should correctly identify this as a valid rotated array (rotation count of 0).
Array sorted in descending order	The algorithm should return false as rotating a descending array won't result in a sorted one.
Array with all identical elements	Return true since even with identical elements, it can be considered sorted and rotated.
Array with duplicate values that are not strictly increasing after rotation	The logic must handle duplicate values correctly, ensuring that only a single 'break' point exists where the previous element is greater than the current one, disregarding duplicates.
Array with large integers that could cause integer overflow	The comparison should avoid potential integer overflow issues by using appropriate data types or checking for overflow during comparisons.
Array with a very large number of elements	Ensure that the algorithm's time complexity is optimal, ideally O(n), to avoid timeouts with large arrays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values in the `nums` array? Can I expect negative numbers, zeros, or only positive integers?
Can the input array be empty or contain only one element? If so, what should the output be in these cases?
Are duplicate numbers allowed in the array? How should I handle cases with duplicates?
By 'strictly increasing,' do you mean each element must be strictly greater than the previous element, or is non-decreasing (greater than or equal to) acceptable?
If multiple rotations result in a sorted array, should I return true, or is there a specific criteria for choosing which rotation to consider?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the arrangement as is, without any rotation, and check if it's sorted.
Next, imagine rotating the arrangement by one position to the right. Now, see if this new arrangement is sorted.
Keep rotating the arrangement by one position at a time, checking for sorted order each time.
Continue this until you've tried every possible rotation of the original arrangement.
If, at any point, you find an arrangement that's sorted, you can conclude that the original arrangement was sorted and rotated.
If you go through all possible rotations and none are sorted, then the original arrangement was not sorted and rotated.

Code Implementation

def check_if_array_is_sorted_and_rotated_brute_force(array):
    array_length = len(array)

    # Iterate through all possible rotations.
    for rotation_index in range(array_length):
        rotated_array = array[rotation_index:] + array[:rotation_index]

        # Check if the rotated array is sorted.
        is_sorted = True
        for index in range(array_length - 1):
            if rotated_array[index] > rotated_array[index + 1]:
                is_sorted = False
                break

        # If a sorted rotation is found, return True.
        if is_sorted:
            return True

    # If no sorted rotation is found, return False. This covers the non-rotated case as well
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find where the smooth sorted order of the numbers is disrupted. Look for a spot where a number is bigger than the number that comes after it.
If there's no disruption at all, the array is already sorted and we're done!
If there's more than one disruption, it means it can't be a rotated sorted array.
Next, we check if the number before the disruption is smaller than or equal to the last number in the series, and if the first number in the series is smaller than or equal to the number after the disruption. If so, the array is sorted and rotated.

Code Implementation

def is_sorted_and_rotated(numbers) -> bool:
    disruption_count = 0
    array_length = len(numbers)

    # Find disruptions in the sorted order
    for i in range(array_length):
        if numbers[i] > numbers[(i + 1) % array_length]:
            disruption_count += 1

    # Already sorted condition
    if disruption_count == 0:
        return True

    # More than one disruption means not rotated
    if disruption_count > 1:
        return False

    # Check rotation conditions
    if numbers[array_length - 1] <= numbers[0]:

        # This is the potential rotated point we expect
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty array	Return true since an empty array can be considered sorted and rotated.
Array with one element	Return true since a single element array is trivially sorted and rotated.
Array already sorted in strictly increasing order	The algorithm should correctly identify this as a valid rotated array (rotation count of 0).
Array sorted in descending order	The algorithm should return false as rotating a descending array won't result in a sorted one.
Array with all identical elements	Return true since even with identical elements, it can be considered sorted and rotated.
Array with duplicate values that are not strictly increasing after rotation	The logic must handle duplicate values correctly, ensuring that only a single 'break' point exists where the previous element is greater than the current one, disregarding duplicates.
Array with large integers that could cause integer overflow	The comparison should avoid potential integer overflow issues by using appropriate data types or checking for overflow during comparisons.
Array with a very large number of elements	Ensure that the algorithm's time complexity is optimal, ideally O(n), to avoid timeouts with large arrays.