Welcome to Subscribe On Youtube

3447. Assign Elements to Groups with Constraints

Description

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

Solutions

Solution 1: Enumeration

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

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

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

• Java
• C++
• Python
• Go
• TypeScript

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

• 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]
  
  

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

All Problems

All Solutions