# Convert 1D Array Into 2D Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/convert-1d-array-into-2d-array)
Canonical: https://scaleengineer.com/dsa/problems/convert-1d-array-into-2d-array
**Data structures:** Array, Matrix
---
## 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:**

![](https://assets.glich.co/dsa/convert-1d-array-into-2d-array/image0.png) 

**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 * 104`
* `1 <= original[i] <= 105`
* `1 <= m, n <= 4 * 104`

# Approaches
## Single Loop with Mathematical Mapping
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1.  Check if `original.length` is not equal to `m * n`. If true, return an empty 2D array (`new int[0][0]`).
2.  Initialize a new 2D array `result` of size `m x n`.
3.  Iterate with an index `i` from `0` to `original.length - 1`.
4.  Calculate `row = i / n`.
5.  Calculate `col = i % n`.
6.  Set `result[row][col] = original[i]`.
7.  Return `result`.

## Optimal Approach: Nested Loops
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.
**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.
**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 `result` array is sequential, which can be beneficial for CPU caching.
**Cons:** The code is slightly more verbose due to nested loops.
### Explanation
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.

```java
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.

```java
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.
### Algorithm
1.  Check if `original.length` is not equal to `m * n`. If true, return an empty 2D array.
2.  Initialize a new 2D array `result` of size `m x n`.
3.  Initialize a 1D array index `k = 0`.
4.  Iterate with a row index `i` from `0` to `m - 1`.
5.  Inside the row loop, iterate with a column index `j` from `0` to `n - 1`.
6.  Set `result[i][j] = original[k]`.
7.  Increment `k`.
8.  Return `result`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @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;
  };

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)]

```