Convert 1D Array Into 2D Array

Patrick Leaton
Published: Dec. 13, 2021, 8:20 p.m.
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 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.

Example 4:

Input: original = [3], m = 1, n = 2
Output: []
Explanation:
There is 1 element in original.
It is impossible to make 1 element fill all the spots in a 1x2 2D array, so return an empty 2D array.

 

Constraints:

  • 1 <= original.length <= 5 * 10^4
  • 1 <= original[i] <= 10^5
  • 1 <= m, n <= 4 * 10^4

 

The description was taken from https://leetcode.com/problems/convert-1d-array-into-2d-array/.

Problem Solution

#Build Rows Individually
#O(M*N) Time, O(M*N) Space
class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []
       
        output, row = [], []
       
        for num in original:
            row.append(num)
            if len(row) == n:
                output.append(row)
                row = []
       
        return output
 
#List Slicing
#O(M*N) Time, O(M*N) Space
class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []
       
        output = []
       
        for i in range(len(original)):
            if i % n == 0:
                output.append(original[i:i+n])
       
        return output

Problem Explanation

Build Rows Individually

The most intuitive approach may be to build each row individually.  

To do this, we can continuously utilize a temporary array which we will fill with elements from the original array, and once the temporary array becomes the length of n, the width of the matrix we are being asked to build, we will append the temporary array to the output.

First off, let's check if it wouldn't be possible to build the given matrix.

We can check this by taking the area of the desired matrix by multiplying the given length and width, m and n, then comparing that value with the number of elements from the original array.  If these two values aren't equal, then we are either missing elements or have too many.  

If this is the case, we will return an empty list.

        if m * n != len(original):
            return []

 

Otherwise, we'll initialize our output array which we will fill with rows and the initial row temporary array.

        output, row = [], []

 

For each number in the original array, we will append it to the temporary row array.

        for num in original:
            row.append(num)

 

If the length of the row is the width of the desired matrix, we will append the row to the output then reset the row.

            if len(row) == n:
                output.append(row)
                row = []

 

Once we have filled our output array with each row, we will return it.

        return output

List Slicing

With Python, we can take advantage of List Slicing.

What we can do is traverse the original array, and each time we get to an index that divides evenly by n, the width, we can slice the array from that spot up to n indices ahead and append that to the output.  This is a similar idea to the first solution but will save us a tiny bit of space.

Same as before, if the area of the desired matrix isn't equal to the number of elements from the original array then we will return an empty array.

        if m * n != len(original):
            return []

 

Otherwise, we will initialize an output array that we will fill with rows from the original array.

        output = []

 

For each index in the original array, if we arrive at an index that divides evenly by n, then we are standing on the first index of the next row.

If this is the case then we will create a row using this array slice and append that to the output.

        for i in range(len(original)):
            if i % n == 0:
                output.append(original[i:i+n])

 

Once we have filled our output array with each row, we will return it.

        return output