Assign Elements to Groups with Constraints
Source: leetcode
Difficulty: Medium
Tags: array, hash-table

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`




C++ solution:
class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        const int MAX_ELEMENT = 100000;
        vector<int> element_indices(MAX_ELEMENT + 1, -1);
        for (int i = 0; i < elements.size(); ++i) {
            int e = elements[i];
            if (element_indices[e] == -1) {
                element_indices[e] = i;
            }
        }
        
        vector<int> assigned;
        for (int g : groups) {
            int min_idx = -1;
            unordered_set<int> divisors;
            for (int i = 1; i * i <= g; ++i) {
                if (g % i == 0) {
                    divisors.insert(i);
                    divisors.insert(g / i);
                }
            }
            for (int d : divisors) {
                int idx = element_indices[d];
                if (idx != -1) {
                    if (min_idx == -1 || idx < min_idx) {
                        min_idx = idx;
                    }
                }
            }
            assigned.push_back(min_idx);
        }
        return assigned;
    }
};

Go solution:
func assignElements(groups []int, elements []int) []int {
    elementIndices := make(map[int]int)
    for idx, val := range elements {
        if _, exists := elementIndices[val]; !exists {
            elementIndices[val] = idx
        }
    }
    
    assigned := make([]int, len(groups))
    for i, g := range groups {
        minIndex := -1
        divisors := make(map[int]struct{})
        for d := 1; d*d <= g; d++ {
            if g%d == 0 {
                divisors[d] = struct{}{}
                divisors[g/d] = struct{}{}
            }
        }
        for d := range divisors {
            if idx, ok := elementIndices[d]; ok {
                if minIndex == -1 || idx < minIndex {
                    minIndex = idx
                }
            }
        }
        assigned[i] = minIndex
    }
    return assigned
}

Java solution:
class Solution {
    public int[] assignElements(int[] groups, int[] elements) {
        Map<Integer, Integer> elementMap = new HashMap<>();
        for (int j = 0; j < elements.length; j++) {
            int elem = elements[j];
            if (!elementMap.containsKey(elem)) {
                elementMap.put(elem, j);
            }
        }

        int[] assigned = new int[groups.length];
        Set<Integer> divisors = new HashSet<>();

        for (int i = 0; i < groups.length; i++) {
            int g = groups[i];
            divisors.clear();
            for (int j = 1; j * j <= g; j++) {
                if (g % j == 0) {
                    divisors.add(j);
                    divisors.add(g / j);
                }
            }
            int minIndex = Integer.MAX_VALUE;
            for (int d : divisors) {
                if (elementMap.containsKey(d)) {
                    int idx = elementMap.get(d);
                    if (idx < minIndex) {
                        minIndex = idx;
                    }
                }
            }
            assigned[i] = (minIndex != Integer.MAX_VALUE) ? minIndex : -1;
        }

        return assigned;
    }
}

JavaScript solution:
var assignElements = function(groups, elements) {
    const elementMap = {};
    for (let j = 0; j < elements.length; j++) {
        const val = elements[j];
        if (!(val in elementMap)) {
            elementMap[val] = j;
        }
    }

    const assigned = [];
    for (const g of groups) {
        const divisors = new Set();
        for (let i = 1; i * i <= g; i++) {
            if (g % i === 0) {
                divisors.add(i);
                divisors.add(g / i);
            }
        }
        let minIndex = Infinity;
        for (const d of divisors) {
            if (elementMap.hasOwnProperty(d)) {
                if (elementMap[d] < minIndex) {
                    minIndex = elementMap[d];
                }
            }
        }
        assigned.push(minIndex === Infinity ? -1 : minIndex);
    }
    return assigned;
};

Python solution:
class Solution:
    def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
        element_map = {}
        for idx, val in enumerate(elements):
            if val not in element_map:
                element_map[val] = idx
        
        assigned = []
        for g in groups:
            divisors = set()
            for i in range(1, int(math.isqrt(g)) + 1):
                if g % i == 0:
                    divisors.add(i)
                    divisors.add(g // i)
            candidates = []
            for d in divisors:
                if d in element_map:
                    candidates.append(element_map[d])
            if candidates:
                assigned.append(min(candidates))
            else:
                assigned.append(-1)
        return assigned

Ruby solution:
def assign_elements(groups, elements)
  element_indices = Array.new(100001)
  elements.each_with_index { |val, idx| element_indices[val] ||= idx }
  max_group = groups.max
  candidate = Array.new(max_group + 1)
  (1..max_group).each do |d|
    next if element_indices[d].nil?
    d.step(max_group, d) do |m|
      candidate[m] = candidate[m].nil? ? element_indices[d] : [candidate[m], element_indices[d]].min
    end
  end
  groups.map { |g| candidate[g].nil? ? -1 : candidate[g] }
end