Convert 1D Array Into 2D Array
Easy
You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.
The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.
Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.
For example:
original = [1,2,3,4], m = 2, n = 2. The expected output is [[1,2],[3,4]].
original = [1,2,3], m = 1, n = 3. The expected output is [[1,2,3]].
original = [1,2], m = 1, n = 1. The expected output is [].
How would you implement a function to solve this problem efficiently? What is the time and space complexity of your solution? Consider edge cases such as when the original array cannot form the desired 2D array.
Solution
Naive Solution
The most straightforward approach is to iterate through the original array and populate the 2D array row by row. We need to check if the total number of elements in original matches the required size of the 2D array (m * n). If not, we return an empty array.
Code:
def construct2DArray_naive(original, m, n):
if m * n != len(original):
return []
result = []
for i in range(m):
row = []
for j in range(n):
row.append(original[i * n + j])
result.append(row)
return result
Time Complexity: O(m*n)
We iterate through each cell of the m x n matrix once.
Space Complexity: O(m*n)
We create a new 2D array of size m x n to store the result.
Optimal Solution
The optimal solution is essentially the same as the naive solution, as we must visit each element to construct the 2D array. However, we can make the code slightly more concise.
Code:
def construct2DArray_optimal(original, m, n):
if m * n != len(original):
return []
result = [original[i*n:(i+1)*n] for i in range(m)]
return result
Time Complexity: O(m*n)
We iterate through each cell of the m x n matrix once.
Space Complexity: O(m*n)
We create a new 2D array of size m x n to store the result.
Edge Cases
- If
m * nis not equal to the length of the original array, it's impossible to construct the 2D array, so we return an empty array. - Empty
originalarray. mornis zero.
