Convert 1D Array Into 2D Array

Difficulty: Easy | Acceptance: 72.20% | Paid: No Topics: Array, Matrix, Simulation

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) in 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.

• Examples
• Constraints
• Chunking (Slicing)
• Index Mapping (Math)
• Nested Loops (Simulation)

Examples

Example 1

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation: The input original has length 4, and m * n = 4, so the construction is possible.
The constructed 2D array should have 2 rows and 2 columns.
- The first row is formed by elements original[0..1] = [1, 2].
- The second row is formed by elements original[2..3] = [3, 4].

Example 2

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation: The input original has length 3, and m * n = 3, so the construction is possible.
The constructed 2D array should have 1 row and 3 columns.
- The first row is formed by elements original[0..2] = [1, 2, 3].

Example 3

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation: The input original has length 2, and m * n = 1, so the construction is not possible.
Return an empty 2D array.

Constraints

1 <= original.length <= 5 * 10⁴
1 <= m, n <= 4 * 10⁴

Chunking (Slicing)

Intuition We can directly slice the 1D array into chunks of size n to form the rows of the 2D array. This approach is clean and leverages built-in language features for array manipulation.

Steps

• Check if m * n equals the length of original. If not, return an empty array.
• Iterate from 0 to m - 1.
• In each iteration, slice the original array from index i * n to (i + 1) * n.
• Append the sliced chunk to the result array.

from typing import List

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []
        
        result = []
        for i in range(m):
            start = i * n
            end = start + n
            result.append(original[start:end])
            
        return result

Complexity

• Time: O(m * n) — We visit every element exactly once to copy it to the new structure.
• Space: O(m * n) — To store the resulting 2D array.
• Notes: In Python and JavaScript, slicing creates a new list/array, which adds to the space complexity, but this is required for the output anyway.

Index Mapping (Math)

Intuition We can map the 1D index of the original array to the 2D indices (row, column) of the result array using division and modulo operations. This avoids slicing overhead and is very cache-friendly.

Steps

• Check if m * n equals the length of original. If not, return an empty array.
• Initialize an m x n result array.
• Iterate through the original array with index k.
• Calculate the row index as k / n (integer division) and column index as k % n.
• Assign original[k] to result[row][col].

from typing import List

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []
        
        result = [[0] * n for _ in range(m)]
        for k in range(len(original)):
            row = k // n
            col = k % n
            result[row][col] = original[k]
            
        return result

Complexity

• Time: O(m * n) — We iterate through the array once.
• Space: O(m * n) — For the result array.
• Notes: This is often the most performant approach in lower-level languages like C++ and Java as it minimizes overhead.

Nested Loops (Simulation)

Intuition We can simulate the process of filling a 2D matrix row by row using two nested loops. We maintain a pointer to the current position in the original array and increment it as we fill cells.

Steps

• Check if m * n equals the length of original. If not, return an empty array.
• Initialize an m x n result array.
• Initialize an index variable idx to 0.
• Loop i from 0 to m - 1 (rows).
• Loop j from 0 to n - 1 (columns).
• Assign original[idx] to result[i][j] and increment idx.

from typing import List

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []
        
        result = [[0] * n for _ in range(m)]
        idx = 0
        for i in range(m):
            for j in range(n):
                result[i][j] = original[idx]
                idx += 1
                
        return result

Complexity

• Time: O(m * n) — We iterate through the array once.
• Space: O(m * n) — For the result array.
• Notes: This is the most straightforward simulation approach, logically equivalent to the Index Mapping method but with explicit loop control.