{x}
blog image

Convert 1D Array Into 2D Array

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

Solution Explanation: Converting a 1D Array to a 2D Array

This problem involves transforming a one-dimensional (1D) array into a two-dimensional (2D) array with specified dimensions (m rows and n columns). The key constraint is that all elements from the original array must be used in the 2D array.

Approach:

The solution employs a straightforward approach:

  1. Dimension Check: First, it verifies if the dimensions m and n are valid. The product of m and n must equal the length of the original array (original.length). If not, it's impossible to create the 2D array, so an empty array is returned.

  2. Array Construction: If the dimensions are valid, the solution iterates through the original array and populates the 2D array row by row. It uses a nested loop or list comprehension (depending on the programming language) to achieve this. The index calculations ensure that elements are placed correctly into their corresponding rows and columns.

Code (with explanations):

I'll focus on the Python and Java solutions as they represent common approaches:

Python:

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []  # Invalid dimensions
        return [original[i : i + n] for i in range(0, m * n, n)]

  • if m * n != len(original): return []: This line performs the dimension check. If m * n (total number of elements in the desired 2D array) doesn't match len(original) (the number of elements in the 1D array), an empty list is returned.

  • [original[i : i + n] for i in range(0, m * n, n)]: This is a list comprehension. It's a concise way to create a list.

    • range(0, m * n, n): This generates a sequence of indices: 0, n, 2n, 3n... These are the starting indices of each row in the original array.
    • original[i : i + n]: This slices the original array, taking n elements starting from index i. Each slice represents a row in the 2D array.

Java:

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        if (m * n != original.length) {
            return new int[0][0]; // Invalid dimensions
        }
        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;
    }
}

  • if (m * n != original.length): This performs the dimension check, similar to the Python code.

  • int[][] ans = new int[m][n];: This creates a 2D integer array with m rows and n columns.

  • for loops: The nested loops iterate through the rows (i) and columns (j) of the ans array.

  • ans[i][j] = original[i * n + j];: This is the crucial line. It calculates the index in the original array (i * n + j) and assigns the element to the correct position in the ans array.

Time and Space Complexity:

  • Time Complexity: O(m * n) - The nested loops (or list comprehension in Python) iterate through all the elements of the 2D array, which has m * n elements.

  • Space Complexity: O(m * n) - The space is dominated by the newly created 2D array ans, which has m * n elements. The space used by intermediate variables is negligible compared to this.

Other languages (C++, Go, TypeScript, JavaScript) follow similar logic, just with different syntax. The core algorithm remains consistent across all implementations.