# Assign Elements to Groups with Constraints
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/assign-elements-to-groups-with-constraints)
Canonical: https://scaleengineer.com/dsa/problems/assign-elements-to-groups-with-constraints
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute Force Iteration
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.
**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).
**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.
### Explanation
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:
```java
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;
    }
}
```
### Algorithm
*   Initialize an integer array `assigned` of the same size as `groups` and fill it with `-1`.
*   Iterate through each group `groups[i]` from `i = 0` to `n-1` (where `n` is the length of `groups`).
*   For each group, start a nested loop to iterate through each element `elements[j]` from `j = 0` to `m-1` (where `m` is the length of `elements`).
*   Inside the inner loop, check if `groups[i]` is divisible by `elements[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 `j` from `0` upwards. Set `assigned[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 `assigned` array.

## Pre-computation of Element Indices and Divisor Finding
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.
**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.
**Pros:** Significantly faster than the brute-force approach.; Reduces redundant searches by pre-processing the `elements` array.
**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.
### Explanation
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:
```java
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;
    }
}
```
### Algorithm
*   Create a hash map `elementToIndex` to store the first-occurrence index for each unique element value. Iterate through `elements` from right to left (`j = m-1` down to `0`) 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 `assigned` array of size `n`.
*   Iterate through each group `groups[i]` from `i = 0` to `n-1`.
*   For each group size `g = groups[i]`, find all of its divisors. A standard way to do this is to iterate from `d = 1` up to `sqrt(g)`.
*   Initialize a variable `bestIndex` to `-1` for the current group.
*   For each divisor `d` found, check if it exists as a key in `elementToIndex`. If it does, retrieve its index `j` and update `bestIndex = min(bestIndex, j)` (or just set `bestIndex = j` if `bestIndex` was -1).
*   Do the same for the corresponding divisor `g/d`.
*   After checking all divisors, `bestIndex` will hold the minimum index of a suitable element. Set `assigned[i] = bestIndex`.
*   Return the `assigned` array.

## Sieve-like Approach with Multiples Iteration
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.
**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)).
**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.
### Explanation
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:
```java
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;
    }
}
```
### Algorithm
*   Determine the maximum value `maxVal` present in `groups` and `elements`.
*   Create an array of lists, `groupIndicesBySize`, of size `maxVal + 1`. This will map a group size to a list of original indices.
*   Populate `groupIndicesBySize` by iterating through `groups`: for each `groups[i]`, add `i` to the list at `groupIndicesBySize[groups[i]]`.
*   Initialize an `assigned` array of size `n` with `-1`.
*   Create a boolean array `processedElements` of size `maxVal + 1` initialized to `false`. This will track which element values have been handled.
*   Iterate through `elements` from `j = 0` to `m-1`.
*   For each element `e = elements[j]`:
    *   If `processedElements[e]` is `true`, it means an earlier occurrence of this value has already been processed, so we `continue` to the next element.
    *   Mark `processedElements[e] = true`.
    *   Now, iterate through all multiples of `e` (i.e., `k = e, 2*e, 3*e, ...`) up to `maxVal`.
    *   For each multiple `k`, retrieve the list of group indices from `groupIndicesBySize[k]`.
    *   For each `groupIndex` in this list, if `assigned[groupIndex]` is still `-1`, set `assigned[groupIndex] = j`.
*   Return the `assigned` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```