LeetCode 2022: Convert 1D Array Into 2D Array

If we cannot fit all elements of original in the $(m \times n)$ grid, we return empty.

Otherwise, say we have already copied $k$ elements from the original. Then the next element would be at index $k$ of the original. If we translate $k$ into grid coordinates, $k = (\text{count-copied-rows}) \cdot n + \text{count-copied-columns}$ . In other words, original[k] corresponds to grid[count-copied-rows * row-width][count-copied-columns].

We can copy by grid: $(\text{row}, \text{col}) \rightarrow k$ or by original: $k \rightarrow (\text{row}, \text{col})$ .

By grid

For the cell $(\texttt{row}, \texttt{col})$ we copy the number at the index $(\texttt{row} \cdot n + \texttt{col})$ of the original.

Time: $\mathcal{O}(m \cdot n)$ , space: $\mathcal{O}(\texttt{output-size})$ .

from itertools import product as cartesian

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m*n != len(original):
            return []

        two_d = [
            [0] * n for _ in range(m)
        ]

        for r, c in cartesian(range(m), range(n)):
            i = r*n + c
            two_d[r][c] = original[i]

        return two_d

By original

We copy $\texttt{original}[k]$ into $\text{grid}\left[ \frac{k}{n} \right]\left[ k \bmod n \right]$ .

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m*n != len(original):
            return []

        two_d = [
            [0] * n for _ in range(m)
        ]

        for i, x in enumerate(original):
            r, c = divmod(i, n)
            two_d[r][c] = x

        return two_d

unreasonably effective