Loading…

easyBasicsSometimes asked

Kth Smallest Element

Basics · 6 min

Given an integer array nums and k (1-indexed), return the k-th smallest element.

In plain English

Sorting and indexing at k-1 is the simple O(n log n) answer; a heap or quickselect can do better.

Examples

Example 1

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

Example 2

Input: nums = [5], k = 1
Output: 5
Note: Only element.

Example 3

Input: nums = [4, 4, 4], k = 2
Output: 4
Note: Duplicates count.

Constraints

1 ≤ k ≤ nums.length ≤ 10^4

Clarifying questions2First question: Is k 1-indexed?Explore questions

Q1.Is k 1-indexed?
Assuming yes → sorted index k-1; confirm if 0-indexed.
Q2.k-th smallest or largest?
Smallest here; largest is symmetric (n-k).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Sort ascending and return `nums[k-1]`. O(n log n). For large data, quickselect is O(n) average and a min-heap is O(n + k log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle the 1/0 indexing and know faster order-statistic methods.

Where candidates slip

The k vs k-1 off-by-one, or sorting in place destructively.

How to stand out

Describe quickselect's average O(n) and the size-k heap.

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

Sort and index

TimeO(n log n)SpaceO(1) – O(n)

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

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Where does the k-th smallest sit in a sorted array?

2Hint 2Explore hint

Sort and index k−1 is the baseline — what's the 1-vs-0 indexing?

3Hint 3Explore hint

Do you need to sort everything for one order statistic?

A · Core idea

The k-th smallest element sits at index k−1 once the array is sorted, so sort and index is the clean O(n log n) baseline. Faster methods exist for a single order statistic.

Why sort-and-index is correct. Sorting ascending arranges elements by rank; the element at 0-based index k−1 is the k-th smallest (1-indexed k). Duplicates count toward the rank, which is the usual convention.

Why mention quickselect / a heap. If you only need one order statistic, sorting everything is overkill. Quickselect partitions like quicksort but recurses into only one side, averaging O(n). A bounded max-heap of size k gives O(n log k). Naming these shows you know sorting isn't always necessary.

Don't mutate the caller's array unless allowed — sort a copy.

B · Visual dry run

Interactive dry run

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

nums = [3, 1, 2], k = 2

sort

[1, 2, 3]

Statesorted

Final result2

C · Code with teaching comments

solution.javaJava

Sort and index — optimal

2 teaching notes

1
public int kthSmallest(int[] nums, int k) {
2
    int[] copy = nums.clone();
3
    // Order the elements ascending.
4
    java.util.Arrays.sort(copy);
5
    // 1-indexed k maps to array index k-1.
6
    return copy[k - 1];
7
}

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

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

Naming quickselect / a bounded heap shows you know sorting isn't always necessary for a single order statistic.

ComplexityO(n log n) time, O(1) – O(n) space — sorting is O(n log n); quickselect averages O(n); a size-k heap is O(n log k).

E · Edge cases and pitfalls4nums = [5], k = 1 — Only element → 5.Explore edge cases

Edge cases handled

nums = [5], k = 1Only element → 5.
nums = [4, 4, 4], k = 2Duplicates count → 4.

Pitfalls

Off-by-one: returning nums[k] instead of nums[k-1].
Mutating the caller's array when a copy is expected.

Practice

Try the solution yourself

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

Editable code previewpublic int kthSmallest(int[] nums, int k) { int[] copy = nums.clone(); java.util.Arrays.sort(copy); return copy[k - 1]; }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.

Off-by-one: returning nums[k] instead of nums[k-1].
Mutating the caller's array when a copy is expected.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort then index (order statistic)

Code pattern to memorize

sorted(nums)[k-1]   (or quickselect for O(n) avg)

Rules to remember

1Sort ascending.
2k-th smallest = index k-1.
3Quickselect for O(n).

Use this pattern when

Order statistics

Choose another pattern when

Streaming / huge data — use a bounded heap or quickselect

Interview takeaway

k-th smallest = sort and index; quickselect if you need speed.

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: Sort then index (order statistic). Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Kth Largest Element
Coming soon
Heap or quickselect; symmetric to smallest.

Same pattern

easyBasicsSometimes asked

Kth Smallest Element

Basics · 6 min

Given an integer array nums and k (1-indexed), return the k-th smallest element.

In plain English

Sorting and indexing at k-1 is the simple O(n log n) answer; a heap or quickselect can do better.

Examples

Example 1

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

Example 2

Input: nums = [5], k = 1
Output: 5
Note: Only element.

Example 3

Input: nums = [4, 4, 4], k = 2
Output: 4
Note: Duplicates count.

Constraints

1 ≤ k ≤ nums.length ≤ 10^4

Clarifying questions2First question: Is k 1-indexed?Explore questions

Q1.Is k 1-indexed?
Assuming yes → sorted index k-1; confirm if 0-indexed.
Q2.k-th smallest or largest?
Smallest here; largest is symmetric (n-k).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Sort ascending and return `nums[k-1]`. O(n log n). For large data, quickselect is O(n) average and a min-heap is O(n + k log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you handle the 1/0 indexing and know faster order-statistic methods.

Where candidates slip

The k vs k-1 off-by-one, or sorting in place destructively.

How to stand out

Describe quickselect's average O(n) and the size-k heap.

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

Sort and index

TimeO(n log n)SpaceO(1) – O(n)

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

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Where does the k-th smallest sit in a sorted array?

2Hint 2Explore hint

Sort and index k−1 is the baseline — what's the 1-vs-0 indexing?

3Hint 3Explore hint

Do you need to sort everything for one order statistic?

A · Core idea

The k-th smallest element sits at index k−1 once the array is sorted, so sort and index is the clean O(n log n) baseline. Faster methods exist for a single order statistic.

Don't mutate the caller's array unless allowed — sort a copy.

B · Visual dry run

Interactive dry run

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

nums = [3, 1, 2], k = 2

sort

[1, 2, 3]

Statesorted

Final result2

C · Code with teaching comments

solution.javaJava

Sort and index — optimal

2 teaching notes

1
public int kthSmallest(int[] nums, int k) {
2
    int[] copy = nums.clone();
3
    // Order the elements ascending.
4
    java.util.Arrays.sort(copy);
5
    // 1-indexed k maps to array index k-1.
6
    return copy[k - 1];
7
}

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

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

Naming quickselect / a bounded heap shows you know sorting isn't always necessary for a single order statistic.

ComplexityO(n log n) time, O(1) – O(n) space — sorting is O(n log n); quickselect averages O(n); a size-k heap is O(n log k).

E · Edge cases and pitfalls4nums = [5], k = 1 — Only element → 5.Explore edge cases

Edge cases handled

nums = [5], k = 1Only element → 5.
nums = [4, 4, 4], k = 2Duplicates count → 4.

Pitfalls

Off-by-one: returning nums[k] instead of nums[k-1].
Mutating the caller's array when a copy is expected.

Practice

Try the solution yourself

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

Editable code previewpublic int kthSmallest(int[] nums, int k) { int[] copy = nums.clone(); java.util.Arrays.sort(copy); return copy[k - 1]; }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.

Off-by-one: returning nums[k] instead of nums[k-1].
Mutating the caller's array when a copy is expected.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort then index (order statistic)

Code pattern to memorize

sorted(nums)[k-1]   (or quickselect for O(n) avg)

Rules to remember

1Sort ascending.
2k-th smallest = index k-1.
3Quickselect for O(n).

Use this pattern when

Order statistics

Choose another pattern when

Streaming / huge data — use a bounded heap or quickselect

Interview takeaway

k-th smallest = sort and index; quickselect if you need speed.

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: Sort then index (order statistic). Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Kth Largest Element
Coming soon
Heap or quickselect; symmetric to smallest.

Same pattern