Convert an Array Into a 2D Array With Conditions Solution In C++/Java/Python/Javascript
Problem Description
Imagine you are given a list of numbers and need to transform it into a 2D array while following some rules. Each row in the 2D array must contain distinct numbers—no duplicates are allowed within a row. If a number appears multiple times in the input list, it needs to be placed in separate rows. Additionally, the 2D array can have a different number of elements in each row, meaning rows don’t need to have the same length.
The challenge is to minimize the number of rows while still using all the numbers. For example, if the input is [1, 3, 4, 1, 2, 3, 1], one way to arrange it would be [[1, 3, 4, 2], [1, 3], [1]]. Each row has distinct values, and there are only three rows—the minimum possible for this input. On the other hand, if the input list contains all unique numbers, like [1, 2, 3, 4], you can place everything into a single row: [[1, 2, 3, 4]].
The task in the Convert an Array Into a 2D Array With Conditions LeetCode solution is to find the most efficient way to distribute the numbers into rows while ensuring these conditions are met.
Real-world Example
Imagine a classroom where students need to be seated in rows based on their unique ID numbers. The rule is that no row should have duplicate student IDs. As students enter, they are assigned to existing rows if their ID is not already present; otherwise, a new row is created. This ensures proper distribution while minimizing the number of rows.
Similarly, in the Convert an Array Into a 2D Array With Conditions LeetCode solution, we need to distribute numbers into rows while ensuring no duplicates exist in any row, optimizing space and structure efficiently.
Input: nums = [1, 3, 4, 1, 2, 3, 1]
Output: [[1, 3, 4, 2], [1, 3], [1]]
Explanation: Let’s break it down step by step. First, notice that the input array contains some duplicate numbers: 1 appears three times, and 3 appears twice. Since no row in the 2D array can contain duplicates, these repeated numbers must be placed in different rows.
- Start with the first row. Add 1, 3, 4, and 2 because all these numbers are distinct. Now the remaining numbers are 1, 3, and 1.
- In the second row, include another 1 and 3. At this point, only one 1 remains.
- In the third row, place the last 1.
The final 2D array is [[1, 3, 4, 2], [1, 3], [1]]. Each row contains distinct values, and all numbers from the input are used. Additionally, the number of rows (3) is minimized, satisfying the problem's conditions.
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= nums.length
"The goal here is to efficiently distribute numbers into rows while ensuring each row contains distinct values. We need to minimize the number of rows while handling repeated numbers by placing them in separate rows, ensuring no duplicates within a row. Let's explore how we can achieve this efficiently!"
Brute Force Approach:
Intuition
To solve the problem of converting a 1D array into a 2D array while meeting the given conditions, let’s first consider the simplest and most straightforward approach. Imagine we don’t prioritize efficiency and focus only on ensuring the rules are followed.
We can process the array element by element. For each number, we check if it can fit into an existing row without creating duplicates. If it can, we place it there; otherwise, we create a new row and add the number to it. This way, we handle each number individually and ensure no duplicates are present within any row.
This approach guarantees a valid solution since we carefully place numbers while adhering to the rules. However, the downside is that checking all rows for every number could be slow, especially for larger arrays, as we may repeatedly scan rows to find a suitable position. While inefficient, this method helps us understand the problem and lays the groundwork for more optimized solutions.
While inefficient, this method helps us understand how to convert an array into a 2D array with conditions and lays the groundwork for more optimized solutions.
Approach:
Step 1: Initialize Data Structures
We start by creating an output data structure, a list of lists (the 2D array), which will store the rows of the resulting array. This structure will be built row by row as we process the input array nums. Each row will ensure it contains only distinct elements.
Step 2: Iterate Through the Input Array
Next, we traverse the input array nums one element at a time. For each number, we try to place it into an existing row in the output array. Starting from the first row, we check each row to see if the current number is already present. If it is not, we add it to that row.
Step 3: Create New Rows When Necessary
If no existing row can accommodate the current number (i.e., the number is already present in all rows), we create a new row and add the number to it. This guarantees that every element in the input array is used while adhering to the condition that no row contains duplicates.
Step 4: Continue Until All Numbers Are Processed
We repeat the above steps for all elements in the input array, ensuring every number is placed in a valid position. As we process, rows may have varying lengths based on how the numbers are distributed.
Step 5: Return the Resulting 2D Array
After processing all elements in the input array, the constructed 2D array contains all the numbers from the input, distributed across rows with no duplicates. This array is returned as the final result. While this approach ensures correctness, it involves checking all rows for each number, which can make it inefficient for larger inputs. However, this method provides a foundational understanding of how to convert an array into a 2D array with conditions, helping us refine and optimize the solution further.
Let us understand this with a video,
Convert an Array Into a 2D Array With Conditions Problem-Brute-Force-Approach
Dry Run
InitializationWe start with an empty output structure result which will hold the rows of our 2D array.Initial State:result = []Step-by-Step ExecutionProcessing the first number (1):
- 1 is not present in any row (since result is empty).
- Create a new row and add 1 to it.
State:result = [[1]]Processing the second number (3):
- 3 is not in the first row ([1]).
- Add 3 to the first row.
State:result = [[1, 3]]Processing the third number (4):
- 4 is not in the first row ([1, 3]).
- Add 4 to the first row.
State:result = [[1, 3, 4]]Processing the fourth number (1):
- 1 is already in the first row ([1, 3, 4]).
- Create a new row and add 1 to it.
State:result = [[1, 3, 4], [1]]Processing the fifth number (2):
- 2 is not in the first row ([1, 3, 4]).
- Add 2 to the first row.
State:result = [[1, 3, 4, 2], [1]]Processing the sixth number (3):
- 3 is already in the first row ([1, 3, 4, 2]).
- 3 is not in the second row ([1]).
- Add 3 to the second row.
State:result = [[1, 3, 4, 2], [1, 3]]Processing the seventh number (1):
- 1 is already in the first row ([1, 3, 4, 2]).
- 1 is already in the second row ([1, 3]).
- Create a new row and add 1 to it.
State:result = [[1, 3, 4, 2], [1, 3], [1]]Final OutputAfter processing all numbers, the resulting 2D array is:result = [[1, 3, 4, 2], [1, 3], [1]]Explanation of the Result
- The first row ([1, 3, 4, 2]) contains all distinct numbers and uses as many numbers as possible before duplicates force new rows.
- The second row ([1, 3]) accommodates duplicates (1 and 3) from the input list that couldn’t fit into the first row.
- The third row ([1]) handles the final occurrence of 1.
Code for All Languages
C++ - Convert an Array Into a 2D Array With Conditions solution - Brute force
//Convert an Array Into a 2D Array With Conditions solution in cpp
vector<vector<int>> findMatrix(vector<int>& nums) {
// Initialize an empty 2D vector to store rows
vector<vector<int>> result;
// Iterate through each number in the input array
for (int num : nums) {
bool placed = false; // Flag to check if the number is placed in any row
// Check each existing row in the result
for (auto& row : result) {
// Create a set from the row for quick duplicate checking
unordered_set<int> rowSet(row.begin(), row.end());
if (rowSet.find(num) == rowSet.end()) { // If num is not in the row
row.push_back(num); // Add num to the row
placed = true; // Mark as placed
break; // Stop checking other rows
}
}
// If the number couldn't be placed in any existing row
if (!placed) {
result.push_back({num}); // Create a new row with this number
}
}
return result; // Return the final 2D array
}Java - Convert an Array Into a 2D Array With Conditions solution - Brute force
//Convert an Array Into a 2D Array With Conditions solution in java
public List<List<Integer>> findMatrix(List<Integer> nums) {
// Initialize an empty list to store rows
List<List<Integer>> result = new ArrayList<>();
// Iterate through each number in the input list
for (int num : nums) {
boolean placed = false; // Flag to check if the number is placed in any row
// Check each existing row in the result
for (List<Integer> row : result) {
// Create a set from the row for quick duplicate checking
Set<Integer> rowSet = new HashSet<>(row);
if (!rowSet.contains(num)) { // If num is not in the row
row.add(num); // Add num to the row
placed = true; // Mark as placed
break; // Stop checking other rows
}
}
// If the number couldn't be placed in any existing row
if (!placed) {
List<Integer> newRow = new ArrayList<>();
newRow.add(num);
result.add(newRow); // Create a new row with this number
}
}
return result; // Return the final 2D list
}Python - Convert an Array Into a 2D Array With Conditions solution - Brute force
#Convert an Array Into a 2D Array With Conditions solution in python
def findMatrix(self, nums):
# Initialize an empty list to store rows
result = []
# Iterate through each number in the input array
for num in nums:
placed = False # Flag to check if the number is placed in any row
# Check each existing row in the result
for row in result:
# Create a set from the row for quick duplicate checking
row_set = set(row)
if num not in row_set: # If num is not in the row
row.append(num) # Add num to the row
placed = True # Mark as placed
break # Stop checking other rows
# If the number couldn't be placed in any existing row
if not placed:
result.append([num]) # Create a new row with this number
return result # Return the final 2D arrayJavaScript - Convert an Array Into a 2D Array With Conditions solution - Brute force
//Convert an Array Into a 2D Array With Conditions solution in javaScript
// Function to find the matrix
function findMatrix(nums) {
const result = [];
for (const num of nums) {
let placed = false;
// Check each row
for (const row of result) {
if (!row.includes(num)) {
row.push(num);
placed = true;
break;
}
}
if (!placed) {
result.push([num]);
}
}
return result;
}Time Complexity: O (n^2)
Input Array Traversal
We iterate through the input array nums of size n, processing each number once. This traversal contributes O(n).
Row Placement
For each number in nums, we check each row in the 2D array to see if it can fit. In the worst case, we may check all rows. If the number of rows is r, this step contributes O(r * n), where r is the number of rows in the final result.
Overall Time Complexity
The total time complexity is O(r * n). In the worst case, when every number in nums is distinct, the number of rows r equals n. This makes the complexity O(n²) in the worst case.
Space Complexity: O(n)
Storage for the Result Array
The 2D array result stores all the numbers from nums. In the worst case, where each number forms its own row, we need O(n) space for storing all rows.
Auxiliary Space
We use additional variables like flags and iterators for processing, but these consume negligible space compared to the primary storage.
Overall Space Complexity
The total space complexity is O(n), dominated by the storage required for the 2D result array.
In the brute force approach, we check every row for each number to see where it can fit, which leads to a lot of unnecessary work. The optimized approach makes this simpler by directly tracking where each number belongs while processing. Instead of scanning all rows repeatedly, we handle placement more efficiently as we go, making the process quicker and easier to follow without changing the core idea. This refinement significantly improves the way we convert an array into a 2D array with conditions, ensuring both correctness and efficiency.
Optimized Approach:
Intuition
Let’s think about how we can make the process smoother. In the brute force approach, we repeatedly check all rows to find where a number can fit, even if it’s obvious that duplicates are forcing us to create new rows. This repeated scanning wastes time. What if we could directly track how many rows a number needs and place it without all those extra checks?
Here’s the idea: as we go through the input array, we can count how many times each number appears. This tells us upfront how many rows that number will need. For example, if 1 appears three times, we know it will need three separate rows. With this information, we can build the rows dynamically by simply placing each occurrence of the number into its required row.
By focusing on grouping duplicates intelligently as we process the array, we eliminate the need for constant row checking and make the entire process much faster and more organized. It’s like assigning numbers to their rows directly, instead of hunting for a place to fit them every time.
Approach
Step 1: Initialize Data Structures
We start by creating a frequency hash table to count how many times each number appears in the input array. This hash table will help us determine upfront how many rows each number needs in the final 2D array. Additionally, we initialize an empty list result to hold the rows of the 2D array.
Step 2: Populate Rows Dynamically
Next, we traverse through the frequency hash table. For each number and its count, we place the number in rows incrementally. If the number requires more rows than currently exist in the result, we add new rows as needed. For example, if 1 appears three times and we only have two rows, we create an additional row to accommodate it.
Step 3: Add Numbers to Rows
For each occurrence of a number, we place it in the next available row. This ensures that all rows remain valid with no duplicates. If a number needs three rows, its instances will be distributed across three separate rows, one in each.
Step 4: Build the Result
As we continue adding numbers to rows, the result list dynamically grows to accommodate all elements while ensuring that each row contains distinct values.
Step 5: Return the 2D Array
After processing all numbers in the frequency hash table, the result list contains the required 2D array. Each row is valid, all numbers are included, and the total number of rows is minimized. This is returned as the final output. This approach simplifies placement by working with counts directly, reducing unnecessary checks, and making the process more efficient. By leveraging this method, we effectively convert an array into a 2D array with conditions, ensuring both accuracy and optimization.
Let us understand this with a video,
Convert an Array Into a 2D Array With Conditions Problem-Optimal-Appraoch
Dry Run
Input:
nums = [1, 3, 4, 1, 2, 3, 1]
Step 1: Initialize Data Structures
- Create a frequency hash table to count occurrences of each number: frequency = {1: 3, 3: 2, 4: 1, 2: 1}
- Initialize an empty result list: result = []
Step 2: Populate Rows Dynamically
- Process number 1 with frequency 3:
- 1 needs 3 rows. Create new rows as needed:
- Add 1 to row 1 → result = [[1]]
- Add 1 to row 2 → result = [[1], [1]]
- Add 1 to row 3 → result = [[1], [1], [1]]
- Process number 3 with frequency 2:
- 3 needs 2 rows. Add 3 to the first 2 rows:
- Add 3 to row 1 → result = [[1, 3], [1], [1]]
- Add 3 to row 2 → result = [[1, 3], [1, 3], [1]]
- Process number 4 with frequency 1:
- 4 needs 1 row. Add 4 to row 1:
- Add 4 to row 1 → result = [[1, 3, 4], [1, 3], [1]]
- Process number 2 with frequency 1:
- x`2 needs 1 row. Add 2 to row 1:
Add 2 to row 1 → result = [[1, 3, 4, 2], [1, 3], [1]]
- x`2 needs 1 row. Add 2 to row 1:
Final Result
After processing all numbers, the final 2D array is: result = [[1, 3, 4, 2], [1, 3], [1]]
Code for All Languages
C++ - Convert an Array Into a 2D Array With Conditions solution - Optimized Approach
//Convert an Array Into a 2D Array With Conditions solution in c++
vector<vector<int>> findMatrix(vector<int>& nums) {
// Step 1: Initialize the result vector and tracking map
vector<vector<int>> result;
unordered_map<int, int> tracking;
// Step 2: Process each number in the input
for (int num : nums) {
// Get the count of how many times the number has been placed
int count = tracking[num];
// Ensure the row for this count exists
if (result.size() <= count) {
result.push_back(vector<int>());
}
// Place the number in the correct row
result[count].push_back(num);
// Update the tracking map
tracking[num] = count + 1;
}
// Step 3: Return the final 2D array
return result;
}Java - Convert an Array Into a 2D Array With Conditions solution - Optimized Approach
//Convert an Array Into a 2D Array With Conditions solution in java
public List<List<Integer>> findMatrix(List<Integer> nums) {
// Step 1: Initialize the result list and tracking map
List<List<Integer>> result = new ArrayList<>();
Map<Integer, Integer> tracking = new HashMap<>();
// Step 2: Process each number in the input
for (int num : nums) {
// Get the count of how many times the number has been placed
int count = tracking.getOrDefault(num, 0);
// Ensure the row for this count exists
if (result.size() <= count) {
result.add(new ArrayList<>());
}
// Place the number in the correct row
result.get(count).add(num);
// Update the tracking map
tracking.put(num, count + 1);
}
// Step 3: Return the final 2D array
return result;
}Python - Convert an Array Into a 2D Array With Conditions solution - Optimized Approach
#Convert an Array Into a 2D Array With Conditions solution in python
def findMatrix(self, nums):
# Step 1: Initialize the result list and tracking dictionary
result = []
tracking = defaultdict(int)
# Step 2: Process each number in the input
for num in nums:
# Get the count of how many times the number has been placed
count = tracking[num]
# Ensure the row for this count exists
if len(result) <= count:
result.append([])
# Place the number in the correct row
result[count].append(num)
# Update the tracking dictionary
tracking[num] = count + 1
# Step 3: Return the final 2D array
return result
JavaScript - Convert an Array Into a 2D Array With Conditions solution - Optimized Approach
//Convert an Array Into a 2D Array With Conditions solution in javaScript
function findMatrix(nums) {
// Step 1: Initialize the result array and tracking object
let result = [];
let tracking = {};
// Step 2: Process each number in the input
for (let num of nums) {
// Get the count of how many times the number has been placed
let count = tracking[num] || 0;
// Ensure the row for this count exists
if (result.length <= count) {
result.push([]);
}
// Place the number in the correct row
result[count].push(num);
// Update the tracking object
tracking[num] = count + 1;
}
// Step 3: Return the final 2D array
return result;
}Complexity Analysis of the problem
Time Complexity: O(n)
Frequency hash table Construction
We traverse the input array nums of size n once to build the frequency hash table. This operation takes O(n).
Row Placement
For each unique number in the frequency hash table, we distribute its occurrences into rows. If there are u unique numbers and each number has a frequency f, placing the numbers into rows takes a total of O(n) (since each number is processed exactly as many times as it appears in nums).
Overall Time Complexity
The total time complexity is O(n), as we process the input array and handle row placements efficiently.
Space Complexity: O(n)
Storage for the Frequency hash table
The frequency hash table requires space proportional to the number of unique numbers in nums. In the worst case, where all numbers are distinct, this takes O(u), where u is the number of unique numbers.
Storage for the Result Array
The result array stores all elements from nums. In the worst case, where each number forms its own row, this requires O(n) space.
Auxiliary Space
Additional space is used for iterators and variables, but this is negligible compared to the primary data structures.
Overall Space Complexity
The total space complexity is O(n), dominated by the storage for the result array and the frequency hash table.
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems.
Find the element that appears more than (n/2) times in the array.
Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order