Skip to main content
Talentd

Assign Elements to Groups with Constraints - Solution & Explanation

MediumArrayHash Table9 min readAsked at: Bcg
Practice this problem

Problem Statement

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 j can be assigned to a group i if groups[i] is divisible by elements[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] = 4 is assigned to groups 0, 1, and 4.
  • elements[1] = 2 is 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] = 3 is assigned to group 1.
  • elements[0] = 5 is 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 <= 105
  • 1 <= elements.length <= 105
  • 1 <= groups[i] <= 105
  • 1 <= elements[i] <= 105

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n * m)O(1)Small input sizes or when implementing the most direct interpretation of the problem
Enumeration with Hash TableO(n + m) averageO(m)General case when repeated constraint checks can be replaced with constant-time lookups

Video Solution

3447. Assign Elements to Groups with Constraints | Factors & Divisors | HashMap • Aryan Mittal • 2,545 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Assign Elements to Groups with Constraints easy or hard?
Assign Elements to Groups with Constraints is rated Medium difficulty. The brute-force logic is simple, but optimizing it requires recognizing repeated constraint checks and applying a hash table to avoid nested loops.
Assign Elements to Groups with Constraints Python/Java solution
A typical Python or Java solution iterates through groups and checks candidate elements using a dictionary or HashMap. The map stores elements by the constraint key so each group can quickly find a valid assignment. The optimized implementation runs in roughly O(n + m) time.
How to solve Assign Elements to Groups with Constraints in O(n)?
Achieving near O(n) performance requires preprocessing elements into a hash table. Each element is inserted once, and each group performs constant-time lookups to find a valid candidate instead of scanning the entire list. This removes the nested loop and reduces the total work to linear passes over the input.
What is the best approach for Assign Elements to Groups with Constraints?
The most effective approach uses enumeration combined with a hash table. Preprocess elements into a hash map keyed by the property used in the constraint, then iterate through groups and perform constant-time lookups. This reduces repeated scanning and typically runs in O(n + m) time with O(m) extra space.
Is Assign Elements to Groups with Constraints asked at Google/Amazon/Meta?
Problems involving constrained assignment, hashing, and array processing frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this question test your ability to reduce brute-force enumeration using hash maps or other indexing structures.
What data structure is used in Assign Elements to Groups with Constraints?
Arrays store the groups and elements, while a hash table is typically used to index elements by the attribute used in the constraint. The hash map allows constant-time lookups, which eliminates repeated scanning across the elements array.
What is the time complexity of Assign Elements to Groups with Constraints?
The brute force solution runs in O(n * m) time because each group may scan all elements. With a hash table optimization that indexes elements by the relevant constraint property, the complexity improves to about O(n + m) on average with O(m) auxiliary space.

Ready to solve this problem?

Practice Assign Elements to Groups with Constraints with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays