Introduction

The Partition Array problem involves rearranging elements based on a condition.

Given:

  • an array
  • a pivot condition

the task is to:

  • place elements satisfying condition on one side
  • place remaining elements on other side

This problem is one of the most important applications of:

 Partitioning Technique

This concept is heavily used in:

  • Quick Sort
  • Dutch National Flag Algorithm
  • Two Pointer problems

This problem helps in understanding:

  • partitioning
  • swapping
  • two pointers
  • in-place rearrangement

Example

Input:arr = [9, 12, 3, 5, 14, 10, 10]

pivot = 10

Output:
[9, 3, 5, 10, 14, 10, 12]

Explanation:
Elements smaller than pivot are moved left side.

Constraints

 1 <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9

Approach 1 : Extra Array Method

Explanation

The simplest way to solve this problem is:

  1. Traverse array
  2. Store smaller elements
  3. Store greater elements
  4. Combine results

This approach is easy but uses extra space.

Steps

  1. Create result array.
  2. Store smaller elements.
  3. Store equal elements.
  4. Store larger elements.
  5. Return partitioned array.

Dry Run

Input:[9, 12, 3, 5, 14, 10, 10]

pivot = 10

Smaller elements:
[9, 3, 5]

Equal elements:
[10, 10]


Larger elements:
[12, 14]

Combined result:
[9, 3, 5, 10, 10, 12, 14]

Final Result:
[9, 3, 5, 10, 10, 12, 14]

Extra Array Method Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Array is traversed once.

Space Complexity: O(n)
Explanation:
Extra arrays are used.

Approach 2 : Two Pointer Partitioning

Explanation

The optimized solution uses:

 Two Pointers

The idea is:

  1. Maintain partition index
  2. Move smaller elements left
  3. Swap elements in-place

This is the same logic used in:

  • Quick Sort partitioning

Steps

  1. Initialize partition index.
  2. Traverse array.
  3. If current element smaller:
    • swap with partition index
  4. Increment partition index.
  5. Return partitioned array.

Dry Run

Input:[9, 12, 3, 5, 14, 10, 10]

pivot = 10

Initial:
partition = 0

Traverse 9:
9 < 10
Swap with partition

Array:
[9, 12, 3, 5, 14, 10, 10]
partition++

Traverse 3:
3 < 10
Swap with partition

Array:
[9, 3, 12, 5, 14, 10, 10]

Continue traversal...

Final Result:
[9, 3, 5, 12, 14, 10, 10]

Two Pointer Partitioning Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Array is traversed once.

Space Complexity: O(1)
Explanation:
Partitioning is performed in-place.

Edge Cases

  1. Empty array
  2. All elements smaller
  3. All elements larger
  4. Duplicate pivot values
  5. Already partitioned array

Why This Problem is Important

Partition Array helps in understanding:

  1. Partitioning techniques
  2. Two pointer logic
  3. In-place swapping
  4. Quick Sort foundation
  5. Array rearrangement

It is one of the most important partitioning interview problems.

Real-World Applications

Partitioning concepts are used in:

  1. Quick Sort
  2. Data filtering
  3. Memory management
  4. Stream segregation
  5. Task scheduling systems

Common Mistakes

  1. Incorrect partition index
  2. Wrong swap conditions
  3. Forgetting partition increment
  4. Confusing pivot placement

Interview Tips

Interviewers often expect:

  1. Partitioning explanation
  2. In-place optimization
  3. Two pointer understanding

Always explain:

  • role of partition index
  • why swapping works
  • how smaller elements move left

Related Questions

  1. Sort Colors
  2. Quick Sort
  3. Move Zeroes
  4. Sort Array By Parity
  5. Quick Select

Final Takeaway

The Partition Array problem is a fundamental partitioning problem that teaches in-place rearrangement and two-pointer techniques. Understanding this problem builds a strong foundation for advanced partitioning and sorting interview problems.