Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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:
j can be assigned to a group i if groups[i] is divisible by elements[j].j.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.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.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 <= 1051 <= elements.length <= 1051 <= groups[i] <= 1051 <= elements[i] <= 105Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map
[8,4,3,2,4] [4,2]
[2,3,5,7] [5,3,3]
[10,21,30,41] [2,1]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3447: Assign Elements to Groups with Constraints
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;
}
}
// Accepted solution for LeetCode #3447: Assign Elements to Groups with Constraints
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
}
# Accepted solution for LeetCode #3447: Assign Elements to Groups with Constraints
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]
// Accepted solution for LeetCode #3447: Assign Elements to Groups with Constraints
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3447: Assign Elements to Groups with Constraints
// 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;
// }
// }
// Accepted solution for LeetCode #3447: Assign Elements to Groups with Constraints
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]);
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.