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.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.
Return a sorted list of the items such that:
beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).Return any solution if there is more than one solution and return an empty list if there is no solution.
Example 1:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] Output: [6,3,4,1,5,2,0,7]
Example 2:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] Output: [] Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.
Constraints:
1 <= m <= n <= 3 * 104group.length == beforeItems.length == n-1 <= group[i] <= m - 10 <= beforeItems[i].length <= n - 10 <= beforeItems[i][j] <= n - 1i != beforeItems[i][j]beforeItems[i] does not contain duplicates elements.Problem summary: There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it. Return a sorted list of the items such that: The items that belong to the same group are next to each other in the sorted list. There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item). Return any solution if there is more than one solution and return an empty list if there is no solution.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Topological Sort
8 2 [-1,-1,1,0,0,1,0,-1] [[],[6],[5],[6],[3,6],[],[],[]]
8 2 [-1,-1,1,0,0,1,0,-1] [[],[6],[5],[6],[3],[],[4],[]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1203: Sort Items by Groups Respecting Dependencies
class Solution {
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
int idx = m;
List<Integer>[] groupItems = new List[n + m];
int[] itemDegree = new int[n];
int[] groupDegree = new int[n + m];
List<Integer>[] itemGraph = new List[n];
List<Integer>[] groupGraph = new List[n + m];
Arrays.setAll(groupItems, k -> new ArrayList<>());
Arrays.setAll(itemGraph, k -> new ArrayList<>());
Arrays.setAll(groupGraph, k -> new ArrayList<>());
for (int i = 0; i < n; ++i) {
if (group[i] == -1) {
group[i] = idx++;
}
groupItems[group[i]].add(i);
}
for (int i = 0; i < n; ++i) {
for (int j : beforeItems.get(i)) {
if (group[i] == group[j]) {
++itemDegree[i];
itemGraph[j].add(i);
} else {
++groupDegree[group[i]];
groupGraph[group[j]].add(group[i]);
}
}
}
List<Integer> items = new ArrayList<>();
for (int i = 0; i < n + m; ++i) {
items.add(i);
}
var groupOrder = topoSort(groupDegree, groupGraph, items);
if (groupOrder.isEmpty()) {
return new int[0];
}
List<Integer> ans = new ArrayList<>();
for (int gi : groupOrder) {
items = groupItems[gi];
var itemOrder = topoSort(itemDegree, itemGraph, items);
if (itemOrder.size() != items.size()) {
return new int[0];
}
ans.addAll(itemOrder);
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
private List<Integer> topoSort(int[] degree, List<Integer>[] graph, List<Integer> items) {
Deque<Integer> q = new ArrayDeque<>();
for (int i : items) {
if (degree[i] == 0) {
q.offer(i);
}
}
List<Integer> ans = new ArrayList<>();
while (!q.isEmpty()) {
int i = q.poll();
ans.add(i);
for (int j : graph[i]) {
if (--degree[j] == 0) {
q.offer(j);
}
}
}
return ans.size() == items.size() ? ans : List.of();
}
}
// Accepted solution for LeetCode #1203: Sort Items by Groups Respecting Dependencies
func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
idx := m
groupItems := make([][]int, n+m)
itemDegree := make([]int, n)
groupDegree := make([]int, n+m)
itemGraph := make([][]int, n)
groupGraph := make([][]int, n+m)
for i, g := range group {
if g == -1 {
group[i] = idx
idx++
}
groupItems[group[i]] = append(groupItems[group[i]], i)
}
for i, gi := range group {
for _, j := range beforeItems[i] {
gj := group[j]
if gi == gj {
itemDegree[i]++
itemGraph[j] = append(itemGraph[j], i)
} else {
groupDegree[gi]++
groupGraph[gj] = append(groupGraph[gj], gi)
}
}
}
items := make([]int, n+m)
for i := range items {
items[i] = i
}
topoSort := func(degree []int, graph [][]int, items []int) []int {
q := []int{}
for _, i := range items {
if degree[i] == 0 {
q = append(q, i)
}
}
ans := []int{}
for len(q) > 0 {
i := q[0]
q = q[1:]
ans = append(ans, i)
for _, j := range graph[i] {
degree[j]--
if degree[j] == 0 {
q = append(q, j)
}
}
}
return ans
}
groupOrder := topoSort(groupDegree, groupGraph, items)
if len(groupOrder) != len(items) {
return nil
}
ans := []int{}
for _, gi := range groupOrder {
items = groupItems[gi]
itemOrder := topoSort(itemDegree, itemGraph, items)
if len(items) != len(itemOrder) {
return nil
}
ans = append(ans, itemOrder...)
}
return ans
}
# Accepted solution for LeetCode #1203: Sort Items by Groups Respecting Dependencies
class Solution:
def sortItems(
self, n: int, m: int, group: List[int], beforeItems: List[List[int]]
) -> List[int]:
def topo_sort(degree, graph, items):
q = deque(i for _, i in enumerate(items) if degree[i] == 0)
res = []
while q:
i = q.popleft()
res.append(i)
for j in graph[i]:
degree[j] -= 1
if degree[j] == 0:
q.append(j)
return res if len(res) == len(items) else []
idx = m
group_items = [[] for _ in range(n + m)]
for i, g in enumerate(group):
if g == -1:
group[i] = idx
idx += 1
group_items[group[i]].append(i)
item_degree = [0] * n
group_degree = [0] * (n + m)
item_graph = [[] for _ in range(n)]
group_graph = [[] for _ in range(n + m)]
for i, gi in enumerate(group):
for j in beforeItems[i]:
gj = group[j]
if gi == gj:
item_degree[i] += 1
item_graph[j].append(i)
else:
group_degree[gi] += 1
group_graph[gj].append(gi)
group_order = topo_sort(group_degree, group_graph, range(n + m))
if not group_order:
return []
ans = []
for gi in group_order:
items = group_items[gi]
item_order = topo_sort(item_degree, item_graph, items)
if len(items) != len(item_order):
return []
ans.extend(item_order)
return ans
// Accepted solution for LeetCode #1203: Sort Items by Groups Respecting Dependencies
// struct Solution;
// impl Solution {
// fn sort_items(n: i32, m: i32, group: Vec<i32>, before_items: Vec<Vec<i32>>) -> Vec<i32> {
// let n = n as usize;
// let m = m as usize;
// let mut k = m;
// let mut new_group = vec![];
// for i in 0..n {
// if group[i] == -1 {
// new_group.push(k);
// k += 1;
// } else {
// new_group.push(group[i] as usize);
// }
// }
// let mut before_items: Vec<Vec<usize>> = before_items
// .into_iter()
// .map(|v| v.into_iter().map(|i| i as usize).collect())
// .collect();
// let mut groups = vec![vec![]];
// for i in 0..n {
// let g = new_group[i];
// groups[g].push(i);
// }
// let mut res = vec![];
// if !Self::topological_sort(k, n, &new_group, &groups, &before_items, &mut res) {
// return vec![];
// }
// res
// }
// fn topological_sort(
// k: usize,
// n: usize,
// group: &[usize],
// groups: &[Vec<usize>],
// before_items: &[Vec<usize>],
// stack: &mut Vec,
// ) -> bool {
// }
// }
// Accepted solution for LeetCode #1203: Sort Items by Groups Respecting Dependencies
function sortItems(n: number, m: number, group: number[], beforeItems: number[][]): number[] {
let idx = m;
const groupItems: number[][] = new Array(n + m).fill(0).map(() => []);
const itemDegree: number[] = new Array(n).fill(0);
const gorupDegree: number[] = new Array(n + m).fill(0);
const itemGraph: number[][] = new Array(n).fill(0).map(() => []);
const groupGraph: number[][] = new Array(n + m).fill(0).map(() => []);
for (let i = 0; i < n; ++i) {
if (group[i] === -1) {
group[i] = idx++;
}
groupItems[group[i]].push(i);
}
for (let i = 0; i < n; ++i) {
for (const j of beforeItems[i]) {
if (group[i] === group[j]) {
++itemDegree[i];
itemGraph[j].push(i);
} else {
++gorupDegree[group[i]];
groupGraph[group[j]].push(group[i]);
}
}
}
let items = new Array(n + m).fill(0).map((_, i) => i);
const topoSort = (graph: number[][], degree: number[], items: number[]): number[] => {
const q: number[] = [];
for (const i of items) {
if (degree[i] === 0) {
q.push(i);
}
}
const ans: number[] = [];
while (q.length) {
const i = q.pop()!;
ans.push(i);
for (const j of graph[i]) {
if (--degree[j] === 0) {
q.push(j);
}
}
}
return ans.length === items.length ? ans : [];
};
const groupOrder = topoSort(groupGraph, gorupDegree, items);
if (groupOrder.length === 0) {
return [];
}
const ans: number[] = [];
for (const gi of groupOrder) {
items = groupItems[gi];
const itemOrder = topoSort(itemGraph, itemDegree, items);
if (itemOrder.length !== items.length) {
return [];
}
ans.push(...itemOrder);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Repeatedly find a vertex with no incoming edges, remove it and its outgoing edges, and repeat. Finding the zero-in-degree vertex scans all V vertices, and we do this V times. Removing edges touches E edges total. Without an in-degree array, this gives O(V × E).
Build an adjacency list (O(V + E)), then either do Kahn's BFS (process each vertex once + each edge once) or DFS (visit each vertex once + each edge once). Both are O(V + E). Space includes the adjacency list (O(V + E)) plus the in-degree array or visited set (O(V)).
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.