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.

Examples

Example 1:

$$ original = \begin{bmatrix} 1 & 2 & 3 & 4 \end{bmatrix} $$ $$ output = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} $$

1
2
3
4
5

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:

1
2
3
4

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:

1
2
3
4

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.

Solution

Video Explanation

Please refer the video for more explanation:

Method 1 - Index mapping with number of columns

Here are the steps we can take:

  • Step 1: Check if it’s possible to construct the 2D array - Before proceeding, we check if the length of the original array is equal to ( m * n ). If it’s not, it means that we cannot reshape the 1D array into the specified 2D array dimensions, so we return an empty 2D array.
  • Step 2: Fill the 2D array with elements from original
    • If the check passes, we proceed to initialize a 2D array result with dimensions ( m \times n ).
    • We iterate through the original array and for each index i, calculate the corresponding row (i / n) and column (i % n) in the 2D array.
    • We then place the element from original[i] into result[row][col].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        // Step 1: Check if it's possible to construct the 2D array
        if (original.length != m * n) {
            return new int[0][0]; // Return an empty 2D array
        }

        int[][] ans = new int[m][n];

        // Step 2: Fill the 2D array with elements from 'original'
        for (int i = 0; i < original.length; i++) {
            int row = i / n;
            int col = i % n;
            ans[row][col] = original[i];
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def construct2DArray(original, m, n):
    # Step 1: Check if it's possible to construct the 2D array
    if len(original) != m * n:
        return []

    # Step 2: Initialize the 2D array
    ans = [[0] * n for _ in range(m)]

    # Step 3: Fill the 2D array with elements from 'original'
    for i in range(len(original)):
        row = i // n
        col = i % n
        ans[row][col] = original[i]

    return ans

Complexity

  • ⏰ Time complexity: O(N) where N = m*n is number of elements in the original array
  • 🧺 Space complexity: O(N) because we create new matrix of size O(m*n) but this is not an extra space.

Method 2 - Looping on output matrix and using index from original

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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];
        int idx = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[i][j] = original[idx++];
            }
        }
        return ans;
    }
}

Method 3 - Looping on output matrix and mapping index

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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