Vultr DocsLatest Content

Convert an Array Into a 2D Array With Conditions

Updated on 12 May, 2025
Convert an Array Into a 2D Array With Conditions header image

Problem Statement

Given an integer array nums, the task is to construct a two-dimensional (2D) array that adheres to certain rules. Firstly, the 2D array must only include elements from nums. Each row in this 2D array must consist of distinct integers, meaning no row should have repeated numbers. Additionally, the challenge is to organize these rows such that the total count of rows is minimized. The 2D array can vary in the number of elements per row. The goal is to find a possible configuration for this array and return it. It is important to note that if multiple valid configurations exist, returning any one of them is acceptable.

Examples

Example 1

Input:

nums = [1,3,4,1,2,3,1]

Output:

[[1,3,4,2],[1,3],[1]]

Explanation:

We can create a 2D array that contains the following rows:
- 1,3,4,2
- 1,3
- 1
All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer.
It can be shown that we cannot have less than 3 rows in a valid array.

Example 2

Input:

nums = [1,2,3,4]

Output:

[[4,3,2,1]]

Explanation:

All elements of the array are distinct, so we can keep all of them in the first row of the 2D array.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= nums.length

Approach and Intuition

To tackle this problem, we can use a frequency-based approach combined with a strategy to reduce the number of rows. Below are steps to illustrate a possible solution:

  1. Calculate Frequency: First, determine the frequency of each integer in nums. This helps in understanding the maximum number of rows needed because the number with the highest frequency determines the minimal number of rows required.

  2. Prepare the Rows: Initialize an empty list of lists (2D array). The length of this initialization often equals the highest frequency found in the previous step, as this dictates the minimal number of rows needed.

  3. Fill Each Row: Iterate through each element in nums:

    • For each number, place it in the next available row where it hasn't been placed yet to ensure all rows contain distinct numbers.
    • Rotate through the rows to distribute numbers evenly and meet the distinct requirement.

  4. Result Compilation: After processing all numbers in nums, the list of lists prepared should meet all requirements. The structure ensures each element is placed appropriately, rows contain distinct integers, and the configuration uses the minimal number of rows possible based on the constraints.

For example, in Example 1 from the problem's statement:

  • We have numbers like 1 appearing three times, which directly leads us to need at least three rows.
  • By placing each instance of the numbers in successive rows and rotating back to the first row after reaching the last initialized row, we ensure all requirements are met efficiently.

Using this basic but effective scheme helps in achieving the desired configuration with respect to the constraints and requirements specified.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    vector<vector<int>> gatherMatrix(vector<int>& elements) {
        vector<int> count(elements.size() + 1);

        vector<vector<int>> result;
        for (int element : elements) {
            if (count[element] >= result.size()) {
                result.push_back({});
            }

            // Add the element to the subgroup indexed by current count
            result[count[element]].push_back(element);
            count[element]++;
        }

        return result;
    }
};

The provided solution transforms a linear array into a two-dimensional (2D) array subject to specific conditions using C++. The gatherMatrix function accepts a vector of integers named elements and restructures these into a 2D array based on the frequency of each element.

  • The function initializes a count vector to track occurrences of each element.
  • A 2D vector result is set up to store the final grouped integers.
  • Iterating over each element of the elements vector:
    • Ensure there is a sub-vector in result for each occurrence count of the element by checking and potentially adding a new sub-vector.
    • Add the current element to the appropriate sub-vector in result based on its current count.
    • Increment the count for that element.
  • Finally, the function returns the restructured 2D array.
java 
class Solution {

    public List<List<Integer>> gatherMatrix(int[] elements) {
        int count[] = new int[elements.length + 1];
        ArrayList<List<Integer>> result = new ArrayList<>();
        for (int element : elements) {
            if (count[element] >= result.size()) {
                result.add(new ArrayList<>());
            }

            result.get(count[element]).add(element);
            count[element]++;
        }

        return result;
    }
}

The provided Java solution, gatherMatrix, converts a one-dimensional array into a two-dimensional array (list of lists) based on specific conditions. It effectively categorizes repeated elements into separate subarrays within the main array, ensuring each occurrence of an element is in a different subarray.

Here is how the code operates:

  1. Initialize an array count which will record the number of times each element has appeared.

  2. Create an ArrayList named result which will eventually be populated with other ArrayLists representing each subarray.

  3. Loop through the input array elements. For each element:

    • If the number of times this element has appeared so far (count[element]) is equal to or exceeds the number of subarrays currently in result, add a new subarray to result.
    • Append the current element to the appropriate subarray in result, specifically the subarray that corresponds to how many times this element has previously appeared.
    • Increment the count for that element in the count array.

  4. Return result, which is now a list of lists restructured based on the frequency and order of elements in the original array.

This reorganized two-dimensional array groups instances of each number into different sublists, according to their occurrences, creating a clear and organized structure from a simple list of integers.

python 
class Solution:
    def arrangeMatrix(self, data: list[int]) -> list[list[int]]:
        count = [0] * (len(data) + 1)

        result = []
        for item in data:
            if count[item] >= len(result):
                result.append([])

            # Insert the item in its frequency-specific sub-list.
            result[count[item]].append(item)
            count[item] += 1

        return result

To solve the problem of converting an array into a 2D array based on conditions, this Python solution employs a frequency counting strategy to distribute elements into sublists. Here's how the solution works:

  1. A count list is initiated to keep a track of how many times each element has been encountered. The size of this list is one more than the size of the input list to accommodate index equal to the number of elements.

  2. An empty list named result is defined to store the sublists formed based on the frequency of each item in the input array.

  3. A loop is then used to iterate through each item in the input array data. Inside the loop:

    • It checks if the current item’s frequency is at least as high as the length of the result. If true, a new sublist is added to accommodate items with that frequency.

    • The item is appended to the sublist that corresponds to how often it has appeared so far.

    • The frequency count of the item is incremented.

  4. After processing all items in the data, the constructed result 2D list is returned, which contains elements grouped according to the number of times they occur in the input list.

By executing this code with a properly structured input list, you receive a 2D array where items are grouped into sublists based on their frequency in the initial data set.

Comments

No comments yet.