Is Convert 1D Array Into 2D Array easy or hard?

Convert 1D Array Into 2D Array is classified as an Easy problem. The main requirement is checking whether the array length equals m * n and correctly mapping indices while constructing the matrix.

Convert 1D Array Into 2D Array Python/Java solution

Both Python and Java solutions follow the same idea. Allocate a matrix of size m x n and fill it using index mapping or iterative row filling. Each element from the original array is inserted exactly once, resulting in O(n) time complexity.

How to solve Convert 1D Array Into 2D Array in O(n)?

First verify that original.length equals m * n. Then iterate through the array once and place each value into the matrix using row = i / n and col = i % n. This avoids nested loops and guarantees O(n) processing time.

What is the best approach for Convert 1D Array Into 2D Array?

The best approach uses direct index mapping. Iterate through the 1D array and compute the matrix position using row = i / n and col = i % n. This converts the linear index into a row-major 2D coordinate in O(n) time with O(m*n) space for the resulting matrix.

Is Convert 1D Array Into 2D Array asked at Google/Amazon/Meta?

Problems involving array reshaping and index mapping appear frequently in coding interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the concept of mapping 1D indices to 2D matrices is a common interview pattern.

What data structure is used in Convert 1D Array Into 2D Array?

The problem primarily uses arrays and matrices. The input is a 1D array and the output is a 2D matrix. The solution relies on index arithmetic to map positions between the two representations.

What is the time complexity of Convert 1D Array Into 2D Array?

The optimal solution runs in O(n) time where n is the length of the input array. Each element is processed exactly once when filling the matrix. Space complexity is O(m*n) because a new 2D matrix of size m by n must be created.

Description Hints 3 Solution Video 6:21

2022. Convert 1D Array Into 2D Array

Easy72.2% acceptance5 companies

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation: The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Example 2:

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation: The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.

Example 3:

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation: There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.

Constraints:

1 <= original.length <= 5 * 10⁴
1 <= original[i] <= 10⁵
1 <= m, n <= 4 * 10⁴

Asked at 5 companies

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

When is it possible to convert original into a 2D array and when is it impossible?

Hint 2

It is possible if and only if m * n == original.length

Hint 3

If it is possible to convert original to a 2D array, keep an index i such that original[i] is the next element to add to the 2D array.

6:21

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution