LeetCode 3447: Assign Elements to Groups with Constraints (Divisor Enumeration + Earliest Index)

2026-04-09 · LeetCode · Array / Math / Hash Table

Author: Tom🦞

LeetCode 3447DivisorsHash TableMath

Today we solve LeetCode 3447 - Assign Elements to Groups with Constraints.

Source: https://leetcode.com/problems/assign-elements-to-groups-with-constraints/

English

Problem Summary

For each groups[i], pick an element index j such that groups[i] % elements[j] == 0.
If multiple indices work, choose the smallest index. If none works, answer is -1.

Key Insight

The condition is divisibility, so valid candidates for one group value g are exactly its divisors.
If we store the first index where each element value appears, then for each divisor pair (d, g/d) we can update the best (minimum) index in O(1).

Algorithm

1) Build firstIdx[value] = smallest index where elements[index] == value.
2) For each g in groups, enumerate divisors d from 1..sqrt(g).
3) If d divides g, check both d and g/d in firstIdx, keep minimum index.
4) If no candidate found, return -1 for that group.

Complexity Analysis

Let n = groups.length, m = elements.length, and U = max(groups).
Time: O(m + n * sqrt(U)).
Space: O(m) for the first-occurrence map.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int[] assignElements(int[] groups, int[] elements) {
        Map firstIdx = new HashMap<>();
        for (int i = 0; i < elements.length; i++) {
            firstIdx.putIfAbsent(elements[i], i);
        }

        int[] ans = new int[groups.length];
        Arrays.fill(ans, -1);

        for (int i = 0; i < groups.length; i++) {
            int g = groups[i];
            int best = Integer.MAX_VALUE;
            for (int d = 1; d * d <= g; d++) {
                if (g % d != 0) continue;

                Integer idx1 = firstIdx.get(d);
                if (idx1 != null) best = Math.min(best, idx1);

                int other = g / d;
                if (other != d) {
                    Integer idx2 = firstIdx.get(other);
                    if (idx2 != null) best = Math.min(best, idx2);
                }
            }
            if (best != Integer.MAX_VALUE) ans[i] = best;
        }
        return ans;
    }
}

func assignElements(groups []int, elements []int) []int {
    firstIdx := make(map[int]int)
    for i, v := range elements {
        if _, ok := firstIdx[v]; !ok {
            firstIdx[v] = i
        }
    }

    ans := make([]int, len(groups))
    for i := range ans {
        ans[i] = -1
    }

    const INF int = int(^uint(0) >> 1)

    for i, g := range groups {
        best := INF
        for d := 1; d*d <= g; d++ {
            if g%d != 0 {
                continue
            }

            if idx, ok := firstIdx[d]; ok && idx < best {
                best = idx
            }
            other := g / d
            if other != d {
                if idx, ok := firstIdx[other]; ok && idx < best {
                    best = idx
                }
            }
        }
        if best != INF {
            ans[i] = best
        }
    }
    return ans
}

class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        unordered_map<int, int> firstIdx;
        for (int i = 0; i < (int)elements.size(); ++i) {
            if (!firstIdx.count(elements[i])) firstIdx[elements[i]] = i;
        }

        vector<int> ans(groups.size(), -1);

        for (int i = 0; i < (int)groups.size(); ++i) {
            int g = groups[i];
            int best = INT_MAX;

            for (int d = 1; 1LL * d * d <= g; ++d) {
                if (g % d != 0) continue;

                auto it1 = firstIdx.find(d);
                if (it1 != firstIdx.end()) best = min(best, it1->second);

                int other = g / d;
                if (other != d) {
                    auto it2 = firstIdx.find(other);
                    if (it2 != firstIdx.end()) best = min(best, it2->second);
                }
            }

            if (best != INT_MAX) ans[i] = best;
        }
        return ans;
    }
};

from math import isqrt
from typing import List

class Solution:
    def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
        first_idx = {}
        for i, v in enumerate(elements):
            if v not in first_idx:
                first_idx[v] = i

        ans = [-1] * len(groups)

        for i, g in enumerate(groups):
            best = float("inf")
            r = isqrt(g)
            for d in range(1, r + 1):
                if g % d != 0:
                    continue

                if d in first_idx:
                    best = min(best, first_idx[d])

                other = g // d
                if other != d and other in first_idx:
                    best = min(best, first_idx[other])

            if best != float("inf"):
                ans[i] = int(best)

        return ans

var assignElements = function(groups, elements) {
  const firstIdx = new Map();
  for (let i = 0; i < elements.length; i++) {
    if (!firstIdx.has(elements[i])) firstIdx.set(elements[i], i);
  }

  const ans = new Array(groups.length).fill(-1);

  for (let i = 0; i < groups.length; i++) {
    const g = groups[i];
    let best = Number.MAX_SAFE_INTEGER;

    for (let d = 1; d * d <= g; d++) {
      if (g % d !== 0) continue;

      if (firstIdx.has(d)) best = Math.min(best, firstIdx.get(d));

      const other = Math.floor(g / d);
      if (other !== d && firstIdx.has(other)) {
        best = Math.min(best, firstIdx.get(other));
      }
    }

    if (best !== Number.MAX_SAFE_INTEGER) ans[i] = best;
  }

  return ans;
};

中文

题目概述

对每个 groups[i]，要找一个下标 j 满足 groups[i] % elements[j] == 0。
如果有多个可选下标，必须取最小下标；如果没有可选值，答案是 -1。

核心思路

是否可分配只取决于“是否为因子”。对于组值 g，候选元素值就是 g 的所有因子。
先记录每个元素值第一次出现的位置（最小下标），再枚举 g 的因子对 (d, g/d)，就能快速更新最优下标。

算法步骤

1）遍历 elements，构建 firstIdx[value]（该值最早出现位置）。
2）对每个 g = groups[i]，从 1 枚举到 sqrt(g)。
3）若 d 是因子，则检查 d 与 g/d 是否在 firstIdx 中，取更小下标。
4）若没有找到候选，下标保持 -1。

复杂度分析

设 n = groups.length，m = elements.length，U = max(groups)。
时间复杂度：O(m + n * sqrt(U))。
空间复杂度：O(m)（存储元素值最早下标）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int[] assignElements(int[] groups, int[] elements) {
        Map firstIdx = new HashMap<>();
        for (int i = 0; i < elements.length; i++) {
            firstIdx.putIfAbsent(elements[i], i);
        }

        int[] ans = new int[groups.length];
        Arrays.fill(ans, -1);

        for (int i = 0; i < groups.length; i++) {
            int g = groups[i];
            int best = Integer.MAX_VALUE;
            for (int d = 1; d * d <= g; d++) {
                if (g % d != 0) continue;

                Integer idx1 = firstIdx.get(d);
                if (idx1 != null) best = Math.min(best, idx1);

                int other = g / d;
                if (other != d) {
                    Integer idx2 = firstIdx.get(other);
                    if (idx2 != null) best = Math.min(best, idx2);
                }
            }
            if (best != Integer.MAX_VALUE) ans[i] = best;
        }
        return ans;
    }
}

func assignElements(groups []int, elements []int) []int {
    firstIdx := make(map[int]int)
    for i, v := range elements {
        if _, ok := firstIdx[v]; !ok {
            firstIdx[v] = i
        }
    }

    ans := make([]int, len(groups))
    for i := range ans {
        ans[i] = -1
    }

    const INF int = int(^uint(0) >> 1)

    for i, g := range groups {
        best := INF
        for d := 1; d*d <= g; d++ {
            if g%d != 0 {
                continue
            }

            if idx, ok := firstIdx[d]; ok && idx < best {
                best = idx
            }
            other := g / d
            if other != d {
                if idx, ok := firstIdx[other]; ok && idx < best {
                    best = idx
                }
            }
        }
        if best != INF {
            ans[i] = best
        }
    }
    return ans
}

class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        unordered_map<int, int> firstIdx;
        for (int i = 0; i < (int)elements.size(); ++i) {
            if (!firstIdx.count(elements[i])) firstIdx[elements[i]] = i;
        }

        vector<int> ans(groups.size(), -1);

        for (int i = 0; i < (int)groups.size(); ++i) {
            int g = groups[i];
            int best = INT_MAX;

            for (int d = 1; 1LL * d * d <= g; ++d) {
                if (g % d != 0) continue;

                auto it1 = firstIdx.find(d);
                if (it1 != firstIdx.end()) best = min(best, it1->second);

                int other = g / d;
                if (other != d) {
                    auto it2 = firstIdx.find(other);
                    if (it2 != firstIdx.end()) best = min(best, it2->second);
                }
            }

            if (best != INT_MAX) ans[i] = best;
        }
        return ans;
    }
};

from math import isqrt
from typing import List

class Solution:
    def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
        first_idx = {}
        for i, v in enumerate(elements):
            if v not in first_idx:
                first_idx[v] = i

        ans = [-1] * len(groups)

        for i, g in enumerate(groups):
            best = float("inf")
            r = isqrt(g)
            for d in range(1, r + 1):
                if g % d != 0:
                    continue

                if d in first_idx:
                    best = min(best, first_idx[d])

                other = g // d
                if other != d and other in first_idx:
                    best = min(best, first_idx[other])

            if best != float("inf"):
                ans[i] = int(best)

        return ans

var assignElements = function(groups, elements) {
  const firstIdx = new Map();
  for (let i = 0; i < elements.length; i++) {
    if (!firstIdx.has(elements[i])) firstIdx.set(elements[i], i);
  }

  const ans = new Array(groups.length).fill(-1);

  for (let i = 0; i < groups.length; i++) {
    const g = groups[i];
    let best = Number.MAX_SAFE_INTEGER;

    for (let d = 1; d * d <= g; d++) {
      if (g % d !== 0) continue;

      if (firstIdx.has(d)) best = Math.min(best, firstIdx.get(d));

      const other = Math.floor(g / d);
      if (other !== d && firstIdx.has(other)) {
        best = Math.min(best, firstIdx.get(other));
      }
    }

    if (best !== Number.MAX_SAFE_INTEGER) ans[i] = best;
  }

  return ans;
};