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 required to write a function that reshapes the 1D array into a 2D array with m rows and n columns.

If it is not possible to reshape the array due to mismatch in total size, return an empty 2D array.

Example 1:

Example 2:

Example 3:

Clarifying Questions

  1. Q: What should be done if original is empty?
    • A: If original is empty and m and n are both zero, return an empty 2D array. If m or n are non-zero, return an empty array as reshaping is not possible.
  2. Q: Are the elements in original always positive integers?
    • A: The elements can be any integer, but it doesn’t affect the reshaping logic.
  3. Q: What if m or n are less than or equal to zero?
    • A: Since the dimensions for a matrix can’t be non-positive, we should return an empty array in such cases.

Strategy

  1. Check Validity: First, we need to check if the reshape is possible by comparing the size of original with m * n.
  2. Initialization: If sizes match, initialize a 2D vector of size m by n.
  3. Filling the 2D Array: Use a nested loop or row-major indexing to fill in the 2D array from the 1D array.
  4. Return Result: Return the freshly constructed 2D array if reshaping is possible; otherwise, return an empty vector.

Code

Here’s the C++ code to convert the 1D array into a 2D array:

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
        int totalSize = original.size();
        if (totalSize != m * n) {
            return vector<vector<int>>(); // Return an empty vector if reshaping is not possible
        }

        vector<vector<int>> result(m, vector<int>(n, 0));
        for (int i = 0; i < totalSize; ++i) {
            result[i / n][i % n] = original[i];
        }

        return result;
    }
};

Time Complexity

The time complexity for this solution is O(m * n) or O(totalSize) because we are iterating over the original array exactly once to fill the 2D array. The auxiliary space complexity is O(1), excluding the space needed for the result vector.

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