Convert 1D Array Into 2D Array
Problem Description
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 the original.
The elements from indices 0 to n - 1 (inclusive) of the original should form the first row of the constructed 2D array, and 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 impossible.
Problem Explanation
- We are given a 1D array with some elements and the dimensions of the 2D array we have to return, two integers denoting the rows and columns of the matrix i.e. m and n.
- All the elements from the original array should be used to fill in the 2D array created with the said dimensions, i.e. size of the original array should be equal to the number of elements in the 2D array. If it's not possible then the question asks us to return an empty array.
- Elements in the matrix should be filled sequentially, i.e., the first row should be filled completely first, and then we can proceed to fill the second row, and so on.
When should we return an empty array?
When the dimensions given for the 2D array do not exactly accommodate all the elements of the given original 1D array. If the size dimensions of a number of rows and cols are say m and n then the number of elements that a 2D array can have is m×n. Which according to the question should be equal to the size of the 1D original given array, m×n = N, where m and n are the number of rows and cols and N is the length of the 1D array.
Examples
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 the original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in the 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 the 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 the original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.
Constraints
1 <= original.length <= 5 × 104
1 <= original[i] <= 105
1 <= m, n <= 4 × 104
Approach - 1
Intuition
The solution comes from the understanding that the 1D array needs to be mapped into a 2D matrix. Since the problem provides specific dimensions m (rows) and n (columns), the main idea is to check whether the total number of elements in the 1D array matches the required size of the 2D matrix (m×n). If the sizes match, the conversion is straightforward by iterating over the matrix and assigning values from the 1D array. The logic of matrix[i][j] = original[index++] ensures that elements are filled row-wise from the original array.
Pseudo Code
- Check size compatibility: If the size of the original array does not match m×n, return an empty 2D array.
- Create 2D matrix: Create a 2D matrix of size m×n.
- Fill the matrix:
Initialize an index index = 0.
Iterate over each row iii from 0 to m−1: For each row, iterate over each column j from 0 to n−1: Set matrix[i][j] = original[index] and increment index.
Return the filled matrix.
Dry Run (Example 1)
- Input: original = [1, 2, 3, 4], m = 2, n = 2.
- Step 1: Check if the total number of elements matches 2×2=4. Since it does, proceed.
- Step 2: Create a 2D matrix matrix = [[0, 0], [0, 0]].
- Step 3: Initialize index = 0.
- For i = 0, j = 0: matrix[0][0] = original[0] = 1, increment index = 1.
- For i = 0, j = 1: matrix[0][1] = original[1] = 2, increment index = 2.
- For i = 1, j = 0: matrix[1][0] = original[2] = 3, increment index = 3.
- For i = 1, j = 1: matrix[1][1] = original[3] = 4, increment index = 4.
Step 4: Return matrix = [[1, 2], [3, 4]].
Approach 1 in All Languages
C++ Code Try on Compiler!
class Solution {
public:
vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
//If the matrix contains a different number of elements
//than the original array then return an empty array
//as said in the question
if(m*n != original.size()) return {};
//Create a 2D array of the dimensions given in the question
vector<vector<int>> matrix(m,vector<int> (n,0));
//To keep track of the index in the original array
int index = 0;
//Iterate over our created array
//Iterate over m rows
for(int i = 0; i < m; i++){
//Iterate over n columns
for(int j = 0; j < n; j++){
//Assign each cell in the matrix with the
//current pointing element in the original array
//And then increment the index pointer to point
//next element
matrix[i][j] = original[index++];
}
}
//return the filled matrix
return matrix;
}
};Java Code Try on Compiler!
class Solution {
public int[][] construct2DArray(int[] original, int m, int n) {
// If the dimensions don't match the size of the original array, return an empty array
if (m * n != original.length) {
return new int[0][0];
}
// Initialize the 2D array
int[][] matrix = new int[m][n];
int index = 0;
// Fill the 2D array with values from the original array
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = original[index++];
}
}
return matrix;
}
}Python Code Try on Compiler!
class Solution:
def construct2DArray(self, original, m, n):
# If the dimensions don't match the size of the original array, return an empty array
if m * n != len(original):
return []
# Initialize the 2D array and fill it with values from the original array
matrix = []
index = 0
for i in range(m):
row = []
for j in range(n):
row.append(original[index])
index += 1
matrix.append(row)
return matrixJavascript Code Try on Compiler!
class Solution {
construct2DArray(original, m, n) {
// If the dimensions don't match the size of the original array, return an empty array
if (m * n !== original.length) return [];
// Initialize the 2D array and fill it with values from the original array
const matrix = [];
let index = 0;
for (let i = 0; i < m; i++) {
const row = [];
for (let j = 0; j < n; j++) {
row.push(original[index++]);
}
matrix.push(row);
}
return matrix;
}
}Time Complexity : O(m*n)
The time complexity of this solution can be understood by looking at how we iterate over the 2D array. We first create a new 2D array with dimensions m×n. Then, we fill this array by iterating through the original 1D array. Since the size of the newly created 2D array is m×n, and we are assigning values to each element of the 2D array, the time complexity is proportional to the number of elements in the 2D array.
Thus, the time complexity is O(m×n), as we have to iterate through all m×n elements.
Looking at the constraints, in the worst case, the size of the 2D array (and therefore the size of the original array) is 5×104. This means the worst-case time complexity will remain O(5×104), which is well within the computational limits of 108, making this solution efficient and acceptable for the given problem constraints.
Space Complexity : O(m*n)
Now let’s evaluate the space complexity of this solution, taking into account both the total space used and the auxiliary space.
- Total Space Complexity: The total space used by the algorithm is determined by the size of the 2D array we create, which is m×n. Since we need to store m×n elements in the matrix, the total space complexity is O(m×n).
- Auxiliary Space Complexity: The auxiliary space refers to any extra space that the algorithm uses aside from the input and output data. In this case, no additional space is used beyond the 2D matrix itself. We are not using any extra data structures or temporary storage that grows with the input size. Therefore, the auxiliary space complexity is O(1), meaning the algorithm uses constant extra space.
In conclusion, while the total space complexity is O(m×n) due to the matrix creation, the auxiliary space complexity remains O(1) since no extra storage is required for processing.
Is there some easier way to write this code?
In the previous solution, we used two nested loops to fill the matrix row by row from the 1D array. Now, in this approach, instead of manually iterating over rows and columns, we leverage modulus and integer division to directly calculate where each element from the 1D array should go in the 2D array. This method is more compact and eliminates the need for the nested loop structure.
Let’s break it down by asking ourselves a couple of questions to get to the core of how and why it works.
How can we assign each element from a 1D array to the correct position in a 2D array?
To assign each element from a one-dimensional (1D) array to the correct position in a two-dimensional (2D) array, we can leverage the structure of the matrix, which consists of m rows and n columns. The objective is to map each element in the 1D array to its corresponding position in the 2D matrix as we progress through the 1D array.
Why does matrix[i/n][i%n] = original[i] work?
Mathematically, for any given index i in the 1D array, we can determine the appropriate row and column in the 2D array using simple calculations. The row index can be computed using integer division: i/n. This operation effectively tells us how many full rows of n columns fit within the first i elements. Conversely, the column index can be determined using the modulus operation: i%n. This calculation provides the remainder when iii is divided by n, which indicates the specific position of the element within the current row.
This approach enables us to map each element from the 1D array into the correct row and column of the 2D matrix efficiently, without the need for nested loops. Thus, the assignment operation matrix[i/n][i%n] = original[i] effectively positions each element in the right spot. Here, i/n yields the appropriate row index, while i%n specifies the correct column index, ensuring that every element from the 1D array is correctly positioned in the 2D matrix.
Intuition
Instead of iterating over rows and columns separately, this solution treats the 1D array as a single sequence where each element is naturally assigned to a calculated position in the 2D array using mathematical relationships (i/n for rows and i%n for columns). This approach simplifies the logic and removes the need for two explicit loops.
Pseudo Code
- Check size compatibility: If the size of the original array does not match m×n, return an empty 2D array.
- Create 2D matrix: Create a 2D matrix of size m×n.
- Fill the matrix using math: Iterate over each element in the original array, calculate the corresponding row and column using integer division and modulus, and assign the value.
- Return the filled matrix.
Dry Run (Example 1)
- Input: original = [1, 2, 3, 4], m = 2, n = 2.
- Step 1: Check if the total number of elements matches 2×2=4. Since it does, proceed.
- Step 2: Create a 2D matrix matrix = [[0, 0], [0, 0]].
- Step 3: Iterate through the original array:
- For i=0, calculate i / n = 0 / 2 = 0 (row), i % n = 0 % 2 = 0 (column), assign matrix[0][0] = original[0] = 1.
- For i=1, calculate i / n = 1 / 2 = 0 (row), i % n = 1 % 2 = 1 (column), assign matrix[0][1] = original[1] = 2.
- For i=2, calculate i / n = 2 / 2 = 1 (row), i % n = 2 % 2 = 0 (column), assign matrix[1][0] = original[2] = 3.
- For i=3, calculate i / n = 3 / 2 = 1 (row), i % n = 3 % 2 = 1 (column), assign matrix[1][1] = original[3] = 4.
- Step 4: Return matrix = [[1, 2], [3, 4]].
Math Breakdown
- The key idea here is that for any index in the original array:
- The row index can be found by dividing i by n (the number of columns). This gives us the number of full rows that have been completed, hence the row to which i belong.
- The column index is found by the remainder when i is divided by n. This tells us how far along the current row the element should go.
For example, for i=2:
- Row: 2/2=1 (this means we’re in the second row).
- Column: 2%2=0 (this means it’s the first element of the row).
Alternate Approach Code in All Languages
C++ Code Try on Compiler!
class Solution {
public:
vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
//If the matrix contains a different number of elements
//than the original array then return an empty array
//as said in the question
if(m*n != original.size()) return {};
//Create a 2D array of the dimensions given in the question
vector<vector<int>> matrix(m,vector<int> (n,0));
//Iterate through the elements of the original array
for(int i = 0 ;i < original.size(); i++){
//Calculate and assign that element to
//its relevant position in the 2D array
matrix[i/n][i%n] = original[i];
}
//return your filled 2D array
return matrix;
}
};Java Code Try on Compiler!
class Solution {
public int[][] construct2DArray(int[] original, int m, int n) {
// If the matrix contains a different number of elements
// than the original array then return an empty array
//As said in the question
if (m * n != original.length) return new int[][]{};
// Create a 2D array of the dimensions given in the question
int[][] matrix = new int[m][n];
// Iterate through the elements of the original array
for (int i = 0; i < original.length; i++) {
// Calculate and assign that element to
// its relevant position in the 2D array
matrix[i / n][i % n] = original[i];
}
// return your filled 2D array
return matrix;
}
}
Python Code Try on Compiler!
class Solution:
def construct2DArray(self, original, m, n):
# If the matrix contains a different number of elements
# than the original array then return an empty array
# As said in the question
if m * n != len(original):
return []
# Create a 2D array of the dimensions given in the question
matrix = [[0] * n for _ in range(m)]
# Iterate through the elements of the original array
for i in range(len(original)):
# Calculate and assign that element to
# its relevant position in the 2D array
matrix[i // n][i % n] = original[i]
# return your filled 2D array
return matrix
Javascript Code Try on Compiler!
class Solution {
construct2DArray(original, m, n) {
// If the matrix contains a different number of elements
// than the original array, return an empty array
if (m * n !== original.length) {
return [];
}
// Create a 2D array of the dimensions given in the question
const matrix = Array.from({ length: m }, () => Array(n).fill(0));
// Iterate through the elements of the original array
for (let i = 0; i < original.length; i++) {
// Calculate and assign the element to its relevant position
matrix[Math.floor(i / n)][i % n] = original[i];
}
// Return the filled 2D array
return matrix;
}
}Time Complexity : O(m×n)
The time complexity of the solution can be analyzed based on the iterations through the original array. We iterate over the entire original array, which has a length of N. Since the problem specifies that N must be equal to m×n(the total number of elements in the 2D array), we can express the time complexity in terms of the dimensions of the matrix.
Thus, the time complexity is O(m×n).
When we consider the constraints of the problem, in the worst case, we will be iterating through the maximum size of the original array, which can reach 5 × 104. This corresponds to a worst-case scenario where m×n approaches this upper limit, yielding a time complexity that remains well within the acceptable threshold of 10^8. Therefore, we can conclude that this solution is efficient and acceptable for the given constraints.
Space Complexity : O(m×n)
Now, let’s analyze the space complexity of the solution. The space complexity consists of two components: total space complexity and auxiliary space complexity.
- Total Space Complexity: The total space used by the algorithm includes the space required to store the output matrix, which is of size m×n. This means that the total space complexity is O(m×n).
- Auxiliary Space Complexity: Auxiliary space refers to the extra space or temporary space used by the algorithm, excluding the space for the input and output. In this solution, we do not use any additional data structures that grow with the input size. All we do is create the output matrix, and there are no other significant variables that occupy space proportional to the input. Therefore, the auxiliary space complexity is O(1), indicating that we use constant extra space.
In summary, while the total space complexity is O(m×n) due to the output matrix, the auxiliary space complexity remains O(1) since we do not utilize any additional storage during the computation.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.