LeetCode 2022 - Convert 1D Array Into 2D Array

The problem asks us to transform a one-dimensional array, original, into a two-dimensional array with m rows and n columns.

leetcodeeasyarraymatrixsimulation

LeetCode Problem 2022

Difficulty: 🟢 Easy
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

The problem asks us to transform a one-dimensional array, original, into a two-dimensional array with m rows and n columns. The construction is sequential: the first n elements of original form the first row, the next n elements form the second row, and this continues until all rows are filled. If the total number of elements in original does not equal m * n, it is impossible to form a complete m x n array, so an empty 2D array should be returned.

The input original is a list of integers, m represents the number of rows, and n represents the number of columns for the 2D array. The expected output is a list of lists in Python (or a slice of slices in Go), where each inner list represents a row of the 2D array.

The constraints indicate that the length of original can be as large as 50,000 and m and n can be up to 40,000. This tells us that the solution must be efficient and avoid unnecessary copying of elements.

Important edge cases include when the number of elements in original does not match m * n, when original has only one element, or when m or n is one, which would effectively produce a row or column vector. The problem guarantees that original is non-empty and that m and n are positive.

Approaches

A brute-force approach would be to manually iterate over each row and column, extracting elements from original one by one, and appending them to a new row until we have filled m rows. While this is straightforward, the main limitation is that we would need nested loops, which might be slightly verbose, although the time complexity would still be acceptable for the constraints.

The key insight for the optimal approach is to first check whether the array can actually be reshaped by verifying if len(original) == m * n. If not, we can immediately return an empty array. Otherwise, we can use slicing in Python or indexed assignment in Go to efficiently fill the 2D array row by row. This avoids nested loops and keeps the implementation simple and clean.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(m * n) Nested loops to fill each row and column
Optimal O(m * n) O(m * n) Check feasibility and use slicing/indexing to fill rows efficiently

Algorithm Walkthrough

  1. Compute the total number of elements required for the 2D array, which is m * n.
  2. Compare this with the length of original. If they do not match, immediately return an empty array since reshaping is impossible.
  3. Initialize an empty list result (or a slice of slices in Go) to hold the rows of the 2D array.
  4. Iterate over original in steps of n (the number of columns). For each step, slice original[i:i+n] to extract the next row.
  5. Append each extracted row to result.
  6. After processing all elements, return result.

Why it works: This algorithm works because we are sequentially taking contiguous blocks of size n from original and forming rows, which aligns exactly with the problem description. The feasibility check ensures we never attempt an invalid reshape.

Python Solution

from typing import List

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

The code first checks if the reshape is possible. The loop iterates over original in increments of n to slice contiguous segments representing rows. Each slice is appended to result, which is returned at the end.

Go Solution

func construct2DArray(original []int, m int, n int) [][]int {
    if len(original) != m*n {
        return [][]int{}
    }
    
    result := make([][]int, 0, m)
    for i := 0; i < len(original); i += n {
        row := make([]int, n)
        copy(row, original[i:i+n])
        result = append(result, row)
    }
    
    return result
}

In Go, we first check feasibility, then create a slice result with capacity m. For each row, we allocate a slice of length n and use the copy function to efficiently copy elements from original. This ensures memory safety and correct row separation.

Worked Examples

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

i original[i:i+n] result
0 [1,2] [[1,2]]
2 [3,4] [[1,2],[3,4]]

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

i original[i:i+n] result
0 [1,2,3] [[1,2,3]]

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

Check: len(original) != m * n → return [].

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) We iterate through each element exactly once to fill the 2D array
Space O(m * n) We allocate a new 2D array with m rows and n columns

The time and space complexity are optimal since we must at least touch each element once and store them in the output array.

Test Cases

# provided examples
assert Solution().construct2DArray([1,2,3,4], 2, 2) == [[1,2],[3,4]]  # 2x2 reshape
assert Solution().construct2DArray([1,2,3], 1, 3) == [[1,2,3]]      # 1x3 reshape
assert Solution().construct2DArray([1,2], 1, 1) == []               # impossible reshape

# edge cases
assert Solution().construct2DArray([1], 1, 1) == [[1]]               # single element
assert Solution().construct2DArray([1,2,3,4], 4, 1) == [[1],[2],[3],[4]]  # column vector
assert Solution().construct2DArray([1,2,3,4], 1, 4) == [[1,2,3,4]]       # row vector
assert Solution().construct2DArray([1,2,3,4,5,6], 2, 3) == [[1,2,3],[4,5,6]]  # normal 2x3 reshape
assert Solution().construct2DArray([1,2,3], 2, 2) == []             # cannot reshape 3 elements into 2x2
Test Why
2x2 reshape normal case, square matrix
1x3 reshape single row
1x1 impossible cannot fit all elements
single element minimal input
column vector m > 1, n = 1
row vector m = 1, n > 1
2x3 reshape rectangular matrix
2x2 impossible insufficient elements

Edge Cases

The first edge case is when the number of elements does not match m * n. This is a common source of errors if the implementation attempts to fill the array anyway. The solution handles this with an immediate return of an empty array.

The second edge case is when m = 1 or n = 1, effectively producing a row or column vector. Slicing or indexed copying handles these without any special logic because the algorithm does not assume multiple rows or columns.

The third edge case is a single-element input. Even though trivial, it validates that the algorithm can handle minimal input without error and produces the correct 2D array [[element]]. This tests both the slicing and feasibility logic.