#2610

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Convert an Array Into a 2D Array With Conditions

Learn how to convert an integer array into a 2D array with distinct rows using array scanning plus hash lookup efficiently.

array hash table

Problem Statement

Given an integer array nums, you need to construct a 2D array where each row contains unique integers from nums. You may rearrange the elements as needed, but each row must not have duplicate numbers.

Return any valid 2D array that satisfies the conditions. Rows can have different lengths, and all elements of nums must be used exactly once.

Examples

Example 1

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

Output: [[1,3,4,2],[1,3],[1]]

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]]

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

Solution Approach

Track Rows with Hash Maps

Maintain a list of sets representing each row and a hash map to track which integers are already in which rows. For each number in nums, iterate through existing rows to find one where the number is absent. Add it there or create a new row if needed.

Scan Array Sequentially

Process nums from left to right, attempting to place each integer into the first available row without duplicates. This ensures the number is placed efficiently and reduces the chance of unnecessary extra rows.

Handle Multiple Valid Outputs

Since multiple arrangements are possible, always adding numbers to the first suitable row works. Returning any of these valid 2D arrays satisfies the problem, so focus on correctness and hash-based uniqueness rather than one canonical output.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) since each element is checked against existing rows once using hash lookups. Space complexity is O(N) to store row sets and mapping of elements.

What Interviewers Usually Probe

Expecting a hash table solution to track elements in rows.
Looking for efficient O(N) placement without nested loops over elements.
Will ask about handling multiple valid 2D array outputs and row length differences.

Common Pitfalls or Variants

Common pitfalls

Trying to predefine the number of rows instead of dynamically creating them.
Using nested loops without hash lookup, which increases runtime.
Not ensuring each row contains distinct integers, violating the main condition.

Follow-up variants

Allowing each row to contain at most K elements while keeping them distinct.
Returning the arrangement with the minimal number of rows instead of any valid output.
Permuting nums before placement to observe different valid 2D array outputs.

FAQ

What is the main pattern to solve 'Convert an Array Into a 2D Array With Conditions'?

The key pattern is array scanning with hash lookup, placing each number into the first row where it is absent or creating a new row if needed.

Can the rows have different lengths?

Yes, rows can vary in length as long as each contains distinct integers and all elements of nums are used.

Is there a unique solution for the output array?

No, multiple valid 2D arrays may exist. Any arrangement that meets the conditions is acceptable.

What is the time complexity of this approach?

Using hash maps to track row contents ensures O(N) time complexity for scanning and placement.

Can I place elements in any order?

Yes, processing elements sequentially works, but always ensure placement avoids duplicates in each row.

terminal

Solution

Solution 1: Array or Hash Table

We first use an array or hash table $\textit{cnt}$ to count the frequency of each element in the array $\textit{nums}$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def findMatrix(self, nums: List[int]) -> List[List[int]]:
        cnt = Counter(nums)
        ans = []
        for x, v in cnt.items():
            for i in range(v):
                if len(ans) <= i:
                    ans.append([])
                ans[i].append(x)
        return ans

Continue Practicing

#2606 find the substring with maximum cost #2605 form smallest number from two digit arrays #2615 sum of distances