Jobs

Interviews

Discussions

Rotate Array

Medium

Visa

0 views

Topics:

Arrays

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps 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 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Rotate Array

Medium

Visa

0 views

Topics:

Arrays

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps 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 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with 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:

Can the input array `nums` contain negative numbers or zeros?
What is the maximum possible length of the `nums` array, and what is the maximum possible value of `k`?
Is `k` guaranteed to be non-negative? If `k` is greater than the length of `nums`, should I take the modulo of `k` with the length of `nums`?
Should I assume that the input array `nums` is not null or empty?
Are there any memory constraints I should be aware of, given I am modifying the array in-place?

Brute Force Solution

Approach

The brute force method is like physically moving items in a line. We shift each item one by one, repeatedly, until they've moved the required amount. It's simple but not the fastest way.

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

Take the last item in the line.
Remove the last item and place it at the very beginning of the line.
Repeat this process of taking the last item and putting it first, a certain number of times, based on how much we want to rotate the line.
After repeating this process, the items in the line are rotated by the specified amount.

Code Implementation

def rotate_array_brute_force(numbers, rotation_amount):
    array_length = len(numbers)
    
    for _ in range(rotation_amount):
        # Store the last element before rotation.
        last_element = numbers[array_length - 1]

        # Shift elements to the right.
        for index in range(array_length - 1, 0, -1):
            numbers[index] = numbers[index - 1]

        # Place the last element at the beginning.
        numbers[0] = last_element

    return numbers

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*k) – The described algorithm rotates the array by moving the last element to the front k times. Each rotation requires shifting all n elements of the array. Because we perform k such rotations, the total time complexity is proportional to n multiplied by k, thus O(n*k).

Space Complexity

O(1) – The provided brute force approach repeatedly moves the last element of the array to the beginning. This process, as described, does not involve the creation of any additional data structures like temporary arrays or hash maps. It operates directly on the input array. Therefore, the auxiliary space required is constant, independent of the array size (N).

Optimal Solution

Approach

To rotate a collection of items efficiently, we want to avoid moving items one at a time multiple times. The best way to do this is to think about reversing parts of the collection.

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

First, reverse the entire collection of items.
Then, reverse the first portion of the collection, up to the rotation point.
Finally, reverse the remaining portion of the collection after the rotation point.
These three reversals, in order, will place the items in the desired rotated order.

Code Implementation

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

    def reverse_part_of_array(nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    # Reversing the entire array is the first step
    reverse_part_of_array(nums, 0, array_length - 1)

    # Reversing the first part of the array
    reverse_part_of_array(nums, 0, rotation_steps - 1)

    # Reversing the second part of the array
    reverse_part_of_array(nums, rotation_steps, array_length - 1)

    return nums

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves three reversals of portions of the input array. Each reversal iterates through a section of the array, swapping elements from the start and end until the middle is reached. The first reversal processes all n elements. The second reversal processes k elements (where k is related to the rotation amount). The third reversal processes the remaining n-k elements. Since each reversal operation is linear with respect to the size of the portion it reverses, and the sum of the sizes of the portions is n, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm operates by reversing sections of the input array in place. This involves swapping elements, which requires only a constant amount of extra space to hold temporary variables during the swap operation. No auxiliary data structures that scale with the input size N (where N is the number of elements in the array) are used. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty array	Check for null or empty input and return immediately to avoid errors; nothing to rotate.
k is zero	If k is zero, no rotation is needed, so return the array as is.
k is larger than array length	Use the modulo operator (k % nums.length) to normalize k to be within the array's bounds.
Array with one element	If the array has only one element, no rotation changes anything; return as is.
Array with two elements and k=1	A single rotation will simply swap the two elements; ensure code handles this basic case.
Array with all identical values	The rotation should still work correctly regardless of the input value.
Large array size and large k value	Ensure the algorithm is efficient in both space and time to avoid exceeding memory limits or causing excessive runtime.
Negative k value	Handle negative k values appropriately; this typically requires adjusting the k value to represent a left rotation.

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:

Can the input array `nums` contain negative numbers or zeros?
What is the maximum possible length of the `nums` array, and what is the maximum possible value of `k`?
Is `k` guaranteed to be non-negative? If `k` is greater than the length of `nums`, should I take the modulo of `k` with the length of `nums`?
Should I assume that the input array `nums` is not null or empty?
Are there any memory constraints I should be aware of, given I am modifying the array in-place?

Brute Force Solution

Approach

The brute force method is like physically moving items in a line. We shift each item one by one, repeatedly, until they've moved the required amount. It's simple but not the fastest way.

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

Take the last item in the line.
Remove the last item and place it at the very beginning of the line.
Repeat this process of taking the last item and putting it first, a certain number of times, based on how much we want to rotate the line.
After repeating this process, the items in the line are rotated by the specified amount.

Code Implementation

def rotate_array_brute_force(numbers, rotation_amount):
    array_length = len(numbers)
    
    for _ in range(rotation_amount):
        # Store the last element before rotation.
        last_element = numbers[array_length - 1]

        # Shift elements to the right.
        for index in range(array_length - 1, 0, -1):
            numbers[index] = numbers[index - 1]

        # Place the last element at the beginning.
        numbers[0] = last_element

    return numbers

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To rotate a collection of items efficiently, we want to avoid moving items one at a time multiple times. The best way to do this is to think about reversing parts of the collection.

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

First, reverse the entire collection of items.
Then, reverse the first portion of the collection, up to the rotation point.
Finally, reverse the remaining portion of the collection after the rotation point.
These three reversals, in order, will place the items in the desired rotated order.

Code Implementation

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

    def reverse_part_of_array(nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    # Reversing the entire array is the first step
    reverse_part_of_array(nums, 0, array_length - 1)

    # Reversing the first part of the array
    reverse_part_of_array(nums, 0, rotation_steps - 1)

    # Reversing the second part of the array
    reverse_part_of_array(nums, rotation_steps, array_length - 1)

    return nums

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty array	Check for null or empty input and return immediately to avoid errors; nothing to rotate.
k is zero	If k is zero, no rotation is needed, so return the array as is.
k is larger than array length	Use the modulo operator (k % nums.length) to normalize k to be within the array's bounds.
Array with one element	If the array has only one element, no rotation changes anything; return as is.
Array with two elements and k=1	A single rotation will simply swap the two elements; ensure code handles this basic case.
Array with all identical values	The rotation should still work correctly regardless of the input value.
Large array size and large k value	Ensure the algorithm is efficient in both space and time to avoid exceeding memory limits or causing excessive runtime.
Negative k value	Handle negative k values appropriately; this typically requires adjusting the k value to represent a left rotation.