Bubble Sort
An easy Sorting interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sorting
- Sheets
- 2
- Core for
- 13 roles
The problem
Sort an array by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. Continue until no swaps are needed.
Example 1
- Input
- nums = [5, 2, 9, 1, 5, 6]
- Output
- [1, 2, 5, 5, 6, 9]
Example 2
- Input
- nums = [64, 34, 25, 12, 22, 11, 90]
- Output
- [11, 12, 22, 25, 34, 64, 90]
Constraints
- 1 <= nums.length <= 100
- -10^4 <= nums[i] <= 10^4
How to think about it
Updated 2026-09-29Every adjacent comparison is a tiny local filter: whenever a larger value sits on the left of a smaller one, swapping them pulls the larger value rightward. Repeating this full sweep guarantees that after pass k, the k largest elements have permanently settled at the tail, reducing the unsorted frontier by one each round.
Approaches, worst first
Fixed nested loops
time O(n^2) · space O(1)
Run outer loop n times and inner loop across all adjacent pairs regardless of order. Correct and simple, but it blindly completes every comparison even when the array was already sorted at the start or settled early.
Early exit with swap flagWrite this one
time O(n^2) · space O(1)
Shorten the inner scan boundary by one after each pass and track whether any swap happened. If a complete pass finishes without a single swap, every adjacent pair is in order, meaning the entire array is sorted and the routine can stop.
Where people lose marks · 3
- Scanning all the way to index n - 1 on every pass instead of shrinking the inner loop bound wastes comparisons on elements already parked in their final positions.
- Comparing with strict greater-than rather than greater-or-equal preserves stability; using `>=` swaps identical elements and destroys the original relative ordering.
- Forgetting to reset the swapped flag at the start of each outer iteration causes the early-exit check to stay permanently triggered after the first swap.
The theory behind it
Sorting — the ground this problem stands on. All Sorting problems
What Sorting is
Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.
When to reach for it
Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.
How the pattern works
Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.
More Sorting problems
Target Roles
Core requirement for 13 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .