Skip to content

3447. Assign Elements to Groups with Constraints 👍

  • Time: O(nn)O(n\sqrt{n})
  • Space: O(n)O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
    vector<int> ans;
    unordered_map<int, int> elementToMinIndex;

    for (int i = 0; i < elements.size(); ++i)
      if (!elementToMinIndex.contains(elements[i]))
        elementToMinIndex[elements[i]] = i;

    for (const int num : groups)
      ans.push_back(getMinIndex(num, elementToMinIndex));

    return ans;
  }

 private:
  int getMinIndex(int num, const unordered_map<int, int>& elementToMinIndex) {
    int res = INT_MAX;
    for (int i = 1; i * i <= num; ++i) {
      if (num % i != 0)
        continue;
      if (elementToMinIndex.contains(i))
        res = min(res, elementToMinIndex.at(i));
      if (num / i != i && elementToMinIndex.contains(num / i))
        res = min(res, elementToMinIndex.at(num / i));
    }
    return res == INT_MAX ? -1 : res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int[] assignElements(int[] groups, int[] elements) {
    int[] ans = new int[groups.length];
    Map<Integer, Integer> elementToMinIndex = new HashMap<>();

    for (int i = 0; i < elements.length; ++i)
      elementToMinIndex.putIfAbsent(elements[i], i);

    for (int i = 0; i < groups.length; ++i)
      ans[i] = getMinIndex(groups[i], elementToMinIndex);

    return ans;
  }

  private int getMinIndex(int num, Map<Integer, Integer> elementToMinIndex) {
    int res = Integer.MAX_VALUE;
    for (int i = 1; i * i <= num; ++i) {
      if (num % i != 0)
        continue;
      if (elementToMinIndex.containsKey(i))
        res = Math.min(res, elementToMinIndex.get(i));
      if (num / i != i && elementToMinIndex.containsKey(num / i))
        res = Math.min(res, elementToMinIndex.get(num / i));
    }
    return res == Integer.MAX_VALUE ? -1 : res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def assignElements(self, groups: list[int], elements: list[int]) -> list[int]:
    ans = []
    elementToMinIndex = {}

    for i, element in enumerate(elements):
      if element not in elementToMinIndex:
        elementToMinIndex[element] = i

    for num in groups:
      ans.append(self._getMinIndex(num, elementToMinIndex))

    return ans

  def _getMinIndex(self, num: int, elementToMinIndex: dict[int, int]) -> int:
    res = math.inf
    i = 1
    while i * i <= num:
      if num % i != 0:
        continue
      if i in elementToMinIndex:
        res = min(res, elementToMinIndex[i])
      if num // i != i and (num // i) in elementToMinIndex:
        res = min(res, elementToMinIndex[num // i])
      i += 1
    return -1 if res == math.inf else res
Was this page helpful?