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 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}\).

Python3JavaC++GoTypeScript

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]

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

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
}

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

3447. Assign Elements to Groups with Constraints

Description

Solutions

Solution 1: Enumeration

Comments