Jobs

Interviews

Discussions

Convert 1D Array Into 2D Array

Easy

Convert 1D Array Into 2D Array

Easy

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 `m` or `n` ever be zero, and if so, what should I return?
If the original array's length is not perfectly divisible by `m * n`, what should the function return? Should I return an empty array, `null`, or throw an exception?
Are `m` and `n` always positive integers?
What is the data type of the elements within the 1D array? Can I assume it's integers, or could it be floats or other types?
Is the order of elements in the original 1D array important for constructing the 2D array? Should I fill the 2D array row-by-row from the original array?

Brute Force Solution

Approach

The brute force approach to reshaping a one-dimensional list into a two-dimensional one involves checking every possible way to distribute the elements. We try different row and column combinations until a valid arrangement is found. Essentially, we exhaustively explore all configurations until we hit the right one.

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

Begin by figuring out if it's even possible to create a two-dimensional structure with the specified dimensions using the available elements. If there aren't enough elements, or too many, then it cannot be converted and we can immediately determine this.
If the dimensions are valid, start filling the new structure row by row.
Take the first chunk of elements from the original list and put them into the first row.
Then, take the next chunk of elements and put them into the second row, and so on.
Continue this process until all elements from the original list are used to fill all the positions in the new structure.
Finally, confirm that you have successfully used all the elements and the new structure is now completely filled.

Code Implementation

def convert_1d_to_2d_array(original_list, num_rows, num_columns):
    total_elements = len(original_list)
    
    # Check if reshaping is possible based on total element counts.
    if total_elements != num_rows * num_columns:
        return []

    reshaped_array = []

    # Iterate through the number of rows to create.
    for row_index in range(num_rows):
        row = []

        # Fill each row with the correct number of elements.
        for column_index in range(num_columns):
            element_index = row_index * num_columns + column_index
            row.append(original_list[element_index])

        reshaped_array.append(row)

    # Return the fully constructed 2D array.
    return reshaped_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the original 1D array of length n, where n is the number of elements in the input array, to fill the 2D array. Each element is visited and placed exactly once. The number of rows and columns (r and c) are predetermined and based on the dimensions provided, and their product equals n (r * c = n). Therefore, the process of filling the 2D array involves a single pass through the n elements, resulting in O(n) time complexity.

Space Complexity

O(m*n) – The algorithm creates a new 2D array of size m x n, where m is the number of rows and n is the number of columns in the reshaped array. This array is used to store the reshaped elements. The space required for this new array is directly proportional to the product of m and n. Therefore, the auxiliary space complexity is O(m*n).

Optimal Solution

Approach

We're taking a single list and reshaping it into a grid with a specific number of rows and columns. The best way to do this is to methodically fill each spot in the grid, making sure we don't run out of elements or go past the grid's boundaries.

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

First, check if it's even possible to form the grid. See if the total number of items in the original list matches the total number of spots in the grid (rows times columns). If not, it's impossible, and we can stop.
Create a new empty grid with the right number of rows and columns.
Now, go through the original list, item by item.
Place each item from the original list into the next available spot in the new grid, filling each row from left to right before moving to the next row.
Keep going until you've placed all the items from the original list into the new grid.
You'll end up with a new grid that has the items arranged as expected.

Code Implementation

def convert_1d_to_2d(original_array, number_of_rows, number_of_columns):
    array_length = len(original_array)

    # Check if reshaping is possible.
    if array_length != number_of_rows * number_of_columns:
        return []

    new_2d_array = [[0] * number_of_columns for _ in range(number_of_rows)]

    original_index = 0
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            #Populate the 2D array element by element.
            new_2d_array[row_index][column_index] = original_array[original_index]
            original_index += 1

    return new_2d_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array 'original' of size 'n' exactly once to populate the 2D array. Creating the 2D array itself takes constant time relative to the input size. Each element from the original array is placed into its corresponding position in the 2D array in constant time. Therefore, the dominant operation is the single iteration through the original array, resulting in O(n) time complexity.

Space Complexity

O(R * C) – The primary space complexity comes from creating a new 2D array (the 'grid') to store the reshaped elements. The dimensions of this grid are determined by the input rows (R) and columns (C). Therefore, the auxiliary space required is proportional to the total number of elements in the grid, which is R multiplied by C. No other significant auxiliary space is used beyond this resulting 2D array.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty 2D array or throw an IllegalArgumentException, depending on requirements.
Invalid dimensions: m * n != original array length	Return an empty 2D array or throw an IllegalArgumentException to indicate no valid conversion is possible.
m or n is zero	Return an empty 2D array immediately as no rows or columns can be created.
Large array size leading to potential integer overflow when calculating m * n	Check for potential integer overflow before multiplication, and if detected, throw an exception.
Array contains negative numbers	The algorithm should handle negative numbers without any special consideration as they are simply elements in the array.
m or n is negative	Throw IllegalArgumentException as the dimensions of the array must be positive integers.
Array with all identical values	The algorithm constructs the 2D array regardless of the value distribution within the 1D array.
m or n equals the length of the original array	The algorithm correctly constructs a 2D array with one row or one column as needed

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 `m` or `n` ever be zero, and if so, what should I return?
If the original array's length is not perfectly divisible by `m * n`, what should the function return? Should I return an empty array, `null`, or throw an exception?
Are `m` and `n` always positive integers?
What is the data type of the elements within the 1D array? Can I assume it's integers, or could it be floats or other types?
Is the order of elements in the original 1D array important for constructing the 2D array? Should I fill the 2D array row-by-row from the original array?

Brute Force Solution

Approach

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

Begin by figuring out if it's even possible to create a two-dimensional structure with the specified dimensions using the available elements. If there aren't enough elements, or too many, then it cannot be converted and we can immediately determine this.
If the dimensions are valid, start filling the new structure row by row.
Take the first chunk of elements from the original list and put them into the first row.
Then, take the next chunk of elements and put them into the second row, and so on.
Continue this process until all elements from the original list are used to fill all the positions in the new structure.
Finally, confirm that you have successfully used all the elements and the new structure is now completely filled.

Code Implementation

def convert_1d_to_2d_array(original_list, num_rows, num_columns):
    total_elements = len(original_list)
    
    # Check if reshaping is possible based on total element counts.
    if total_elements != num_rows * num_columns:
        return []

    reshaped_array = []

    # Iterate through the number of rows to create.
    for row_index in range(num_rows):
        row = []

        # Fill each row with the correct number of elements.
        for column_index in range(num_columns):
            element_index = row_index * num_columns + column_index
            row.append(original_list[element_index])

        reshaped_array.append(row)

    # Return the fully constructed 2D array.
    return reshaped_array

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check if it's even possible to form the grid. See if the total number of items in the original list matches the total number of spots in the grid (rows times columns). If not, it's impossible, and we can stop.
Create a new empty grid with the right number of rows and columns.
Now, go through the original list, item by item.
Place each item from the original list into the next available spot in the new grid, filling each row from left to right before moving to the next row.
Keep going until you've placed all the items from the original list into the new grid.
You'll end up with a new grid that has the items arranged as expected.

Code Implementation

def convert_1d_to_2d(original_array, number_of_rows, number_of_columns):
    array_length = len(original_array)

    # Check if reshaping is possible.
    if array_length != number_of_rows * number_of_columns:
        return []

    new_2d_array = [[0] * number_of_columns for _ in range(number_of_rows)]

    original_index = 0
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            #Populate the 2D array element by element.
            new_2d_array[row_index][column_index] = original_array[original_index]
            original_index += 1

    return new_2d_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty 2D array or throw an IllegalArgumentException, depending on requirements.
Invalid dimensions: m * n != original array length	Return an empty 2D array or throw an IllegalArgumentException to indicate no valid conversion is possible.
m or n is zero	Return an empty 2D array immediately as no rows or columns can be created.
Large array size leading to potential integer overflow when calculating m * n	Check for potential integer overflow before multiplication, and if detected, throw an exception.
Array contains negative numbers	The algorithm should handle negative numbers without any special consideration as they are simply elements in the array.
m or n is negative	Throw IllegalArgumentException as the dimensions of the array must be positive integers.
Array with all identical values	The algorithm constructs the 2D array regardless of the value distribution within the 1D array.
m or n equals the length of the original array	The algorithm correctly constructs a 2D array with one row or one column as needed