Assign Elements to Groups with Constraints
MedPrompt
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:
- An element at index
jcan be assigned to a groupiifgroups[i]is divisible byelements[j]. - If there are multiple elements that can be assigned, assign the element with the smallest index
j. - If no element satisfies the condition for a group, assign -1 to that group.
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] = 4is assigned to groups 0, 1, and 4.elements[1] = 2is assigned to group 3.- Group 2 cannot be assigned any element.
Example 2:
Input: groups = [2,3,5,7], elements = [5,3,3]
Output: [-1,1,0,-1]
Explanation:
elements[1] = 3is assigned to group 1.elements[0] = 5is assigned to group 2.- Groups 0 and 3 cannot be assigned any element.
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is a direct and straightforward implementation based on the problem description. It iterates through each group and, for each one, performs a linear scan through the elements array to find the first element that satisfies the divisibility condition. The "smallest index" rule is naturally handled by searching elements from index 0 for every group.
Algorithm
- Initialize an integer array
assignedof the same size asgroupsand fill it with-1. - Iterate through each group
groups[i]fromi = 0ton-1(wherenis the length ofgroups). - For each group, start a nested loop to iterate through each element
elements[j]fromj = 0tom-1(wheremis the length ofelements). - Inside the inner loop, check if
groups[i]is divisible byelements[j]using the modulo operator (groups[i] % elements[j] == 0). - If it is divisible, this is the first suitable element found for the current group because we are iterating
jfrom0upwards. Setassigned[i] = j. - Break the inner loop immediately to move to the next group, as we have found the element with the smallest index.
- If the inner loop finishes without finding any suitable element,
assigned[i]will retain its initial value of-1. - After the outer loop completes, return the
assignedarray.
Walkthrough
The brute-force approach directly translates the problem statement into code. For each group, we iterate through the entire elements array from the beginning. The first element we find that divides the group's size is the one we are looking for, due to the "smallest index" requirement. If we search the entire elements array and find no such element, we assign -1.
Here is the Java implementation:
import java.util.Arrays; class Solution { public int[] assignElements(int[] groups, int[] elements) { int n = groups.length; int m = elements.length; int[] assigned = new int[n]; Arrays.fill(assigned, -1); // Initialize with -1 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (groups[i] % elements[j] == 0) { assigned[i] = j; break; // Found the element with the smallest index j } } } return assigned; }}Complexity
Time
O(N * M), where N is the length of `groups` and M is the length of `elements`. In the worst-case scenario, for each of the N groups, we might have to iterate through all M elements.
Space
O(N), where N is the length of the `groups` array. This space is used for the output array `assigned`. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space.
Cons
Extremely inefficient for large inputs due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms with typical constraints for this problem size.
This approach improves upon the brute-force method by optimizing the search for a suitable element. Instead of scanning the entire elements array for each group, we first pre-process elements to map each unique element value to its first index. Then, for each group, we find its divisors and look up these divisors in our pre-computed map to find the best possible assignment.
Algorithm
- Create a hash map
elementToIndexto store the first-occurrence index for each unique element value. Iterate throughelementsfrom right to left (j = m-1down to0) and put(elements[j], j)into the map. This ensures that if an element value appears multiple times, the map will store the smallest index. - Initialize an
assignedarray of sizen. - Iterate through each group
groups[i]fromi = 0ton-1. - For each group size
g = groups[i], find all of its divisors. A standard way to do this is to iterate fromd = 1up tosqrt(g). - Initialize a variable
bestIndexto-1for the current group. - For each divisor
dfound, check if it exists as a key inelementToIndex. If it does, retrieve its indexjand updatebestIndex = min(bestIndex, j)(or just setbestIndex = jifbestIndexwas -1). - Do the same for the corresponding divisor
g/d. - After checking all divisors,
bestIndexwill hold the minimum index of a suitable element. Setassigned[i] = bestIndex. - Return the
assignedarray.
Walkthrough
The core idea is to reduce the inner loop's complexity. By pre-computing the first-seen index of every number in elements, we can avoid re-scanning. For a given group size g, we only need to consider numbers that are divisors of g. We can generate all divisors of g efficiently (in O(sqrt(g)) time) and then, for each divisor, check our map to see if it exists in elements. We keep track of the minimum index found among all valid divisors.
Here is the Java implementation:
import java.util.*; class Solution { public int[] assignElements(int[] groups, int[] elements) { int n = groups.length; int m = elements.length; // Pre-process elements to find the first index of each value Map<Integer, Integer> elementToIndex = new HashMap<>(); for (int j = m - 1; j >= 0; j--) { elementToIndex.put(elements[j], j); } int[] assigned = new int[n]; for (int i = 0; i < n; i++) { int groupSize = groups[i]; int bestIndex = -1; // Find divisors of groupSize and check against the map for (int d = 1; d * d <= groupSize; d++) { if (groupSize % d == 0) { // Check divisor d if (elementToIndex.containsKey(d)) { int currentIndex = elementToIndex.get(d); if (bestIndex == -1 || currentIndex < bestIndex) { bestIndex = currentIndex; } } // Check divisor groupSize / d int otherDivisor = groupSize / d; if (d != otherDivisor && elementToIndex.containsKey(otherDivisor)) { int currentIndex = elementToIndex.get(otherDivisor); if (bestIndex == -1 || currentIndex < bestIndex) { bestIndex = currentIndex; } } } } assigned[i] = bestIndex; } return assigned; }}Complexity
Time
O(M + N * sqrt(max_g)), where N is `groups.length`, M is `elements.length`, and `max_g` is the maximum group size. The `O(M)` part is for populating the map. The `O(N * sqrt(max_g))` part is for iterating through N groups and finding divisors for each.
Space
O(M + N), where M is the length of `elements` and N is the length of `groups`. The space is for the `elementToIndex` map (which can store up to `min(M, max_element_value)` unique elements) and the `assigned` output array.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Reduces redundant searches by pre-processing the
elementsarray.
Cons
The time complexity depends on finding divisors, which can be slow if group sizes are large.
For the given constraints, this approach is likely to be on the edge of the time limit or may time out.
This highly efficient approach inverts the problem's logic. Instead of finding divisors for each group, we iterate through each unique element and assign it to all groups whose size is a multiple of that element. This is reminiscent of the Sieve of Eratosthenes prime-finding algorithm. By processing elements in their original order (j=0, 1, 2,...), we naturally satisfy the "smallest index" rule. Any group assigned an element elements[j] will not be reassigned later, as we only update groups that haven't been assigned yet.
Algorithm
- Determine the maximum value
maxValpresent ingroupsandelements. - Create an array of lists,
groupIndicesBySize, of sizemaxVal + 1. This will map a group size to a list of original indices. - Populate
groupIndicesBySizeby iterating throughgroups: for eachgroups[i], addito the list atgroupIndicesBySize[groups[i]]. - Initialize an
assignedarray of sizenwith-1. - Create a boolean array
processedElementsof sizemaxVal + 1initialized tofalse. This will track which element values have been handled. - Iterate through
elementsfromj = 0tom-1. - For each element
e = elements[j]:- If
processedElements[e]istrue, it means an earlier occurrence of this value has already been processed, so wecontinueto the next element. - Mark
processedElements[e] = true. - Now, iterate through all multiples of
e(i.e.,k = e, 2*e, 3*e, ...) up tomaxVal. - For each multiple
k, retrieve the list of group indices fromgroupIndicesBySize[k]. - For each
groupIndexin this list, ifassigned[groupIndex]is still-1, setassigned[groupIndex] = j.
- If
- Return the
assignedarray.
Walkthrough
The key to this method's efficiency is pre-computation and changing the perspective. First, we group the indices of the groups array by their size, allowing for O(1) access to all groups of a specific size. Then, we iterate through the elements array. For each unique element value e (encountered at its first-appearing index j), we iterate through all its multiples k. For each k, we find all groups of that size and assign them the index j, provided they haven't been assigned already. This avoids the costly divisor calculation for each group.
Here is the Java implementation:
import java.util.*; class Solution { public int[] assignElements(int[] groups, int[] elements) { int n = groups.length; int m = elements.length; int maxVal = 0; for (int g : groups) { maxVal = Math.max(maxVal, g); } for (int e : elements) { maxVal = Math.max(maxVal, e); } maxVal++; List<Integer>[] groupIndicesBySize = new ArrayList[maxVal]; for (int i = 0; i < maxVal; i++) { groupIndicesBySize[i] = new ArrayList<>(); } for (int i = 0; i < n; i++) { groupIndicesBySize[groups[i]].add(i); } int[] assigned = new int[n]; Arrays.fill(assigned, -1); boolean[] processedElements = new boolean[maxVal]; for (int j = 0; j < m; j++) { int e = elements[j]; if (e >= maxVal || processedElements[e]) { continue; } processedElements[e] = true; for (int k = e; k < maxVal; k += e) { if (!groupIndicesBySize[k].isEmpty()) { for (int groupIndex : groupIndicesBySize[k]) { if (assigned[groupIndex] == -1) { assigned[groupIndex] = j; } } } } } return assigned; }}Complexity
Time
O(N + M + V * log(V)), where N is `groups.length`, M is `elements.length`, and V is the maximum value. The `V * log(V)` term arises from the sum of `V/e` over all unique elements `e`, which is bounded by the harmonic series sum `V * H_V`.
Space
O(N + V), where N is `groups.length` and V is the maximum value in the input arrays. This space is used for `groupIndicesBySize` (O(N+V)), `processedElements` (O(V)), and the output array (O(N)).
Trade-offs
Pros
Most efficient approach for the given constraints.
The time complexity is near-linear, dominated by a harmonic series-like sum.
Cons
More complex to implement compared to the other approaches.
Uses more memory, proportional to the maximum value in the inputs, which could be an issue if the value range is much larger than the number of elements.
Solutions
Solution
class Solution {public int[] assignElements(int[] groups, int[] elements) { int mx = Arrays.stream(groups).max().getAsInt(); int[] d = new int[mx + 1]; Arrays.fill(d, -1); for (int j = 0; j < elements.length; ++j) { int x = elements[j]; if (x > mx || d[x] != -1) { continue; } for (int y = x; y <= mx; y += x) { if (d[y] == -1) { d[y] = j; } } } int n = groups.length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { ans[i] = d[groups[i]]; } return ans; }}class Solution {public: vector<int> assignElements(vector<int> &groups, vector<int> &elements) { int mx = ranges ::max(groups); vector<int> d(mx + 1, -1); for (int j = 0; j < elements.size(); ++j) { int x = elements[j]; if (x > mx || d[x] != -1) { continue; } for (int y = x; y <= mx; y += x) { if (d[y] == -1) { d[y] = j; } } } vector<int> ans(groups.size()); for (int i = 0; i < groups.size(); ++i) { ans[i] = d[groups[i]]; } return ans; }};class Solution: def assignElements(self, groups: List[int], elements: List[int]) -> List[int]: mx = max(groups) d = [- 1] * (mx + 1) for j, x in enumerate(elements): if x > mx or d[x] != - 1: continue for y in range(x, mx + 1, x): if d[y] == - 1: d[y] = j return [d[x] for x in groups]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.