Convert 1D Array Into 2D Array - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You receive a 1D array original and two integers m and n. The goal is to reshape the array into an m x n matrix using all elements in row-major order. If the number of elements in original is not exactly m * n, constructing such a matrix is impossible and you return an empty matrix.
The problem focuses on simple indexing logic and matrix construction using concepts from array and matrix manipulation. Since each element is processed exactly once, the challenge is mainly about mapping indices correctly.
Approach 1: Using Direct Index Mapping (O(n) time, O(m*n) space)
Create a result matrix with m rows and n columns. Iterate through the original array once and compute the target position for each element using index math. For an index i in the 1D array, the row becomes i / n and the column becomes i % n. This mapping converts the linear index into a 2D coordinate following row-major order. The approach avoids nested loops and directly calculates the correct cell for each element. Time complexity is O(n) where n is the length of the input array, and space complexity is O(m*n) for the constructed matrix.
Approach 2: Iterative Filling (O(n) time, O(m*n) space)
Another straightforward method is to build the matrix row by row. First check if original.length == m * n. If valid, iterate through the array while maintaining a pointer. For each row, fill n elements sequentially before moving to the next row. This simulates how a matrix is naturally filled in row-major order and is often easier to reason about during implementation. The algorithm still processes each element exactly once, giving O(n) time complexity and O(m*n) space complexity. This method is commonly described as a simple simulation of matrix construction.
Recommended for interviews: Direct index mapping is typically the preferred explanation. It shows you understand how linear indices translate into matrix coordinates and demonstrates comfort with array math. The iterative filling approach is equally efficient and easier to read, but interviewers often appreciate the concise index-mapping insight.
Approach 1: Approach 1: Using Direct Index Mapping
This approach involves directly mapping each element from the 1D array to its corresponding position in the 2D array.
The key idea is to iterate over the original array, calculate the correct row and column for each element, and place it accordingly in the 2D array.
If the total number of elements in the original array does not match m * n, return an empty array as it's impossible to fill the 2D array correctly.
The given C solution first checks if the transformation is feasible by comparing the size of the original array to m * n. If they do not match, an empty 2D array is returned.
If feasible, the function allocates memory for the 2D array and fills each row and column based on the equivalent index from the original array.
Complexity
Time Complexity: O(m * n), as each element in the original array is accessed exactly once to fill the 2D array.
Space Complexity: O(m * n) for the 2D array itself.
Approach 2: Approach 2: Iterative Filling
An alternative approach is to explicitly iterate over each element of the 1D array and place it in the correct position of the 2D array.
This is similar to the direct mapping approach but demonstrates a more explicit handling of indices and 2D placements.
Again, we must first ensure that conversion is feasible by matching the length of the original array and m * n. If not feasible, return an empty array.
This solution checks if the array can be converted using the same condition.
The 2D array is allocated and populated using nested loops, explicitly filling each element based on calculated indices from the original array.
Complexity
Time Complexity: O(m * n). Space Complexity: O(m * n) for memory used in 2D array creation.
Approach 3: Simulation
According to the problem description, we know that to construct an m-row and n-column two-dimensional array, it needs to satisfy that m times n equals the length of the original array. If it does not satisfy, return an empty array directly.
If it does satisfy, we can follow the process described in the problem, and put the elements from the original array into the two-dimensional array in order.
The time complexity is O(m times n), where m and n are the number of rows and columns of the two-dimensional array, respectively. Ignoring the space consumption of the answer, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Direct Index Mapping | Time Complexity: O(m * n), as each element in the original array is accessed exactly once to fill the 2D array. Space Complexity: O(m * n) for the 2D array itself. |
| Approach 2: Iterative Filling | Time Complexity: O(m * n). Space Complexity: O(m * n) for memory used in 2D array creation. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Index Mapping | O(n) | O(m*n) | Best general solution. Efficient and shows clear understanding of row/column index math. |
| Iterative Filling | O(n) | O(m*n) | Good when writing simple readable code or explaining matrix construction step-by-step. |
Video Solution
Covert 1D Array Into 2D Array - Leetcode 2022 - Python • NeetCodeIO • 8,391 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Convert 1D Array Into 2D Array easy or hard?
Convert 1D Array Into 2D Array Python/Java solution
How to solve Convert 1D Array Into 2D Array in O(n)?
What is the best approach for Convert 1D Array Into 2D Array?
Is Convert 1D Array Into 2D Array asked at Google/Amazon/Meta?
What data structure is used in Convert 1D Array Into 2D Array?
What is the time complexity of Convert 1D Array Into 2D Array?
Ready to solve this problem?
Practice Convert 1D Array Into 2D Array with our built-in code editor and test cases.
Practice on FleetCode