Loading…

easyBasicsSometimes asked

Selection Sort

Basics · 6 min

Given an integer array nums, sort it ascending using selection sort (in place).

In plain English

Repeatedly find the minimum of the unsorted suffix and swap it to the front of that suffix.

Examples

Example 1

Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Note: Sorted.

Example 2

Input: nums = [5, 4]
Output: [4, 5]
Note: One selection.

Example 3

Input: nums = [1]
Output: [1]
Note: Trivial.

Constraints

0 ≤ nums.length ≤ 10^3

Clarifying questions1First question: Stability required?Explore questions

Q1.Stability required?
Selection sort isn't stable; I'd pick insertion/merge sort if it is.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each position i, scan i..n-1 for the minimum index, then swap it into position i. O(n²) comparisons, at most n swaps.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you implement min-selection with a single swap per position.

Where candidates slip

Eager swapping (extra writes) or a wrong inner-scan start.

How to stand out

Highlight the O(n) swap count as its distinguishing trait.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Select-min and swap

TimeO(n²)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each step places which element into its final spot?

2Hint 2Explore hint

Find the min index of the suffix, then swap once.

3Hint 3Explore hint

Compare its swap count to bubble sort's.

A · Core idea

Selection sort grows a sorted prefix by repeatedly finding the minimum of the unsorted suffix and swapping it to the front of that suffix.

Why track the min index, not swap eagerly. Scan the suffix recording the index of the smallest element, then do a single swap into position i. Swapping every time you see a smaller value would do many extra writes.

Its signature property: few swaps. It always does O(n²) comparisons, but only O(n) swaps (one per position). When writes are expensive (e.g. to flash memory), that minimal-write property is its advantage over bubble sort.

Not stable, in place. It can reorder equal elements, and uses O(1) extra space. Like the other O(n²) sorts, it's a fundamentals algorithm.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 1, 2]

i=0

min is 1 at idx1

State[1,3,2]

Final result[1, 2, 3]

C · Code with teaching comments

solution.javaJava

Select-min and swap — optimal

2 teaching notes

1
public void selectionSort(int[] nums) {
2
    for (int i = 0; i < nums.length - 1; i++) {
3
        int min = i;
4
        for (int j = i + 1; j < nums.length; j++) {
5
            // Track the index of the smallest remaining element.
6
            if (nums[j] < nums[min]) min = j;
7
        }
8
        int t = nums[i];
9
        nums[i] = nums[min];
10
        nums[min] = t;
11
    }
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — n positions each scanning the remaining suffix → O(n²) comparisons, but only O(n) swaps.

E · Edge cases and pitfalls5nums = [5, 4] — One selection → [4, 5].Explore edge cases

Edge cases handled

nums = [5, 4]One selection → [4, 5].
nums = [1]Trivial.
nums = [1, 2, 3]Still O(n²) comparisons even when sorted.

Pitfalls

Swapping values instead of tracking the min index.
Starting the inner scan at i instead of i+1 (harmless but wasteful).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void selectionSort(int[] nums) { for (int i = 0; i < nums.length - 1; i++) { int min = i; for (int j = i + 1; j < nums.length; j++) { if (nums[j] < nums[min]) min = j;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Swapping values instead of tracking the min index.
Starting the inner scan at i instead of i+1 (harmless but wasteful).

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Select-min, swap

Code pattern to memorize

for i: m=argmin(a[i..]); swap a[i], a[m]

Rules to remember

1Find min of suffix.
2Swap to position i.
3≤ n swaps total.

Use this pattern when

When swaps/writes are costly

Interview takeaway

Selection sort minimises swaps at the cost of always O(n²) compares.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Select-min, swap. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

easyBasicsSometimes asked

Selection Sort

Basics · 6 min

Given an integer array nums, sort it ascending using selection sort (in place).

In plain English

Repeatedly find the minimum of the unsorted suffix and swap it to the front of that suffix.

Examples

Example 1

Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Note: Sorted.

Example 2

Input: nums = [5, 4]
Output: [4, 5]
Note: One selection.

Example 3

Input: nums = [1]
Output: [1]
Note: Trivial.

Constraints

0 ≤ nums.length ≤ 10^3

Clarifying questions1First question: Stability required?Explore questions

Q1.Stability required?
Selection sort isn't stable; I'd pick insertion/merge sort if it is.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each position i, scan i..n-1 for the minimum index, then swap it into position i. O(n²) comparisons, at most n swaps.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you implement min-selection with a single swap per position.

Where candidates slip

Eager swapping (extra writes) or a wrong inner-scan start.

How to stand out

Highlight the O(n) swap count as its distinguishing trait.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Select-min and swap

TimeO(n²)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each step places which element into its final spot?

2Hint 2Explore hint

Find the min index of the suffix, then swap once.

3Hint 3Explore hint

Compare its swap count to bubble sort's.

A · Core idea

Selection sort grows a sorted prefix by repeatedly finding the minimum of the unsorted suffix and swapping it to the front of that suffix.

Not stable, in place. It can reorder equal elements, and uses O(1) extra space. Like the other O(n²) sorts, it's a fundamentals algorithm.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 1, 2]

i=0

min is 1 at idx1

State[1,3,2]

Final result[1, 2, 3]

C · Code with teaching comments

solution.javaJava

Select-min and swap — optimal

2 teaching notes

1
public void selectionSort(int[] nums) {
2
    for (int i = 0; i < nums.length - 1; i++) {
3
        int min = i;
4
        for (int j = i + 1; j < nums.length; j++) {
5
            // Track the index of the smallest remaining element.
6
            if (nums[j] < nums[min]) min = j;
7
        }
8
        int t = nums[i];
9
        nums[i] = nums[min];
10
        nums[min] = t;
11
    }
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — n positions each scanning the remaining suffix → O(n²) comparisons, but only O(n) swaps.

E · Edge cases and pitfalls5nums = [5, 4] — One selection → [4, 5].Explore edge cases

Edge cases handled

nums = [5, 4]One selection → [4, 5].
nums = [1]Trivial.
nums = [1, 2, 3]Still O(n²) comparisons even when sorted.

Pitfalls

Swapping values instead of tracking the min index.
Starting the inner scan at i instead of i+1 (harmless but wasteful).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Swapping values instead of tracking the min index.
Starting the inner scan at i instead of i+1 (harmless but wasteful).

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Select-min, swap

Code pattern to memorize

for i: m=argmin(a[i..]); swap a[i], a[m]

Rules to remember

1Find min of suffix.
2Swap to position i.
3≤ n swaps total.

Use this pattern when

When swaps/writes are costly

Interview takeaway

Selection sort minimises swaps at the cost of always O(n²) compares.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Select-min, swap. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern