Convert 1D Array Into 2D Array
EasyPrompt
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.
Example 1:
Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation: The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.Example 2:
Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation: The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.Example 3:
Input: original = [1,2], m = 1, n = 1
Output: []
Explanation: There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.
Constraints:
1 <= original.length <= 5 * 1041 <= original[i] <= 1051 <= m, n <= 4 * 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through the source 1D array original just once. For each element in original, it calculates the corresponding row and column in the target 2D array using mathematical division and modulo operations.
Algorithm
- Check if
original.lengthis not equal tom * n. If true, return an empty 2D array (new int[0][0]). - Initialize a new 2D array
resultof sizem x n. - Iterate with an index
ifrom0tooriginal.length - 1. - Calculate
row = i / n. - Calculate
col = i % n. - Set
result[row][col] = original[i]. - Return
result.
Walkthrough
This approach iterates through the source 1D array original just once. For each element in original, it calculates the corresponding row and column in the target 2D array using mathematical division and modulo operations.
First, we perform a sanity check. A 1D array can only be converted into an m x n 2D array if the number of elements in the 1D array is exactly m * n. If original.length is not equal to m * n, it's impossible, so we return an empty 2D array.
If the lengths match, we create a new 2D array result with m rows and n columns.
We then loop through the original array from index i = 0 to original.length - 1.
For each index i, the element original[i] belongs to the 2D array at result[row][col]. The row index can be found by integer division i / n, and the column index can be found by the modulo operator i % n.
We place the element original[i] at result[i / n][i % n].
After the loop finishes, the result array is fully populated, and we return it.
class Solution { public int[][] construct2DArray(int[] original, int m, int n) { if (original.length != m * n) { return new int[0][0]; } int[][] result = new int[m][n]; for (int i = 0; i < original.length; i++) { int row = i / n; int col = i % n; result[row][col] = original[i]; } return result; }}Complexity
Time
O(N), where `N` is the number of elements in the `original` array (`N = m * n`). We iterate through the `original` array once.
Space
O(N) or O(m * n). We need to create a new 2D array of size `m x n` to store the result. If the output array is not considered extra space, the space complexity is O(1).
Trade-offs
Pros
Conceptually straightforward mapping from 1D to 2D index.
Single loop structure can be concise.
Cons
Relies on division and modulo operations inside the loop, which can be slightly less performant than simple index increments on some architectures.
This approach iterates through the structure of the target 2D array, i.e., row by row and column by column. It uses a separate pointer to keep track of the current position in the original 1D array.
Algorithm
- Check if
original.lengthis not equal tom * n. If true, return an empty 2D array. - Initialize a new 2D array
resultof sizem x n. - Initialize a 1D array index
k = 0. - Iterate with a row index
ifrom0tom - 1. - Inside the row loop, iterate with a column index
jfrom0ton - 1. - Set
result[i][j] = original[k]. - Increment
k. - Return
result.
Walkthrough
This is the most optimal approach. We begin by checking if the conversion is possible. If original.length is not equal to m * n, we return an empty 2D array.
We then initialize the m x n result array.
We use nested loops to iterate through each cell of the result array. The outer loop runs from i = 0 to m-1 (for rows), and the inner loop runs from j = 0 to n-1 (for columns).
To get the correct element from original, we can use a single index variable, say k, initialized to 0. Inside the inner loop, we assign result[i][j] = original[k] and then increment k. This is efficient as it only uses increments and has a cache-friendly memory access pattern for the destination array.
class Solution { public int[][] construct2DArray(int[] original, int m, int n) { if (original.length != m * n) { return new int[0][0]; } int[][] result = new int[m][n]; int k = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { result[i][j] = original[k++]; } } return result; }}Alternatively, we can calculate the 1D index from the 2D indices i and j on the fly. The formula is k = i * n + j. This avoids an extra variable but involves a multiplication in each iteration.
class Solution { public int[][] construct2DArray(int[] original, int m, int n) { if (original.length != m * n) { return new int[0][0]; } int[][] result = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { result[i][j] = original[i * n + j]; } } return result; }}After the loops complete, the result array is returned.
Complexity
Time
O(m * n). Since `m * n` must equal `original.length` (let's call it `N`), the complexity is O(N). We visit each cell of the new array once.
Space
O(N) or O(m * n) for the output array.
Trade-offs
Pros
Very intuitive, as it directly mimics the process of filling a 2D grid.
Uses simple index increments which can be slightly faster than division/modulo.
Memory access pattern for the
resultarray is sequential, which can be beneficial for CPU caching.
Cons
The code is slightly more verbose due to nested loops.
Solutions
Solution
class Solution {public int[][] construct2DArray(int[] original, int m, int n) { if (m * n != original.length) { return new int[0][0]; } int[][] ans = new int[m][n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans[i][j] = original[i * n + j]; } } return ans; }}/** * @param {number[]} original * @param {number} m * @param {number} n * @return {number[][]} */ var construct2DArray = function (original, m, n) { if (m * n != original.length) { return []; } const ans = []; for (let i = 0; i < m * n; i += n) { ans.push(original.slice(i, i + n)); } return ans; };class Solution {public: vector<vector<int>> construct2DArray(vector<int> &original, int m, int n) { if (m * n != original.size()) { return {}; } vector<vector<int>> ans(m, vector<int>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans[i][j] = original[i * n + j]; } } return ans; }};class Solution: def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]: if m * n != len(original): return [] return [original[i: i + n] for i in range(0, m * n, n)]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.