3447. Assign Elements to Groups with Constraints 

Description

You are given an integer array groups, where groups[i] represents the size of the i^th 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 <= 10⁵
1 <= elements.length <= 10⁵
1 <= groups[i] <= 10⁵
1 <= elements[i] <= 10⁵

Solutions

Solution 1: Enumeration

First, we find the maximum value in the array $\textit{groups}$, denoted as $\textit{mx}$. We use an array $\textit{d}$ to record the index corresponding to each element. Initially, $\textit{d}[x] = -1$ indicates that the element $x$ has not been assigned yet.

Then, we traverse the array $\textit{elements}$. For each element $x$, if $x > \textit{mx}$ or $\textit{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 $\textit{d}[y]$ to $j$, indicating that the element $y$ is assigned to the index $j$.

Finally, we traverse the array $\textit{groups}$ and obtain the answer based on the records in the $\textit{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 $\textit{groups}$ and $\textit{elements}$, respectively, while $M$ is the maximum value in the array $\textit{groups}$.

Python3

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]

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

C++

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

Go

func assignElements(groups []int, elements []int) (ans []int) {
	mx := slices.Max(groups)
	d := make([]int, mx+1)
	for i := range d {
		d[i] = -1
	}
	for j, x := range elements {
		if x > mx || d[x] != -1 {
			continue
		}
		for y := x; y <= mx; y += x {
			if d[y] == -1 {
				d[y] = j
			}
		}
	}
	for _, x := range groups {
		ans = append(ans, d[x])
	}
	return
}

TypeScript

function assignElements(groups: number[], elements: number[]): number[] {
    const mx = Math.max(...groups);
    const d: number[] = Array(mx + 1).fill(-1);
    for (let j = 0; j < elements.length; ++j) {
        const x = elements[j];
        if (x > mx || d[x] !== -1) {
            continue;
        }
        for (let y = x; y <= mx; y += x) {
            if (d[y] === -1) {
                d[y] = j;
            }
        }
    }
    return groups.map(x => d[x]);
}