Loading…

easyArraysSometimes asked

Quicksort 1 - Partition

Q: How do you solve Quicksort 1 - Partition using the Two Helper Arrays (Out-of-Place Partition) approach?

When to use it: The clearest correct answer for this challenge — state it directly, it's the intended solution. Fix `p = arr[0]`. Walk `arr[1..]` exactly once. Each element is either less than `p` (push to `left`) or greater than `p` (push to `right`) — distinctness guarantees there's no third case. Finally return `left + [p] + right`. **Why we don't sort the sides.** The deliverable is a *partition*, defined by a single invariant: everything before `p` is smaller and everything after is larger. The internal order of each side carries no meaning for this step. Sorting them would be wasted work (and would actually be the next challenge, Quicksort 2, which recurses). **Why this out-of-place version is stable.** Because we append elements in the order we encounter them, two elements on the same side keep their original relative order. The in-place partition (swapping within the array) is faster on space but scrambles that order — a distinction worth naming to an interviewer. **Why the pivot is appended exactly once.** We start the scan at index 1, never re-add `arr[0]` to a side, and place it precisely once in the middle. Losing or duplicating the pivot is the classic partition bug. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Quicksort 1 - Partition using the In-Place Lomuto Partition (Space-Optimised) approach?

When to use it: Bring up when the interviewer constrains extra space to O(1) or asks how real quicksort avoids allocating arrays. The Lomuto scheme partitions in place. With the pivot at index 0, keep a boundary `i` (initialised so the smaller region is empty) and scan `j` from `1` to `n−1`. Whenever `arr[j] < pivot`, advance the boundary and swap `arr[j]` into it. After the scan, swap the pivot into the boundary slot so it lands between the two regions. **Why this trades stability for space.** Swapping distant elements reorders equal-side elements relative to each other, so the in-place version is *not stable* — but it uses only `O(1)` extra memory, which is why production quicksort uses it. **Why the result can differ from the out-of-place version.** Both satisfy the partition invariant (smaller | pivot | larger), but the exact arrangement of each side may differ. For HackerRank's checker, any valid partition with the pivot correctly placed is accepted — but if the grader expects the specific `left + [p] + right` order, prefer the helper-array version. Mention this so you pick the version that matches the spec. Time complexity: O(n). Space complexity: O(1).

Arrays & Hashing · 59 of 83 · 7 min

Given an array arr, partition it around the first element p = arr[0] (the pivot).

Reorder the array so that all elements less than p come before p, and all elements greater than p come after it. You do not need to sort the array — just produce a valid partition.

Return the partitioned array.

In plain English

A partition step takes a pivot and arranges the array into three regions: things smaller than the pivot, the pivot itself, and things larger. The sides do not need to be internally sorted. Here the pivot is fixed as the first element, and elements are guaranteed distinct so there is no 'equal to pivot' case to worry about.

Examples

Example 1

Input: arr = [5, 7, 4, 3, 8, 6, 2]
Output: 4 3 2 5 7 8 6
Note: Pivot p = 5. Smaller than 5: [4, 3, 2]; larger: [7, 8, 6]. Result is [4,3,2] + [5] + [7,8,6]. Sides keep their original relative order (out-of-place).

Example 2

Input: arr = [4, 5, 3, 7, 2]
Output: 3 2 4 5 7
Note: Pivot p = 4. Smaller: [3, 2]; larger: [5, 7]. Result [3,2] + [4] + [5,7].

Constraints

1 ≤ n ≤ 1000
-1000 ≤ arr[i] ≤ 1000
All elements are distinct (so no element equals the pivot besides the pivot itself)
The pivot is always arr[0]

Clarifying questions4First question: Which element is the pivot?Explore questions

Q1.Which element is the pivot?
The first element, arr[0]. The challenge fixes it; in real quicksort you'd often randomise.
Q2.Do the left and right sides need to be sorted?
No. Only their side relative to the pivot matters — this is a single partition, not a sort.
Q3.Can there be elements equal to the pivot?
Not in this challenge — elements are distinct. In general you'd pick a consistent side (or do three-way) for equals.
Q4.In-place or extra array?
This variant allows one extra array, so the simplest correct answer builds left/right lists. The in-place version saves space but loses stability.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Pick the first element as the pivot p. Walk the rest of the array once, sending every element smaller than p into a `left` list and every element larger than p into a `right` list. Output `left + [p] + right`. This is one partition step — not a full sort. O(n) time, O(n) extra space with the two helper arrays.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand that a partition only guarantees 'pivot in the middle, smaller left, larger right' — not a sorted result — and can implement it cleanly with a chosen pivot.

Where candidates slip

Trying to sort the two sides, or accidentally dropping/duplicating the pivot, or putting the pivot itself into a side list.

How to stand out

State the partition invariant explicitly, note this out-of-place version is stable while in-place partitions are not, and connect it to quicksort and quickselect.

Choose

Compare the available approaches

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

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Helper Arrays (Out-of-Place Partition)	`O(n)`	`O(n)`	The clearest correct answer for this challenge — state it directly, it's the intended solution.	Read
2	In-Place Lomuto Partition (Space-Optimised)Optimal	`O(n)`	`O(1)`	Bring up when the interviewer constrains extra space to O(1) or asks how real quicksort avoids allocating arrays.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewPlace pivot p = arr[0]x < p ?YesNoExplore the full tree

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 2

Two Helper Arrays (Out-of-Place Partition)

TimeO(n)SpaceO(n)

The clearest correct answer for this challenge — state it directly, it's the intended solution.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The pivot is arr[0]. Every other element is either smaller or larger than it. Where should each go?

2Hint 2Explore hint

Create two empty lists: left for elements < p, right for elements > p. Scan arr[1..] once and route each element.

3Hint 3Explore hint

Concatenate left + [p] + right. Don't sort the sides — a partition only needs them on the correct side of p.

A · Core idea

Fix p = arr[0]. Walk arr[1..] exactly once. Each element is either less than p (push to left) or greater than p (push to right) — distinctness guarantees there's no third case. Finally return left + [p] + right.

Why we don't sort the sides. The deliverable is a partition, defined by a single invariant: everything before p is smaller and everything after is larger. The internal order of each side carries no meaning for this step. Sorting them would be wasted work (and would actually be the next challenge, Quicksort 2, which recurses).

Why this out-of-place version is stable. Because we append elements in the order we encounter them, two elements on the same side keep their original relative order. The in-place partition (swapping within the array) is faster on space but scrambles that order — a distinction worth naming to an interviewer.

Why the pivot is appended exactly once. We start the scan at index 1, never re-add arr[0] to a side, and place it precisely once in the middle. Losing or duplicating the pivot is the classic partition bug.

B · Visual dry run

Interactive dry run

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

arr = [5, 7, 4, 3, 8, 6, 2]

Array state

start

pivot = 5

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result4 3 2 5 7 8 6

C · Code with teaching comments

Reference implementation previewpublic int[] partition(int[] arr) { int p = arr[0]; List<Integer> left = new ArrayList<>(); List<Integer> right = new ArrayList<>(); for (int i = 1; i < arr.length; i++) {Explore the full code

solution.javaJava

Two Helper Arrays (Out-of-Place Partition) — reference

4 teaching notes

1
public int[] partition(int[] arr) {
2
    // Pivot is the first element, fixed by the challenge.
3
    int p = arr[0];
4
    List<Integer> left = new ArrayList<>();
5
    List<Integer> right = new ArrayList<>();
6
    // Start at index 1 so the pivot itself is never routed into a side.
7
    for (int i = 1; i < arr.length; i++) {
8
        if (arr[i] < p) left.add(arr[i]);
9
        else right.add(arr[i]);
10
    }
11
    int[] result = new int[arr.length];
12
    int idx = 0;
13
    for (int x : left) result[idx++] = x;
14
    // Place the pivot exactly once between the two sides.
15
    result[idx++] = p;
16
    for (int x : right) result[idx++] = x;
17
    return result;
18
}

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

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

Partition is the irreducible atom of quicksort: 'pivot to its region in O(n)'. Recurse on both sides and you get a sort; recurse on one side and you get O(n)-average selection (quickselect). One routine, three famous algorithms.

ComplexityO(n) time, O(n) space — One linear scan over n−1 elements to route them, plus building the result list of size n: O(n) time. The two helper lists hold up to n−1 elements: O(n) space.

E · Edge cases and pitfalls5arr = [4, 5, 3, 7, 2] — Pivot 4 → left=[3,2], right=[5,7] → 3 2 4 5 7.Explore edge cases

Edge cases handled

arr = [4, 5, 3, 7, 2]Pivot 4 → left=[3,2], right=[5,7] → 3 2 4 5 7.
arr = [3]Single element is already partitioned — left and right empty, output [3].

Pitfalls

Sorting the left/right sides — that is a full sort, not a partition.
Starting the scan at index 0 and routing the pivot into a side.
Using `<=` for the right side too, duplicating the pivot or mishandling equals (here elements are distinct, but the habit bites later).

03.2

Approach 2 of 2 · Optimal

In-Place Lomuto Partition (Space-Optimised)

TimeO(n)SpaceO(1)

Bring up when the interviewer constrains extra space to O(1) or asks how real quicksort avoids allocating arrays.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Can you achieve the same partition without allocating two new arrays?

2Hint 2Explore hint

Keep a boundary index i marking the end of the 'smaller-than-pivot' region. Scan with j; when arr[j] < pivot, swap it into the boundary and advance i.

3Hint 3Explore hint

At the end, swap the pivot into position i so it sits exactly between the two regions.

A · Core idea

The Lomuto scheme partitions in place. With the pivot at index 0, keep a boundary i (initialised so the smaller region is empty) and scan j from 1 to n−1. Whenever arr[j] < pivot, advance the boundary and swap arr[j] into it. After the scan, swap the pivot into the boundary slot so it lands between the two regions.

Why this trades stability for space. Swapping distant elements reorders equal-side elements relative to each other, so the in-place version is not stable — but it uses only O(1) extra memory, which is why production quicksort uses it.

Why the result can differ from the out-of-place version. Both satisfy the partition invariant (smaller | pivot | larger), but the exact arrangement of each side may differ. For HackerRank's checker, any valid partition with the pivot correctly placed is accepted — but if the grader expects the specific left + [p] + right order, prefer the helper-array version. Mention this so you pick the version that matches the spec.

B · Visual dry run

Interactive dry run

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

arr = [4, 5, 3, 7, 2]

Array state

after scan

smaller elements moved front

[0]

[1]

i ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result2 3 4 7 5 (valid partition: <4 | 4 | >4)

C · Code with teaching comments

solution.javaJava

In-Place Lomuto Partition (Space-Optimised) — optimal

3 teaching notes

1
public int[] partition(int[] arr) {
2
    int pivot = arr[0];
3
    // Boundary of the <pivot region; pivot sits at index 0 so the region starts empty.
4
    int i = 0;
5
    for (int j = 1; j < arr.length; j++) {
6
        // Only smaller elements get swapped toward the front.
7
        if (arr[j] < pivot) {
8
            i++;
9
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
10
        }
11
    }
12
    // Final swap drops the pivot between the two regions.
13
    int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
14
    return arr;
15
}

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

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

Lomuto's boundary index is a running invariant: everything left of i is < pivot, everything between i and j is ≥ pivot. Maintaining a single boundary pointer in one pass is the same trick behind Move Zeroes and Remove Element.

ComplexityO(n) time, O(1) space — Single pass with j; each comparison is O(1) and there are n−1 of them. Swaps are in-place, so only O(1) auxiliary space beyond the input array.

E · Edge cases and pitfalls5arr = [3] — Loop body never runs; final swap is a no-op → [3].Explore edge cases

Edge cases handled

arr = [3]Loop body never runs; final swap is a no-op → [3].
arr = [2, 1]j=1: 1<2 → i=1, swap arr[1] with itself; final pivot swap of arr[0],arr[1] → [1,2]. Valid partition (1 < 2).

Pitfalls

Off-by-one on the boundary index i (incrementing before vs after the swap).
Forgetting the final pivot swap — leaves the pivot stranded at index 0.
Assuming stable output — in-place Lomuto reorders the sides, which may mismatch a strict checker.

Practice

Try the solution yourself

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

Editable code previewpublic int[] partition(int[] arr) { int pivot = arr[0]; int i = 0; for (int j = 1; j < arr.length; j++) { if (arr[j] < pivot) {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.

Sorting the partition sides

Quicksort 1 asks only for a single partition. Sorting each side does extra work and is actually the next problem (Quicksort 2).

Explore the code comparison

Don't write this

left = sorted(x for x in arr[1:] if x < p)
right = sorted(x for x in arr[1:] if x > p)
return left + [p] + right

Write this instead

left = [x for x in arr[1:] if x < p]
right = [x for x in arr[1:] if x > p]
return left + [p] + right

Including the pivot in a side

Scanning from index 0 (or using <= / >=) puts the pivot into left or right and then again in the middle, duplicating it.

Explore the code comparison

Don't write this

for (int i = 0; i < arr.length; i++) {
    if (arr[i] <= p) left.add(arr[i]);
    else right.add(arr[i]);
}

Write this instead

for (int i = 1; i < arr.length; i++) {
    if (arr[i] < p) left.add(arr[i]);
    else right.add(arr[i]);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Single partition around a pivot using two helper arrays

Code pattern to memorize

p = arr[0]
left  = [x for x in arr[1:] if x < p]
right = [x for x in arr[1:] if x > p]
return left + [p] + right

Rules to remember

1The pivot is the first element, arr[0], in this challenge — not the last and not the median.
2You are NOT sorting. left and right only need to be on the correct side of p; their internal order is irrelevant.
3Output is exactly left + [p] + right — one pivot in the middle, smaller on the left, larger on the right.
4With the 'one extra array' (out-of-place) version, relative order within each side is preserved; the in-place Hoare/Lomuto version need not preserve it.
5Every element except the pivot lands in exactly one side — never lose or duplicate p.

Use this pattern when

You need the building block of quicksort / quickselect
You must place a pivot in its correct relative region without fully sorting
Partitioning a stream into below/above a threshold
Teaching or demonstrating the partition invariant

Choose another pattern when

You need the fully sorted array → that is Quicksort 2 (recurse on both sides)
You need the k-th smallest element → recurse into one side only (quickselect)
Strict O(1) extra space is required → use in-place Lomuto/Hoare partition instead of helper arrays

Interview takeaway

Partition is the heart of quicksort: it places elements relative to a pivot in one linear pass. Master this single step and quicksort, quickselect, and Dutch-flag all fall out of it.

Continue

Transfer the pattern to another problem

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

Transferable patternPartition. The O(n) core of quicksort and quickselect: place a pivot into its region with smaller elements before and larger after. Out-of-place is stable and clear; in-place Lomuto is O(1) space but unstable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Quicksort 2 - Sorting
Recurse this partition on both sides to fully sort the array.
Quickselect / Kth Largest Element
Coming soon
Partition, then recurse into only the side containing rank k — O(n) average.
Sort Colors (Dutch National Flag)
Coming soon
A three-way partition (<, =, >) handling duplicates of the pivot value.

Same pattern

←

Merge Sort: Counting Inversions

Continue · Next problem

Quicksort 2 - Sorting (Partition)

easyArraysSometimes asked

Quicksort 1 - Partition

Arrays & Hashing · 59 of 83 · 7 min

Given an array arr, partition it around the first element p = arr[0] (the pivot).

Reorder the array so that all elements less than p come before p, and all elements greater than p come after it. You do not need to sort the array — just produce a valid partition.

Return the partitioned array.

In plain English

Examples

Example 1

Input: arr = [5, 7, 4, 3, 8, 6, 2]
Output: 4 3 2 5 7 8 6
Note: Pivot p = 5. Smaller than 5: [4, 3, 2]; larger: [7, 8, 6]. Result is [4,3,2] + [5] + [7,8,6]. Sides keep their original relative order (out-of-place).

Example 2

Input: arr = [4, 5, 3, 7, 2]
Output: 3 2 4 5 7
Note: Pivot p = 4. Smaller: [3, 2]; larger: [5, 7]. Result [3,2] + [4] + [5,7].

Constraints

1 ≤ n ≤ 1000
-1000 ≤ arr[i] ≤ 1000
All elements are distinct (so no element equals the pivot besides the pivot itself)
The pivot is always arr[0]

Clarifying questions4First question: Which element is the pivot?Explore questions

Q1.Which element is the pivot?
The first element, arr[0]. The challenge fixes it; in real quicksort you'd often randomise.
Q2.Do the left and right sides need to be sorted?
No. Only their side relative to the pivot matters — this is a single partition, not a sort.
Q3.Can there be elements equal to the pivot?
Not in this challenge — elements are distinct. In general you'd pick a consistent side (or do three-way) for equals.
Q4.In-place or extra array?
This variant allows one extra array, so the simplest correct answer builds left/right lists. The in-place version saves space but loses stability.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand that a partition only guarantees 'pivot in the middle, smaller left, larger right' — not a sorted result — and can implement it cleanly with a chosen pivot.

Where candidates slip

Trying to sort the two sides, or accidentally dropping/duplicating the pivot, or putting the pivot itself into a side list.

How to stand out

State the partition invariant explicitly, note this out-of-place version is stable while in-place partitions are not, and connect it to quicksort and quickselect.

Choose

Compare the available approaches

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

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Helper Arrays (Out-of-Place Partition)	`O(n)`	`O(n)`	The clearest correct answer for this challenge — state it directly, it's the intended solution.	Read
2	In-Place Lomuto Partition (Space-Optimised)Optimal	`O(n)`	`O(1)`	Bring up when the interviewer constrains extra space to O(1) or asks how real quicksort avoids allocating arrays.	Read

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 2

Two Helper Arrays (Out-of-Place Partition)

TimeO(n)SpaceO(n)

The clearest correct answer for this challenge — state it directly, it's the intended solution.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The pivot is arr[0]. Every other element is either smaller or larger than it. Where should each go?

2Hint 2Explore hint

Create two empty lists: left for elements < p, right for elements > p. Scan arr[1..] once and route each element.

3Hint 3Explore hint

Concatenate left + [p] + right. Don't sort the sides — a partition only needs them on the correct side of p.

A · Core idea

B · Visual dry run

Interactive dry run

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

arr = [5, 7, 4, 3, 8, 6, 2]

Array state

start

pivot = 5

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result4 3 2 5 7 8 6

C · Code with teaching comments

solution.javaJava

Two Helper Arrays (Out-of-Place Partition) — reference

4 teaching notes

1
public int[] partition(int[] arr) {
2
    // Pivot is the first element, fixed by the challenge.
3
    int p = arr[0];
4
    List<Integer> left = new ArrayList<>();
5
    List<Integer> right = new ArrayList<>();
6
    // Start at index 1 so the pivot itself is never routed into a side.
7
    for (int i = 1; i < arr.length; i++) {
8
        if (arr[i] < p) left.add(arr[i]);
9
        else right.add(arr[i]);
10
    }
11
    int[] result = new int[arr.length];
12
    int idx = 0;
13
    for (int x : left) result[idx++] = x;
14
    // Place the pivot exactly once between the two sides.
15
    result[idx++] = p;
16
    for (int x : right) result[idx++] = x;
17
    return result;
18
}

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

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

E · Edge cases and pitfalls5arr = [4, 5, 3, 7, 2] — Pivot 4 → left=[3,2], right=[5,7] → 3 2 4 5 7.Explore edge cases

Edge cases handled

arr = [4, 5, 3, 7, 2]Pivot 4 → left=[3,2], right=[5,7] → 3 2 4 5 7.
arr = [3]Single element is already partitioned — left and right empty, output [3].

Pitfalls

Sorting the left/right sides — that is a full sort, not a partition.
Starting the scan at index 0 and routing the pivot into a side.
Using `<=` for the right side too, duplicating the pivot or mishandling equals (here elements are distinct, but the habit bites later).

03.2

Approach 2 of 2 · Optimal

In-Place Lomuto Partition (Space-Optimised)

TimeO(n)SpaceO(1)

Bring up when the interviewer constrains extra space to O(1) or asks how real quicksort avoids allocating arrays.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Can you achieve the same partition without allocating two new arrays?

2Hint 2Explore hint

Keep a boundary index i marking the end of the 'smaller-than-pivot' region. Scan with j; when arr[j] < pivot, swap it into the boundary and advance i.

3Hint 3Explore hint

At the end, swap the pivot into position i so it sits exactly between the two regions.

A · Core idea

B · Visual dry run

Interactive dry run

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

arr = [4, 5, 3, 7, 2]

Array state

after scan

smaller elements moved front

[0]

[1]

i ↓

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result2 3 4 7 5 (valid partition: <4 | 4 | >4)

C · Code with teaching comments

solution.javaJava

In-Place Lomuto Partition (Space-Optimised) — optimal

3 teaching notes

1
public int[] partition(int[] arr) {
2
    int pivot = arr[0];
3
    // Boundary of the <pivot region; pivot sits at index 0 so the region starts empty.
4
    int i = 0;
5
    for (int j = 1; j < arr.length; j++) {
6
        // Only smaller elements get swapped toward the front.
7
        if (arr[j] < pivot) {
8
            i++;
9
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
10
        }
11
    }
12
    // Final swap drops the pivot between the two regions.
13
    int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
14
    return arr;
15
}

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

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

ComplexityO(n) time, O(1) space — Single pass with j; each comparison is O(1) and there are n−1 of them. Swaps are in-place, so only O(1) auxiliary space beyond the input array.

E · Edge cases and pitfalls5arr = [3] — Loop body never runs; final swap is a no-op → [3].Explore edge cases

Edge cases handled

arr = [3]Loop body never runs; final swap is a no-op → [3].
arr = [2, 1]j=1: 1<2 → i=1, swap arr[1] with itself; final pivot swap of arr[0],arr[1] → [1,2]. Valid partition (1 < 2).

Pitfalls

Off-by-one on the boundary index i (incrementing before vs after the swap).
Forgetting the final pivot swap — leaves the pivot stranded at index 0.
Assuming stable output — in-place Lomuto reorders the sides, which may mismatch a strict checker.

Practice

Try the solution yourself

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

Editable code previewpublic int[] partition(int[] arr) { int pivot = arr[0]; int i = 0; for (int j = 1; j < arr.length; j++) { if (arr[j] < pivot) {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.

Sorting the partition sides

Quicksort 1 asks only for a single partition. Sorting each side does extra work and is actually the next problem (Quicksort 2).

Explore the code comparison

Don't write this

left = sorted(x for x in arr[1:] if x < p)
right = sorted(x for x in arr[1:] if x > p)
return left + [p] + right

Write this instead

left = [x for x in arr[1:] if x < p]
right = [x for x in arr[1:] if x > p]
return left + [p] + right

Including the pivot in a side

Scanning from index 0 (or using <= / >=) puts the pivot into left or right and then again in the middle, duplicating it.

Explore the code comparison

Don't write this

for (int i = 0; i < arr.length; i++) {
    if (arr[i] <= p) left.add(arr[i]);
    else right.add(arr[i]);
}

Write this instead

for (int i = 1; i < arr.length; i++) {
    if (arr[i] < p) left.add(arr[i]);
    else right.add(arr[i]);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Single partition around a pivot using two helper arrays

Code pattern to memorize

p = arr[0]
left  = [x for x in arr[1:] if x < p]
right = [x for x in arr[1:] if x > p]
return left + [p] + right

Rules to remember

1The pivot is the first element, arr[0], in this challenge — not the last and not the median.
2You are NOT sorting. left and right only need to be on the correct side of p; their internal order is irrelevant.
3Output is exactly left + [p] + right — one pivot in the middle, smaller on the left, larger on the right.
4With the 'one extra array' (out-of-place) version, relative order within each side is preserved; the in-place Hoare/Lomuto version need not preserve it.
5Every element except the pivot lands in exactly one side — never lose or duplicate p.

Use this pattern when

You need the building block of quicksort / quickselect
You must place a pivot in its correct relative region without fully sorting
Partitioning a stream into below/above a threshold
Teaching or demonstrating the partition invariant

Choose another pattern when

You need the fully sorted array → that is Quicksort 2 (recurse on both sides)
You need the k-th smallest element → recurse into one side only (quickselect)
Strict O(1) extra space is required → use in-place Lomuto/Hoare partition instead of helper arrays

Interview takeaway

Partition is the heart of quicksort: it places elements relative to a pivot in one linear pass. Master this single step and quicksort, quickselect, and Dutch-flag all fall out of it.

Continue

Transfer the pattern to another problem

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

Practice queueDirect variations and pattern siblings

Direct follow-ups

Quicksort 2 - Sorting
Recurse this partition on both sides to fully sort the array.
Quickselect / Kth Largest Element
Coming soon
Partition, then recurse into only the side containing rank k — O(n) average.
Sort Colors (Dutch National Flag)
Coming soon
A three-way partition (<, =, >) handling duplicates of the pivot value.

Same pattern

←

Merge Sort: Counting Inversions

Continue · Next problem

Quicksort 2 - Sorting (Partition)