Sort Problems
2 Sort LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Use sorted order to expose the next safe decision
Sorting is often a preprocessing step that reveals structure: adjacent equal values, the cheapest available edge, or a monotone threshold. Before writing a comparator, state what becomes true after sorting. For component-cost problems, ascending edge weights let you examine connectivity as the permitted maximum cost increases.
When to use it
Sort when processing candidates in a consistent order removes repeated searching or supports a greedy proof. For rearrangement problems, first derive which values are surplus and which exchanges are allowed; sorting those values alone does not establish that a swap strategy is optimal.
Worked example
Vertices A, B, C have edges A–B:2, B–C:5, A–C:9. Find the smallest weight threshold allowing at most two connected components.
- Sort edges by weight: 2, 5, 9. With no edges, there are three components.
- At threshold 2, include A–B and merge its endpoints. There are now two components: {A, B} and {C}.
- No smaller threshold includes an edge, so a threshold below 2 would leave three components.
The minimum threshold is 2. Continuing to weight 5 would connect the entire graph, which is more than this target requires.
Time and space
A comparison sort of n items typically takes O(n log n) time; memory depends on the sorting algorithm and runtime. In the graph example, sorting E edges dominates efficient disjoint-set operations, with O(V) disjoint-set state.
Mistakes to check
- Equal primary keys need a specified secondary key when output order matters. Stability preserves input order among equals; it does not invent the required tie rule.
- A comparator must be consistent and transitive. Subtracting large fixed-width integers can overflow and reverse its result.
- Check whether the problem permits reordering the input and whether its objective concerns total cost, a maximum edge, or lexicographic order.
Further reading: Python Sorting HOWTO: keys, stability, and comparisons
Guide reviewed .