algoadvance

Leetcode 2022. Convert 1D Array Into 2D Array

Problem Statement

You are given a 1D array original and two integers m and n. You are tasked with creating a 2D array with m rows and n columns using all the elements from the original array.

More formally, the transformed array should be such that:

• The values of the 2D array are filled row by row from the 1D array.
• If it is not possible to form the 2D array with the given dimensions, return an empty 2D array.

Example:

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

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

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

Input: original = [3], m = 1, n = 1
Output: [[3]]

Clarifying Questions

1. Can we assume that the input array and integers m and n are always provided and non-null?
   • Yes.
2. Do the values in the original array need to be unique?
   • No, the values do not have to be unique; the task is just to reorganize the array.
3. What should be returned if the transformation is not possible?
   • An empty 2D array.

Strategy

To solve this problem, the following steps can be taken:

1. Check Feasibility:
   • The 1D array can only be converted into an m x n 2D array if and only if the length of original is exactly m * n.
2. Create the 2D Array:
   • Initialize an empty 2D array of dimensions m x n.
   • Iterate over the original array and fill the 2D array row by row.

Code

public class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        int length = original.length;

        // Check if the transformation is feasible
        if (length != m * n) {
            return new int[0][];
        }

        int[][] result = new int[m][n];
        for (int i = 0; i < length; i++) {
            result[i / n][i % n] = original[i];
        }

        return result;
    }
}

Time Complexity

• Time Complexity: O(m * n) since each element from the original array is accessed and placed exactly once in the resulting 2D array.
• Space Complexity: O(m * n) for the resultant 2D array.

This problem involves straightforward looping and index calculations, making it efficient for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?