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.
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; }}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.