Leetcode 2022: Convert 1D Array Into 2D Array

Input: The input consists of a 1D integer array 'original' and two integers 'm' and 'n'.

Example: original = [1, 2, 3, 4], m = 2, n = 2

Constraints:

• 1 <= original.length <= 5 * 10^4

• 1 <= original[i] <= 10^5

• 1 <= m, n <= 4 * 10^4

Output: Return the newly constructed 2D array, or an empty array if it is impossible to fit the elements.

Example: Output: [[1, 2], [3, 4]]

Constraints:

• The 2D array must have m rows and n columns if possible.

Goal: To check if it's possible to fit the elements into a 2D array and construct it row-wise.

Steps:

• 1. Check if m * n equals the length of the original array. If not, return an empty array.

• 2. Create a new 2D array and populate each row with 'n' elements from the original array.

Goal: The constraints on the input values.

Steps:

• 1 <= original.length <= 5 * 10^4

• 1 <= original[i] <= 10^5

• 1 <= m, n <= 4 * 10^4

Assumptions:

• The input array has at least 1 element.

• The integers m and n are both greater than or equal to 1.

• Input: original = [1, 2, 3, 4], m = 2, n = 2

• Explanation: The original array has 4 elements, and it can be evenly split into 2 rows and 2 columns.

• Input: original = [1, 2], m = 1, n = 1

• Explanation: There are 2 elements in the original array, but it's impossible to fit them into a 1x1 matrix.

Approach: The approach involves first checking if the array can be split into a 2D array of the desired dimensions and then constructing it row-wise.

Observations:

• Check if the product of m and n equals the length of the array.

• If not, return an empty array.

• If m * n is equal to the length of the array, proceed to construct the 2D array.

Steps:

• 1. Verify that m * n equals the length of the array.

• 2. Loop through the original array in chunks of size 'n' to construct each row of the 2D array.

Empty Inputs:

• If the input array is empty, return an empty 2D array.

Large Inputs:

• Ensure that large inputs are handled efficiently by breaking the array into smaller rows.

Special Values:

• Handle cases where m or n is larger than the array's length, or when it's impossible to fit the elements.

Constraints:

• Ensure that the constructed array has m rows and n columns, or return an empty array.

vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
    if (m * n != original.size()) return {};
    
    vector<vector<int>> res;
    for (int i = 0; i < m*n; i+=n)
        res.push_back(vector<int>(original.begin()+i, original.begin()+i+n));
        
    return res;
}

1 : Function Definition

vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {

This defines the function 'construct2DArray', which takes a vector of integers 'original', and two integers 'm' and 'n' to form a 2D array.

2 : Condition Check

    if (m * n != original.size()) return {};

This checks if the total number of elements in 'original' matches the required size of the 2D array (m * n). If not, it returns an empty vector.

3 : Variable Initialization

    vector<vector<int>> res;

This initializes a 2D vector 'res' which will hold the result, i.e., the reconstructed 2D array.

4 : Loop Start

    for (int i = 0; i < m*n; i+=n)

This loop iterates over the original array in steps of size 'n', essentially breaking the 1D array into chunks of 'n' elements each to form the rows of the 2D array.

5 : Row Construction

        res.push_back(vector<int>(original.begin()+i, original.begin()+i+n));

This line extracts a subarray from 'original' starting from index 'i' to 'i+n' and adds it as a new row in the result 2D array 'res'.

6 : Return Statement

    return res;

This returns the 2D array 'res' after all rows have been constructed.

Best Case: O(m * n)

Average Case: O(m * n)

Worst Case: O(m * n)

Description: We need to iterate through the entire array to construct the 2D matrix.

Best Case: O(m * n)

Worst Case: O(m * n)

Description: We use extra space for the 2D matrix, which has m * n elements.

Leetcode 2022: Convert 1D Array Into 2D Array

Explore →