Jobs

Interviews

Discussions

Rotate Array

Medium

Google

1 view

Topics:

ArraysTwo Pointers

You are given an integer array nums. Your task is to rotate the array to the right by k steps, where k is a non-negative integer. The rotation should be performed in-place if possible.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Rotate 1 step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
Rotate 1 step to the right: [99,-1,-100,3]
Rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

Could you provide an efficient solution for this problem, and what is the time and space complexity of your approach? Bonus points if you can do it in-place (O(1) extra space).

Rotate Array

Medium

Google

1 view

Topics:

ArraysTwo Pointers

You are given an integer array nums. Your task is to rotate the array to the right by k steps, where k is a non-negative integer. The rotation should be performed in-place if possible.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Rotate 1 step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
Rotate 1 step to the right: [99,-1,-100,3]
Rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

Could you provide an efficient solution for this problem, and what is the time and space complexity of your approach? Bonus points if you can do it in-place (O(1) extra space).

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 for the integers in the `nums` array?
What is the maximum possible value for `k` relative to the length of the `nums` array? Could `k` be larger than the array length?
Is the input array guaranteed to be non-null and non-empty? If the array is empty, what should happen?
Does the array contain only integers, or are other data types (e.g., floats) possible?
Since I'm modifying the array in-place, should I expect the original `nums` array to remain unchanged after the rotation, or is it acceptable for the original array to be overwritten?

Brute Force Solution

Approach

The brute force method to rotate a list of items is like physically moving each item one by one. We essentially move the last item to the front a specified number of times, handling each move individually.

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

Take the last item in the list.
Remove it from the end of the list.
Place the item at the beginning of the list.
Repeat the previous three steps a certain number of times, as specified.

Code Implementation

def rotate_array_brute_force(numbers, rotation_amount):

    list_length = len(numbers)
    # We take the modulo to avoid unnecessary rotations.
    rotation_amount = rotation_amount % list_length

    for _ in range(rotation_amount):
        # Move the last element to the front.
        last_element = numbers[-1]

        # Remove the last element.
        numbers.pop()

        # Insert the last element at the beginning.
        numbers.insert(0, last_element)

    return numbers

Big(O) Analysis

Time Complexity

O(n*k) – The provided approach rotates the array 'k' times. In each rotation, the last element is moved to the beginning. Moving the last element requires removing it from the end, which takes O(1) time if it's an array or potentially O(n) if the underlying data structure is a linked list, though the problem does not specify that case. Inserting the element at the beginning takes O(n) time because all other elements need to be shifted to the right to make space. Since this O(n) operation occurs 'k' times, the overall time complexity is O(n*k).

Space Complexity

O(1) – The brute force method described involves repeatedly moving the last element of the array to the front. This operation is performed in-place, meaning no additional data structures that scale with the input size are created. Only a temporary variable may be needed to hold the value being moved. Therefore, the auxiliary space complexity is constant, or O(1).

Optimal Solution

Approach

Instead of shifting elements one by one, the optimal strategy involves reversing sections of the data to achieve the rotation in a clever way. Think of it like rearranging three parts of a block to get the final result more efficiently. This avoids repeatedly moving single elements.

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

First, reverse the entire block of data.
Next, reverse the first portion of the data, up to the rotation point.
Finally, reverse the remaining portion of the data, from the rotation point to the end.
By reversing these three sections in order, you end up with the rotated block without needing to move each individual item multiple times.

Code Implementation

def rotate_array(nums, rotation_steps):
    array_length = len(nums)
    rotation_steps %= array_length

    def reverse_array_section(start_index, end_index):
        while start_index < end_index:
            nums[start_index], nums[end_index] = nums[end_index], nums[start_index]
            start_index += 1
            end_index -= 1

    # Reverse the entire array to prepare for rotation.
    reverse_array_section(0, array_length - 1)

    # Reverse the first part of array, up to the rotation point.
    reverse_array_section(0, rotation_steps - 1)

    # Reverse the remaining array to complete the rotation.
    reverse_array_section(rotation_steps, array_length - 1)

Big(O) Analysis

Time Complexity

O(n) – The algorithm consists of three reverse operations performed on different sections of the input array. Each reverse operation iterates through its respective section, swapping elements from the start and end until the middle is reached. The first reverse operates on the entire array of size n, the second on a section of size k (rotation point), and the third on a section of size n-k. Each of these operations has a time complexity of O(n), O(k) and O(n-k) respectively. Since k < n, these operations sum up to a multiple of n which means the overall time complexity remains O(n).

Space Complexity

O(1) – The algorithm described performs in-place reversals of array sections. It doesn't use any auxiliary data structures like temporary arrays, lists, or hash maps to store elements. The reversing operations are accomplished by swapping elements within the existing array. Therefore, the space used remains constant irrespective of the input array size N.

Edge Cases

Case	How to Handle
Empty or null input array	Return immediately or throw an exception if modification is not allowed based on problem constraints.
k is zero	No rotation needed, return the original array.
k is equal to the array length	No rotation needed, return the original array as k % length will be 0.
k is greater than the array length	Apply modulo operation (k % nums.length) to get the effective rotation count within the array bounds.
Array contains only one element	No rotation is performed, return the original array.
Array with negative numbers	The standard rotation algorithms work correctly with negative numbers.
Large array size and large k value	Use a time and space efficient algorithm (e.g., reversal algorithm) to avoid exceeding time or memory limits.
Integer overflow with large k and array length if intermediate calculations are performed naively	Ensure intermediate calculations such as index manipulations use appropriate data types to avoid overflow, or use modulo arithmetic correctly.

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 for the integers in the `nums` array?
What is the maximum possible value for `k` relative to the length of the `nums` array? Could `k` be larger than the array length?
Is the input array guaranteed to be non-null and non-empty? If the array is empty, what should happen?
Does the array contain only integers, or are other data types (e.g., floats) possible?
Since I'm modifying the array in-place, should I expect the original `nums` array to remain unchanged after the rotation, or is it acceptable for the original array to be overwritten?

Brute Force Solution

Approach

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

Take the last item in the list.
Remove it from the end of the list.
Place the item at the beginning of the list.
Repeat the previous three steps a certain number of times, as specified.

Code Implementation

def rotate_array_brute_force(numbers, rotation_amount):

    list_length = len(numbers)
    # We take the modulo to avoid unnecessary rotations.
    rotation_amount = rotation_amount % list_length

    for _ in range(rotation_amount):
        # Move the last element to the front.
        last_element = numbers[-1]

        # Remove the last element.
        numbers.pop()

        # Insert the last element at the beginning.
        numbers.insert(0, last_element)

    return numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, reverse the entire block of data.
Next, reverse the first portion of the data, up to the rotation point.
Finally, reverse the remaining portion of the data, from the rotation point to the end.
By reversing these three sections in order, you end up with the rotated block without needing to move each individual item multiple times.

Code Implementation

def rotate_array(nums, rotation_steps):
    array_length = len(nums)
    rotation_steps %= array_length

    def reverse_array_section(start_index, end_index):
        while start_index < end_index:
            nums[start_index], nums[end_index] = nums[end_index], nums[start_index]
            start_index += 1
            end_index -= 1

    # Reverse the entire array to prepare for rotation.
    reverse_array_section(0, array_length - 1)

    # Reverse the first part of array, up to the rotation point.
    reverse_array_section(0, rotation_steps - 1)

    # Reverse the remaining array to complete the rotation.
    reverse_array_section(rotation_steps, array_length - 1)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return immediately or throw an exception if modification is not allowed based on problem constraints.
k is zero	No rotation needed, return the original array.
k is equal to the array length	No rotation needed, return the original array as k % length will be 0.
k is greater than the array length	Apply modulo operation (k % nums.length) to get the effective rotation count within the array bounds.
Array contains only one element	No rotation is performed, return the original array.
Array with negative numbers	The standard rotation algorithms work correctly with negative numbers.
Large array size and large k value	Use a time and space efficient algorithm (e.g., reversal algorithm) to avoid exceeding time or memory limits.
Integer overflow with large k and array length if intermediate calculations are performed naively	Ensure intermediate calculations such as index manipulations use appropriate data types to avoid overflow, or use modulo arithmetic correctly.