You are given an integer array groups, where groups[i] represents the size of the ith group. You are also given an integer array elements.
Your task is to assign one element to each group based on the following rules:
j can be assigned to a group i if groups[i] is divisible by elements[j].j.Return an integer array assigned, where assigned[i] is the index of the element chosen for group i, or -1 if no suitable element exists.
Note: An element may be assigned to more than one group.
Example 1:
Input: groups = [8,4,3,2,4], elements = [4,2]
Output: [0,0,-1,1,0]
Explanation:
elements[0] = 4 is assigned to groups 0, 1, and 4.elements[1] = 2 is assigned to group 3.Example 2:
Input: groups = [2,3,5,7], elements = [5,3,3]
Output: [-1,1,0,-1]
Explanation:
elements[1] = 3 is assigned to group 1.elements[0] = 5 is assigned to group 2.Example 3:
Input: groups = [10,21,30,41], elements = [2,1]
Output: [0,1,0,1]
Explanation:
elements[0] = 2 is assigned to the groups with even values, and elements[1] = 1 is assigned to the groups with odd values.
Constraints:
1 <= groups.length <= 1051 <= elements.length <= 1051 <= groups[i] <= 1051 <= elements[i] <= 105Problem Overview: You are given groups and a set of elements. Each element can only be assigned to a group if it satisfies a specific constraint defined by the problem. The goal is to determine a valid assignment for each group while respecting these constraints and element availability.
Approach 1: Brute Force Enumeration (O(n * m) time, O(1) space)
The most direct method is to check every group against every element. Iterate through the groups array and, for each group, scan the entire elements list to find one that satisfies the constraint. Once a valid element is found, assign it and mark it as used. This approach relies purely on array traversal and explicit constraint checking.
This method is straightforward and mirrors the problem statement exactly. However, the repeated scans create a quadratic pattern when both arrays grow large. It works well when input sizes are small or when constraints are simple enough that the first few checks succeed quickly.
Approach 2: Enumeration with Hash Table Optimization (O(n + m) average time, O(m) space)
A more efficient solution reduces repeated scanning by pre-processing the elements. Store useful information about elements in a hash table so that each group can quickly determine whether a valid element exists. Instead of iterating through every candidate, perform constant-time lookups using a key derived from the constraint.
The key insight is that constraint checks often repeat across groups. By indexing elements by their relevant property (value, category, or requirement), you avoid redundant comparisons. Each group performs a lookup or small set of lookups to find an eligible element, then marks it as used or removes it from the map.
This pattern keeps the algorithm linear in practice. You process elements once during preprocessing and then iterate through groups while performing O(1) lookups. The additional memory cost comes from maintaining the hash table, but the speed improvement is significant for large inputs.
Recommended for interviews: Start with the brute-force enumeration to show you understand the assignment logic. Then optimize using a hash map that indexes elements by the property used in the constraint. Interviewers typically expect the hash table version because it demonstrates awareness of repeated work and the ability to convert nested loops into constant-time lookups.
First, we find the maximum value in the array groups, denoted as mx. We use an array d to record the index corresponding to each element. Initially, d[x] = -1 indicates that the element x has not been assigned yet.
Then, we traverse the array elements. For each element x, if x > mx or d[x] neq -1, it means that the element x cannot be assigned or has already been assigned, so we skip it directly. Otherwise, starting from x, we increment by x each time and set d[y] to j, indicating that the element y is assigned to the index j.
Finally, we traverse the array groups and obtain the answer based on the records in the d array.
The time complexity is O(M times log m + n), and the space complexity is O(M). Here, n and m are the lengths of the arrays groups and elements, respectively, while M is the maximum value in the array groups.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * m) | O(1) | Small input sizes or when implementing the most direct interpretation of the problem |
| Enumeration with Hash Table | O(n + m) average | O(m) | General case when repeated constraint checks can be replaced with constant-time lookups |
3447. Assign Elements to Groups with Constraints | Factors & Divisors | HashMap • Aryan Mittal • 2,511 views views
Watch 8 more video solutions →Practice Assign Elements to Groups with Constraints with our built-in code editor and test cases.
Practice on FleetCode