Introduction

LeetCode 2161 is a clean and important array manipulation problem that tests:

1. Array traversal
2. Stable partitioning
3. Order preservation
4. Two-pass and three-pass approaches
5. Logical grouping of elements

The interesting part of this problem is that we are not only partitioning the array around a pivot, but we also need to preserve the relative order of elements.

This makes the problem slightly different from classical partition algorithms like QuickSort partitioning.

In this article, we will understand:

1. The intuition behind stable partitioning
2. Why order preservation matters
3. Step-by-step explanation
4. Dry run
5. Time and space complexity
6. Complete optimized Java solution

Problem Statement

Try this probelm here :- Partition Array

You are given:

1. An integer array:

1. An integer:

You must rearrange the array such that:

1. All elements smaller than pivot come first
2. All elements equal to pivot come next
3. All elements greater than pivot come last
4. Relative ordering must remain preserved

Return the rearranged array.

Example

Input

Output

Explanation

Elements less than 10

Elements equal to 10

Elements greater than 10

All relative orderings are preserved.

Key Observation

We do NOT need sorting.

We only need grouping while maintaining original order.

This is called:

Approach

We create a new array and fill it in 3 phases:

Phase 1

Insert all elements:

Phase 2

Insert all elements:

Phase 3

Insert all elements:

This naturally preserves relative ordering because we traverse left-to-right every time.

Optimized Java Solution

Step-by-Step Explanation

Step 1: Create Answer Array

Stores final partitioned result.

Step 2: Insert Smaller Elements

All smaller elements go first.

Step 3: Insert Equal Elements

Pivot values are placed in the middle.

Step 4: Insert Larger Elements

Larger elements go to the end.

Dry Run

Input

Pass 1: Smaller Elements

Add:

Current array:

Pass 2: Equal Elements

Add:

Current array:

Pass 3: Greater Elements

Add:

Final array:

Time Complexity

We traverse the array 3 times.

Time Complexity

Because:

Space Complexity

We use an extra array.

Space Complexity

Why This Problem is Important

This problem teaches:

1. Stable partitioning
2. Array grouping
3. Relative order preservation
4. Multi-pass array processing
5. Clean implementation strategy

These concepts are frequently used in:

1. Sorting systems
2. Data pipelines
3. Stream processing
4. Partition-based algorithms

Common Mistakes

1. Using QuickSort Partition Logic

QuickSort partitioning does NOT preserve order.

This problem specifically requires stable ordering.

2. Forgetting Equal Elements

Some solutions only handle:

and

But pivot values must remain in the center.

3. Overcomplicating with Two Pointers

A simple three-pass solution is cleaner and easier to understand.

Interview Explanation

In interviews explain:

Since relative order must remain preserved, we cannot use traditional in-place partitioning. Instead, we perform stable partitioning by collecting smaller, equal, and larger elements sequentially.

This demonstrates:

1. Understanding of stable operations
2. Strong array fundamentals
3. Clean coding approach

Alternative Approach

Another approach is using:

1. Three separate lists
2. Then merging them

Example:

But using one answer array is more space efficient.

Conclusion

LeetCode 2161 is a simple yet important stable partition problem.

The key insight is:

We must preserve relative ordering while grouping elements around the pivot.

Using a clean three-pass traversal gives an elegant and efficient O(N) solution.