Problem of The Day: Convert 1D Array Into 2D Array

Problem Statement

Intuition

When I first looked at this problem, my immediate thought was that it involves reshaping a 1D array into a 2D array, given the constraints of rows (m) and columns (n). The key insight is that if the total number of elements in the original array doesn’t match the product of m and n, it’s impossible to reshape the array, and I should return an empty array.

Approach

My approach involves first checking whether the product of m and n equals the length of the original array. If it doesn’t, I simply return an empty array since the reshape isn’t feasible. If the lengths match, I proceed by iterating over the rows (m) and columns (n). For each position in the new 2D array, I calculate the corresponding index in the original array and place the appropriate value in the 2D structure. Finally, I return the constructed 2D array.

Complexity

• Time complexity:
  The time complexity of my approach is \(O(m \times n)\), as I need to iterate over each element in the resulting 2D array.

• Space complexity:
  The space complexity is also \(O(m \times n)\), which accounts for the space required to store the resulting 2D array.

Code

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        if m * n != len(original):
            return []
        res = []
        for row in range(m):
            curr = []
            for col in range(n):
                index = row * n + col
                curr.append(original[index])
            res.append(curr[:])
        return res

Editorial

Approach 1: Simulation

class Solution:
    def construct2DArray(
        self, original: list[int], m: int, n: int
    ) -> list[list[int]]:
        # Check if it is possible to form an m x n 2D array
        if m * n != len(original):
            # If not, return an empty 2D array
            return []

        # Initialize the result 2D array with m rows and n columns
        result_array = [[0] * n for _ in range(m)]

        # Initialize an index to track the current position in the original array
        index = 0

        for i in range(m):
            for j in range(n):
                # Assign the current element from the original array to the 2D array
                result_array[i][j] = original[index]
                # Move to the next element in the original array
                index += 1

        return result_array

Approach 2: Math

class Solution:
    def construct2DArray(
        self, original: list[int], m: int, n: int
    ) -> list[list[int]]:
        # Check if it is possible to form an m x n 2D array
        if m * n != len(original):
            # If not, return an empty 2D array
            return []

        # Initialize the result 2D array with m rows and n columns
        result_array = [[0] * n for _ in range(m)]

        # Fill the 2D array with elements from the original array
        for i in range(len(original)):
            result_array[i // n][i % n] = original[i]

        return result_array

• time: O(M*N)
• space: O(1)