Jobs

Interviews

Discussions

Shift 2D Grid

Easy

Asked by:

13 views

Topics:

Arrays

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Try coding it in LeetCode

Shift 2D Grid

Easy

Asked by:

13 views

Topics:

Arrays

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

Try coding it in LeetCode

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 are the dimensions of the grid, and what is the range of values within the grid?
Can 'k' (the shift value) be larger than the total number of elements in the grid? If so, what should I do?
Is the grid guaranteed to be rectangular (i.e., all rows have the same length)?
Should the shifting be done in-place, or should I return a new grid?
Is 'k' guaranteed to be non-negative?

Brute Force Solution

Approach

Imagine physically moving numbers in a grid to new spots like sliding tiles. The brute force way is to actually perform each movement one by one, step-by-step, until we've done all the shifts we need.

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

Take the very last number in the entire grid.
Move that number to the first available spot which is wrapping it to the next row and putting it in the first place or in the very first number if it is the last number in the first row.
Repeat this movement for the number that was originally in the second to last spot.
Keep doing this, moving each number one spot at a time, a total of 'k' times.
After doing all 'k' shifts, the grid will be in its final, shifted position.

Code Implementation

def shift_grid_brute_force(grid, shift_amount):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    for _ in range(shift_amount):
        # Store the last element of the grid
        last_element = grid[number_of_rows - 1][number_of_columns - 1]

        # Shift all elements one position to the right and down
        previous_element = last_element
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                current_element = grid[row_index][column_index]
                grid[row_index][column_index] = previous_element
                previous_element = current_element

        #The first element of grid is now the previous last element

    return grid

Big(O) Analysis

Time Complexity

O(k * m * n) – The provided solution simulates the shift operation k times. Each shift operation iterates through all m * n elements in the grid to move them one position at a time. Therefore, for each of the k shifts, we are performing m * n operations. This results in a total time complexity of O(k * m * n), where m is the number of rows and n is the number of columns in the grid.

Space Complexity

O(1) – The described brute force algorithm operates directly on the input grid and doesn't use any auxiliary data structures that scale with the size of the grid or the number of shifts. It only involves moving numbers around within the existing grid. Therefore, the space complexity is constant, regardless of the grid's dimensions (m x n) or the number of shifts (k). We are not creating any extra copies of the array or any extra data structures to hold intermediate results.

Optimal Solution

Approach

The key to efficiently shifting the grid is to treat it as one long continuous sequence of numbers, reshape it, and then reshape it again. This avoids moving elements one by one, which would take much longer.

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

Imagine the grid unwrapped into a single, long line of numbers.
Shift all the numbers in this imaginary line by the specified amount, wrapping around the ends if necessary.
Now, take this shifted line of numbers and wrap it back into the original grid shape.
The numbers are now in their final, shifted positions within the grid.

Code Implementation

def shift_grid(grid, shift_amount):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    # Flatten the 2D grid into a 1D list
    flattened_grid = [element for row in grid for element in row]

    total_elements = number_of_rows * number_of_columns
    effective_shift = shift_amount % total_elements

    # Shift the elements in the flattened grid
    shifted_flattened_grid = flattened_grid[-effective_shift:] + flattened_grid[:-effective_shift]

    # Reshape the shifted 1D list back into a 2D grid
    shifted_grid = []
    for row_index in range(number_of_rows):
        # Reconstruct each row by taking slices of the flattened array.
        shifted_grid.append(shifted_flattened_grid[row_index * number_of_columns:(row_index + 1) * number_of_columns])

    return shifted_grid

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm treats the m x n grid as a single sequence. Shifting the elements conceptually involves iterating through all m * n elements once to perform the shift operation (either directly calculating the new index or using modular arithmetic). Reshaping the array, both unwrapping and wrapping back to the grid format, involves iterating through all m * n elements once each. Therefore, the dominant factor is iterating through all the elements in the grid a constant number of times.

Space Complexity

O(M * N) – The solution conceptually unwraps the grid into a single long sequence, shifts it, and then wraps it back. Although the explanation doesn't explicitly state the creation of a new data structure, to perform the shift and re-wrap efficiently in many implementations, we might need to create a temporary array or list to hold the flattened and shifted sequence. This array would have a size equal to the total number of elements in the grid, which is M * N, where M is the number of rows and N is the number of columns. Therefore, the auxiliary space complexity is O(M * N).

Edge Cases

Case	How to Handle
Null or empty grid	Return the original grid if it's null or empty to avoid NullPointerException or index out of bounds.
Zero shifts (k = 0)	If k is 0, return the original grid without performing any shifts.
Large shift value (k larger than grid size)	Use the modulo operator (k % (m * n)) to reduce k to an effective shift within the grid size.
1x1 grid (single element)	A 1x1 grid shifting will always return the same grid, handle it correctly.
Rectangular grid (m != n)	Ensure the shifting logic correctly handles rectangular grids where the number of rows and columns are different.
Grid with very large dimensions (memory considerations)	Consider in-place shifting if memory constraints are a concern, trading space for time complexity.
Negative shift value (k < 0)	Handle negative shift values by converting them to positive equivalent (k = k % (m * n) + (m*n) if k < 0) to shift correctly.
Integer overflow in k calculation	Use long data type for k when calculating the effective shift to prevent integer overflow if grid dimensions are large.

Null or empty grid

How to Handle:

Return the original grid if it's null or empty to avoid NullPointerException or index out of bounds.

Zero shifts (k = 0)

How to Handle:

If k is 0, return the original grid without performing any shifts.

Large shift value (k larger than grid size)

How to Handle:

Use the modulo operator (k % (m * n)) to reduce k to an effective shift within the grid size.

1x1 grid (single element)

How to Handle:

A 1x1 grid shifting will always return the same grid, handle it correctly.

Rectangular grid (m != n)

How to Handle:

Ensure the shifting logic correctly handles rectangular grids where the number of rows and columns are different.

Grid with very large dimensions (memory considerations)

How to Handle:

Consider in-place shifting if memory constraints are a concern, trading space for time complexity.

Negative shift value (k < 0)

How to Handle:

Handle negative shift values by converting them to positive equivalent (k = k % (m * n) + (m*n) if k < 0) to shift correctly.

Integer overflow in k calculation

How to Handle:

Use long data type for k when calculating the effective shift to prevent integer overflow if grid dimensions are large.

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 are the dimensions of the grid, and what is the range of values within the grid?
Can 'k' (the shift value) be larger than the total number of elements in the grid? If so, what should I do?
Is the grid guaranteed to be rectangular (i.e., all rows have the same length)?
Should the shifting be done in-place, or should I return a new grid?
Is 'k' guaranteed to be non-negative?

Brute Force Solution

Approach

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

Take the very last number in the entire grid.
Move that number to the first available spot which is wrapping it to the next row and putting it in the first place or in the very first number if it is the last number in the first row.
Repeat this movement for the number that was originally in the second to last spot.
Keep doing this, moving each number one spot at a time, a total of 'k' times.
After doing all 'k' shifts, the grid will be in its final, shifted position.

Code Implementation

def shift_grid_brute_force(grid, shift_amount):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    for _ in range(shift_amount):
        # Store the last element of the grid
        last_element = grid[number_of_rows - 1][number_of_columns - 1]

        # Shift all elements one position to the right and down
        previous_element = last_element
        for row_index in range(number_of_rows):
            for column_index in range(number_of_columns):
                current_element = grid[row_index][column_index]
                grid[row_index][column_index] = previous_element
                previous_element = current_element

        #The first element of grid is now the previous last element

    return grid

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the grid unwrapped into a single, long line of numbers.
Shift all the numbers in this imaginary line by the specified amount, wrapping around the ends if necessary.
Now, take this shifted line of numbers and wrap it back into the original grid shape.
The numbers are now in their final, shifted positions within the grid.

Code Implementation

def shift_grid(grid, shift_amount):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    # Flatten the 2D grid into a 1D list
    flattened_grid = [element for row in grid for element in row]

    total_elements = number_of_rows * number_of_columns
    effective_shift = shift_amount % total_elements

    # Shift the elements in the flattened grid
    shifted_flattened_grid = flattened_grid[-effective_shift:] + flattened_grid[:-effective_shift]

    # Reshape the shifted 1D list back into a 2D grid
    shifted_grid = []
    for row_index in range(number_of_rows):
        # Reconstruct each row by taking slices of the flattened array.
        shifted_grid.append(shifted_flattened_grid[row_index * number_of_columns:(row_index + 1) * number_of_columns])

    return shifted_grid

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return the original grid if it's null or empty to avoid NullPointerException or index out of bounds.
Zero shifts (k = 0)	If k is 0, return the original grid without performing any shifts.
Large shift value (k larger than grid size)	Use the modulo operator (k % (m * n)) to reduce k to an effective shift within the grid size.
1x1 grid (single element)	A 1x1 grid shifting will always return the same grid, handle it correctly.
Rectangular grid (m != n)	Ensure the shifting logic correctly handles rectangular grids where the number of rows and columns are different.
Grid with very large dimensions (memory considerations)	Consider in-place shifting if memory constraints are a concern, trading space for time complexity.
Negative shift value (k < 0)	Handle negative shift values by converting them to positive equivalent (k = k % (m * n) + (m*n) if k < 0) to shift correctly.
Integer overflow in k calculation	Use long data type for k when calculating the effective shift to prevent integer overflow if grid dimensions are large.

Null or empty grid

How to Handle:

Return the original grid if it's null or empty to avoid NullPointerException or index out of bounds.

Zero shifts (k = 0)

How to Handle:

If k is 0, return the original grid without performing any shifts.

Large shift value (k larger than grid size)

How to Handle:

Use the modulo operator (k % (m * n)) to reduce k to an effective shift within the grid size.

1x1 grid (single element)

How to Handle:

A 1x1 grid shifting will always return the same grid, handle it correctly.

Rectangular grid (m != n)

How to Handle:

Ensure the shifting logic correctly handles rectangular grids where the number of rows and columns are different.

Grid with very large dimensions (memory considerations)

How to Handle:

Consider in-place shifting if memory constraints are a concern, trading space for time complexity.

Negative shift value (k < 0)

How to Handle:

Handle negative shift values by converting them to positive equivalent (k = k % (m * n) + (m*n) if k < 0) to shift correctly.

Integer overflow in k calculation

How to Handle:

Use long data type for k when calculating the effective shift to prevent integer overflow if grid dimensions are large.