Convert 1D Array Into 2D Array solution and explanation
Google
9 more videos on this problem
Covert 1D Array Into 2D Array - Leetcode 2022 - PythonNeetCodeIO · 6:21 · 8K views
Convert 1D Array Into 2D Array | 2 Approaches | Leetcode 2022 | codestorywithMIKcodestorywithMIK · 13:15 · 6K views
2022. Convert 1D Array Into 2D Array | LEETCODE EASY | BRUTE FORCEcode Explainer · 4:11 · 4K views
2022. Convert 1D Array Into 2D Array (Leetcode Easy)Programming Live with Larry · 3:04 · 2K views
Convert 1D Array Into 2D Array - Leetcode 2022 - JavaCode With K5KC · 9:49 · 254 views
2022 Convert 1D Array Into 2D ArrayMath Geeks · 2:17 · 214 views
Daily Leetcode #1615: Sep 01, 2024 - 2022. Convert 1D Array Into 2D ArrayProgramming Live with Larry · 7:18 · 192 views
LeetCode 2022 - Convert 1D Array into 2D Array - JavaAlpha-Code · 9:52 · 129 views
2022 Convert 1D Array Into 2D Array | C++ | Simple and easy explanation | Daily Leetcode | DSAAnshul Explains · 4:53 · 126 views
Convert 1D Array Into 2D Array - Leetcode 2022King of Interviews · 10:13 · 85 views
The problem
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.
def construct2DArray(original: List[int], m: int, n: int) -> List[List[int]]:
if len(original) != m * n:
return []
return [original[i * n:(i + 1) * n] for i in range(m)]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++) {
result[i / n][i % n] = original[i];
}
return result;
}
}#include <vector>
using namespace std;
vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
if (original.size() != m * n) return {};
vector<vector<int>> matrix(m, vector<int>(n));
for (int i = 0; i < original.size(); ++i) {
matrix[i / n][i % n] = original[i];
}
return matrix;
}function construct2DArray(original, m, n) {
if (original.length !== m * n) return [];
const result = [];
for (let i = 0; i < m; i++) {
result.push(original.slice(i * n, (i + 1) * n));
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int** construct2DArray(int* original, int originalSize, int m, int n, int* returnSize, int** returnColumnSizes) {
// Check if conversion is possible
if (originalSize != m * n) {
*returnSize = 0;
return NULL;
}
// Allocate memory for the 2D array
int** array2D = (int**)malloc(m * sizeof(int*));
*returnColumnSizes = (int*)malloc(m * sizeof(int));
for (int i = 0; i < m; ++i) {
array2D[i] = (int*)malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
// Fill the 2D array
for (int j = 0; j < n; ++j) {
int index = i * n + j;
array2D[i][j] = original[index];
}
}
*returnSize = m;
return array2D;
}public class Solution {
public int[][] Construct2DArray(int[] original, int m, int n) {
if (original.Length != m * n) return new int[0][];
int[][] result = new int[m][];
for (int i = 0; i < m; i++) {
result[i] = new int[n];
for (int j = 0; j < n; j++) {
result[i][j] = original[i * n + j];
}
}
return result;
}
}This Python code leverages list slicing to neatly divide the original list into chunks of size n for each row of the 2D array.
First, it checks if the transformation is valid, and then it constructs the 2D array using list comprehension.
Time Complexity: O(m * n). Space Complexity: O(m * n), primarily due to constructing the 2D array.
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.
def construct2DArray(original: List[int], m: int, n: int) -> List[List[int]]:
if len(original) != m * n:
return []
result = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
result[i][j] = original[i * n + j]
return resultclass 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 index = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = original[index++];
}
}
return result;
}
}#include <vector>
using namespace std;
vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
if (original.size() != m * n) return {};
vector<vector<int>> matrix(m, vector<int>(n));
int currentIndex = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
matrix[i][j] = original[currentIndex++];
}
}
return matrix;
}function construct2DArray(original, m, n) {
if (original.length !== m * n) return [];
const result = Array.from({ length: m }, () => Array(n));
let index = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
result[i][j] = original[index++];
}
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int** construct2DArray(int* original, int originalSize, int m, int n, int* returnSize, int** returnColumnSizes) {
if (originalSize != m * n) {
*returnSize = 0;
return NULL;
}
int** result = (int**)malloc(m * sizeof(int*));
*returnColumnSizes = (int*)malloc(m * sizeof(int));
for (int i = 0; i < m; ++i) {
result[i] = (int*)malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
for (int j = 0; j < n; ++j) {
result[i][j] = original[i * n + j];
}
}
*returnSize = m;
return result;
}public class Solution {
public int[][] Construct2DArray(int[] original, int m, int n) {
if (original.Length != m * n) return new int[0][];
int[][] result = new int[m][];
int index = 0;
for (int i = 0; i < m; i++) {
result[i] = new int[n];
for (int j = 0; j < n; j++) {
result[i][j] = original[index++];
}
}
return result;
}
}In Python, we check if the transformation is due, initialize a zero-filled 2D array, and populate it iteratively by navigating over rows and columns with explicit assignments.
Time Complexity: O(m * n). Space Complexity: O(m * n) is attributed to the newly formed 2D array.
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).
function construct2DArray(original: number[], m: number, n: number): number[][] {
if (m * n != original.length) {
return [];
}
const ans: number[][] = [];
for (let i = 0; i < m * n; i += n) {
ans.push(original.slice(i, i + n));
}
return ans;
}func construct2DArray(original []int, m int, n int) (ans [][]int) {
if m*n != len(original) {
return [][]int{}
}
for i := 0; i < m*n; i += n {
ans = append(ans, original[i:i+n])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Direct Index Mapping | Time Complexity: O(m * n). Space Complexity: O(m * n), primarily due to constructing the 2D array. |
| Approach 2: Iterative Filling | Time Complexity: O(m * n). Space Complexity: O(m * n) is attributed to the newly formed 2D array. |
| Simulation | – |
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. |
Frequently asked questions
Is Convert 1D Array Into 2D Array easy or hard?
Convert 1D Array Into 2D Array is classified as an Easy problem. The main requirement is checking whether the array length equals m * n and correctly mapping indices while constructing the matrix.
Convert 1D Array Into 2D Array Python/Java solution
Both Python and Java solutions follow the same idea. Allocate a matrix of size m x n and fill it using index mapping or iterative row filling. Each element from the original array is inserted exactly once, resulting in O(n) time complexity.
How to solve Convert 1D Array Into 2D Array in O(n)?
First verify that original.length equals m * n. Then iterate through the array once and place each value into the matrix using row = i / n and col = i % n. This avoids nested loops and guarantees O(n) processing time.
What is the best approach for Convert 1D Array Into 2D Array?
The best approach uses direct index mapping. Iterate through the 1D array and compute the matrix position using row = i / n and col = i % n. This converts the linear index into a row-major 2D coordinate in O(n) time with O(m*n) space for the resulting matrix.
Is Convert 1D Array Into 2D Array asked at Google/Amazon/Meta?
Problems involving array reshaping and index mapping appear frequently in coding interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the concept of mapping 1D indices to 2D matrices is a common interview pattern.
What data structure is used in Convert 1D Array Into 2D Array?
The problem primarily uses arrays and matrices. The input is a 1D array and the output is a 2D matrix. The solution relies on index arithmetic to map positions between the two representations.
What is the time complexity of Convert 1D Array Into 2D Array?
The optimal solution runs in O(n) time where n is the length of the input array. Each element is processed exactly once when filling the matrix. Space complexity is O(m*n) because a new 2D matrix of size m by n must be created.