2022. Convert 1D Array Into 2D Array

Description

You are given a 1D array original and two integers m and n. You need to transform the original array into a 2D array with m rows and n columns. If it is impossible to do so (i.e., if the total number of elements in original is not equal to m * n), return an empty 2D array.

Intuition

The problem requires restructuring a 1D array into a 2D matrix. The key insight is that the total number of elements in the original array must match the total number of elements in the desired 2D array. If this condition is met, the elements can be mapped directly to their new positions in the 2D array.

Approach

1. Check Validity: - First, check if the length of the original array is equal to m * n. If not, it is impossible to reshape the array, so return an empty array.
2. Reshape the Array: - If the transformation is possible, iterate through the original array, and populate the 2D array by slicing the original array into chunks of size n.
3. Edge Cases: - If the original array is empty or if m or n is zero, return an empty array.

Complexity

Time Complexity:

• The time complexity is O(m * n), where m * n is the number of elements in the resulting 2D array. This corresponds to the time it takes to iterate over and assign values to the 2D array.

Space Complexity:

• The space complexity is O(m * n) as we are constructing a new 2D array to store the result.

Code

C++

class Solution {
public:
    std::vector> construct2DArray(std::vector& original, int m, int n) {
        if (m * n != original.size()) {
            return {};
        }
        
        std::vector> result(m, std::vector(n));
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                result[i][j] = original[i * n + j];
            }
        }
        
        return result;
    }
};

Python

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

Java

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        if (m * n != original.length) {
            return new int[0][0];
        }
        
        int[][] result = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = original[i * n + j];
            }
        }
        
        return result;
    }
}

JavaScript

/**
 * @param {number[]} original
 * @param {number} m
 * @param {number} n
 * @return {number[][]}
 */
var construct2DArray = function(original, m, n) {
    let result = new Array(m).fill().map(() => []);
    switch (m * n === original.length ? 1 : 0) {
        case 1:
            let i = 0;
            while (i < m) {
                result[i] = original.slice(i * n, i * n + n);
                i++;
            }
            break;
        default:
            return [];
    }
    return result;
};