Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Partition Array According to Given Pivot solution and explanation

MediumArraySimulationTwo Pointers6 min read90.8% acceptanceUpdated 9 Apr 2026
Asked atAmazonMicrosoftBloombergGoogleMeta
Practise Partition Array According to Given Pivot
10:15
Partition Array According to Given Pivot - Leetcode 2161 - PythonNeetCodeIO · 10:15 · 10K viewsWatch on YouTube
9 more videos on this problem
  1. Partition Array According to Given Pivot - Leetcode 2161 - PythonNeetCodeIO · 10:15 · 10K views
  2. Partition Array According to Given Pivot | Multiple Approaches | Leetcode 2161 | codestorywithMIKcodestorywithMIK · 29:52 · 10K views
  3. Partition Array According to Given Pivot | Leetcode 2161Techdose · 13:12 · 2K views
  4. 2161. Partition Array According to Given Pivot | leetcode daily challenge | faang | shashcodeShashCode · 9:34 · 2K views
  5. 2161. Partition Array According to Given Pivot | Arrays | Two PointersAryan Mittal · 13:47 · 1K views
  6. Partition Array According to Given Pivot - leetCode 2161 - Coding Interview QuestionsOne Code Man · 3:15 · 1K views
  7. Leetcode | 2161. Partition Array According to Given Pivot | Medium | Java SolutionDeveloper Docs · 6:40 · 719 views
  8. 2161. Partition Array According to Given Pivot (Leetcode Medium)Programming Live with Larry · 3:25 · 513 views
  9. 2161. Partition Array According to Given Pivot | Leetcode Daily - PythonLeetcode Daily · 5:14 · 255 views
  10. Partition Array According to Given Pivot - Leetcode 2161 - PythonTim Huang · 4:07 · 100 views

The problem

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

  • Every element less than pivot appears before every element greater than pivot.
  • Every element equal to pivot appears in between the elements less than and greater than pivot.
  • The relative order of the elements less than pivot and the elements greater than pivot is maintained.
    • More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. For elements less than pivot, if i < j and nums[i] < pivot and nums[j] < pivot, then pi < pj. Similarly for elements greater than pivot, if i < j and nums[i] > pivot and nums[j] > pivot, then pi < pj.

Return nums after the rearrangement.

Example 1:

Input: nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]
Explanation: 
The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.
The elements 12 and 14 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.

Example 2:

Input: nums = [-3,4,3,2], pivot = 2
Output: [-3,2,4,3]
Explanation: 
The element -3 is less than the pivot so it is on the left side of the array.
The elements 4 and 3 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.

Constraints:

  • 1 <= nums.length <= 105
  • -106 <= nums[i] <= 106
  • pivot equals to an element of nums.

Approach overview

Problem Overview: You are given an integer array and a pivot value. Reorder the array so that all elements smaller than the pivot appear first, followed by elements equal to the pivot, and then elements greater than the pivot. The relative order of elements in each group must remain the same.

Approach 1: Three Lists Approach (O(n) time, O(n) space)

The most straightforward solution is to simulate the partitioning process using three temporary arrays. Iterate through the input array once and place each element into one of three lists: less, equal, or greater. If the current number is smaller than the pivot, append it to less. If it equals the pivot, append it to equal. Otherwise append it to greater. After processing all elements, concatenate the three lists in order: less + equal + greater. Because elements are appended in the same order they appear, the relative ordering requirement is preserved automatically.

This approach relies on basic array traversal and is easy to reason about. The time complexity is O(n) since each element is processed once. The space complexity is O(n) due to the additional lists. When interviewers prioritize clarity and correctness over memory optimization, this is often the quickest implementation.

Approach 2: In-Place Partitioning (O(n) time, O(1) extra space)

If you want to reduce extra memory usage, you can simulate the same grouping with careful index management. Iterate through the array and build the result directly while tracking boundaries for elements smaller than and equal to the pivot. The idea is similar to the partition logic used in quicksort: maintain positions where the next less-than or equal-to element should be placed while scanning the array once.

Using a two pointers style approach, you move through the array and place elements into their correct region while preserving order. This requires careful shifting or staged placement but avoids allocating new arrays. The algorithm still runs in O(n) time because every element is examined once, while the additional memory stays at O(1).

This approach is more space-efficient and demonstrates a deeper understanding of array manipulation and partitioning strategies. The logic is slightly more complex than the three-list method, so it’s often used when memory constraints matter.

Recommended for interviews: Start with the Three Lists approach. It clearly shows you understand the problem and preserves ordering without tricky edge cases. After that, discuss the in-place optimization. Interviewers like seeing the simple simulation first, followed by a space-optimized partition strategy that still achieves O(n) time.

Approach 1: Three Lists Approach

This approach involves creating three separate lists to hold elements less than, equal to, and greater than the pivot. After populating these lists based on the original array, we concatenate them to produce the final result, thereby satisfying the problem conditions.

def partition_array(nums, pivot):
    less = []
    equal = []
    greater = []
    for num in nums:
        if num < pivot:
            less.append(num)
        elif num == pivot:
            equal.append(num)
        else:
            greater.append(num)
    return less + equal + greater

nums = [9, 12, 5, 10, 14, 3, 10]
pivot = 10
result = partition_array(nums, pivot)
print(result)
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static List<Integer> partitionArray(int[] nums, int pivot) {
        List<Integer> less = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> greater = new ArrayList<>();
        for (int num : nums) {
            if (num < pivot)
                less.add(num);
            else if (num == pivot)
                equal.add(num);
            else
                greater.add(num);
        }
        less.addAll(equal);
        less.addAll(greater);
        return less;
    }

    public static void main(String[] args) {
        int[] nums = {9, 12, 5, 10, 14, 3, 10};
        int pivot = 10;
        List<Integer> result = partitionArray(nums, pivot);
        System.out.println(result);
    }
}
#include <iostream>
#include <vector>
using namespace std;

vector<int> partitionArray(vector<int>& nums, int pivot) {
    vector<int> less, equal, greater;
    for (int num : nums) {
        if (num < pivot) less.push_back(num);
        else if (num == pivot) equal.push_back(num);
        else greater.push_back(num);
    }
    less.insert(less.end(), equal.begin(), equal.end());
    less.insert(less.end(), greater.begin(), greater.end());
    return less;
}

int main() {
    vector<int> nums = {9, 12, 5, 10, 14, 3, 10};
    int pivot = 10;
    vector<int> result = partitionArray(nums, pivot);
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}
function partitionArray(nums, pivot) {
    let less = [], equal = [], greater = [];
    nums.forEach(num => {
        if (num < pivot) less.push(num);
        else if (num === pivot) equal.push(num);
        else greater.push(num);
    });
    return less.concat(equal).concat(greater);
}

const nums = [9, 12, 5, 10, 14, 3, 10];
const pivot = 10;
const result = partitionArray(nums, pivot);
console.log(result);
#include <stdio.h>
#include <stdlib.h>

void partitionArray(int* nums, int numsSize, int pivot, int* result) {
    int lessCount = 0, equalCount = 0, greaterCount = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < pivot) lessCount++;
        else if (nums[i] == pivot) equalCount++;
        else greaterCount++;
    }
    int less = 0, equal = lessCount, greater = lessCount + equalCount;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < pivot) result[less++] = nums[i];
        else if (nums[i] == pivot) result[equal++] = nums[i];
        else result[greater++] = nums[i];
    }
}

int main() {
    int nums[] = {9, 12, 5, 10, 14, 3, 10};
    int pivot = 10;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int* result = (int*)malloc(numsSize * sizeof(int));
    partitionArray(nums, numsSize, pivot, result);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", result[i]);
    }
    free(result);
    return 0;
}
using System;
using System.Collections.Generic;

class Program {
    static List<int> PartitionArray(int[] nums, int pivot) {
        var less = new List<int>();
        var equal = new List<int>();
        var greater = new List<int>();
        foreach (var num in nums) {
            if (num < pivot) less.Add(num);
            else if (num == pivot) equal.Add(num);
            else greater.Add(num);
        }
        less.AddRange(equal);
        less.AddRange(greater);
        return less;
    }

    static void Main() {
        int[] nums = {9, 12, 5, 10, 14, 3, 10};
        int pivot = 10;
        List<int> result = PartitionArray(nums, pivot);
        Console.WriteLine(string.Join(", ", result));
    }
}

This Python solution utilizes three lists to hold the numbers based on their comparison with the pivot, finally concatenating them to provide the ordered array.

Complexity

Time Complexity: O(n) for processing each element. Space Complexity: O(n) for the lists used.

Try this approach in the editor

Approach 2: In-Place Partitioning Approach

This in-place approach leverages a two-pointer technique to rearrange elements directly within the original array. One pointer manages the position of elements less than the pivot, while the other handles elements greater than the pivot. This approach reduces space complexity compared to the three lists approach.

def partition_array(nums, pivot):
    left, current, right = 0, 0, len(nums) - 1
    while current <= right:
        if nums[current] < pivot:
            nums[left], nums[current] = nums[current], nums[left]
            left += 1
            current += 1
        elif nums[current] > pivot:
            nums[current], nums[right] = nums[right], nums[current]
            right -= 1
        else:
            current += 1

nums = [9, 12, 5, 10, 14, 3, 10]
pivot = 10
partition_array(nums, pivot)
print(nums)
import java.util.Arrays;

public class Main {
    public static void partitionArray(int[] nums, int pivot) {
        int left = 0, current = 0, right = nums.length - 1;
        while (current <= right) {
            if (nums[current] < pivot) {
                int temp = nums[left];
                nums[left++] = nums[current];
                nums[current++] = temp;
            } else if (nums[current] > pivot) {
                int temp = nums[current];
                nums[current] = nums[right];
                nums[right--] = temp;
            } else {
                current++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {9, 12, 5, 10, 14, 3, 10};
        int pivot = 10;
        partitionArray(nums, pivot);
        System.out.println(Arrays.toString(nums));
    }
}
#include <iostream>
#include <vector>
using namespace std;

void partitionArray(vector<int>& nums, int pivot) {
    int left = 0, current = 0, right = nums.size() - 1;
    while (current <= right) {
        if (nums[current] < pivot) {
            swap(nums[left++], nums[current++]);
        } else if (nums[current] > pivot) {
            swap(nums[current], nums[right--]);
        } else {
            current++;
        }
    }
}

int main() {
    vector<int> nums = {9, 12, 5, 10, 14, 3, 10};
    int pivot = 10;
    partitionArray(nums, pivot);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}
function partitionArray(nums, pivot) {
    let left = 0, current = 0, right = nums.length - 1;
    while (current <= right) {
        if (nums[current] < pivot) {
            [nums[left], nums[current]] = [nums[current], nums[left]];
            left++;
            current++;
        } else if (nums[current] > pivot) {
            [nums[current], nums[right]] = [nums[right], nums[current]];
            right--;
        } else {
            current++;
        }
    }
}

let nums = [9, 12, 5, 10, 14, 3, 10];
let pivot = 10;
partitionArray(nums, pivot);
console.log(nums);
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void partitionArray(int* nums, int numsSize, int pivot) {
    int left = 0, current = 0, right = numsSize - 1;
    while (current <= right) {
        if (nums[current] < pivot) {
            swap(&nums[left], &nums[current]);
            left++; current++;
        } else if (nums[current] > pivot) {
            swap(&nums[current], &nums[right]);
            right--;
        } else {
            current++;
        }
    }
}

int main() {
    int nums[] = {9, 12, 5, 10, 14, 3, 10};
    int pivot = 10;
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    partitionArray(nums, numsSize, pivot);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}
using System;

class Program {
    static void PartitionArray(int[] nums, int pivot) {
        int left = 0, current = 0, right = nums.Length - 1;
        while (current <= right) {
            if (nums[current] < pivot) {
                (nums[left], nums[current]) = (nums[current], nums[left]);
                left++;
                current++;
            } else if (nums[current] > pivot) {
                (nums[current], nums[right]) = (nums[right], nums[current]);
                right--;
            } else {
                current++;
            }
        }
    }

    static void Main() {
        int[] nums = {9, 12, 5, 10, 14, 3, 10};
        int pivot = 10;
        PartitionArray(nums, pivot);
        Console.WriteLine(string.Join(", ", nums));
    }
}

This Python code effectively reorganizes the array in place by utilizing a two-pointer system, making swaps as needed based on comparison with the pivot value.

Complexity

Time Complexity: O(n) is achieved as a single traversal suffices. Space Complexity: O(1), as element swaps don't require extra storage aside from variables.

Try this approach in the editor

Approach 3: Simulation

We can traverse the array nums, sequentially finding all elements less than pivot, all elements equal to pivot, and all elements greater than pivot, then concatenate them in the order required by the problem.

Time complexity O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).

function pivotArray(nums: number[], pivot: number): number[] {
    const ans: number[] = [];
    for (const x of nums) {
        if (x < pivot) {
            ans.push(x);
        }
    }
    for (const x of nums) {
        if (x === pivot) {
            ans.push(x);
        }
    }
    for (const x of nums) {
        if (x > pivot) {
            ans.push(x);
        }
    }
    return ans;
}
func pivotArray(nums []int, pivot int) []int {
	var ans []int
	for _, x := range nums {
		if x < pivot {
			ans = append(ans, x)
		}
	}
	for _, x := range nums {
		if x == pivot {
			ans = append(ans, x)
		}
	}
	for _, x := range nums {
		if x > pivot {
			ans = append(ans, x)
		}
	}
	return ans
}
Try this approach in the editor

Approach 4: Two pointers

function pivotArray(nums: number[], pivot: number): number[] {
    const n = nums.length;
    const res = Array(n).fill(pivot);

    for (let i = 0, l = 0, j = n - 1, r = n - 1; i < n; i++, j--) {
        if (nums[i] < pivot) res[l++] = nums[i];
        if (nums[j] > pivot) res[r--] = nums[j];
    }

    return res;
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Three Lists Approach

Time Complexity: O(n) for processing each element. Space Complexity: O(n) for the lists used.

In-Place Partitioning Approach

Time Complexity: O(n) is achieved as a single traversal suffices. Space Complexity: O(1), as element swaps don't require extra storage aside from variables.

Simulation–
Two pointers–

Complexity analysis

ApproachTimeSpaceWhen to Use
Three Lists ApproachO(n)O(n)Best for clarity and interviews where extra memory is acceptable
In-Place PartitioningO(n)O(1)When memory usage matters or when demonstrating deeper array manipulation skills

Frequently asked questions

Is Partition Array According to Given Pivot easy or hard?

Partition Array According to Given Pivot is rated Medium difficulty. The logic is straightforward once you recognize the three-group partition structure, but the requirement to maintain relative order makes it slightly more involved than a basic partition problem.

Partition Array According to Given Pivot Python/Java solution

In Python or Java, iterate through the array and append each value to one of three lists depending on its relation to the pivot. After the loop, combine the lists in order. This implementation runs in O(n) time and keeps the relative order of elements intact.

How to solve Partition Array According to Given Pivot in O(n)?

Traverse the array once and classify every element relative to the pivot. Store elements smaller than the pivot in one list, equal elements in another, and greater elements in a third list. Concatenate the three lists to form the final result. This single-pass grouping ensures O(n) time complexity while preserving the original order.

What is the best approach for Partition Array According to Given Pivot?

The most practical approach is the Three Lists method. Iterate through the array once and place numbers into three groups: less than the pivot, equal to the pivot, and greater than the pivot. Concatenating these lists preserves relative order and runs in O(n) time with O(n) extra space. This approach is commonly used in interviews because it is simple and reliable.

Is Partition Array According to Given Pivot asked at Google/Amazon/Meta?

Array partitioning and pivot-based rearrangement are common interview themes at companies like Google, Amazon, and Meta. Variations of this idea also appear in quicksort partition questions and Dutch National Flag problems. Practicing this problem helps build intuition for those related interview questions.

What data structure is used in Partition Array According to Given Pivot?

The typical solution uses arrays or dynamic lists to store elements in three groups: less than, equal to, and greater than the pivot. Some implementations use pointer-based partitioning to perform the same operation in-place. The problem mainly tests array traversal, partition logic, and two-pointer techniques.

What is the time complexity of Partition Array According to Given Pivot?

The optimal solutions run in O(n) time. Each element in the array is processed exactly once while determining whether it belongs to the less-than, equal-to, or greater-than partition. Space complexity is O(n) for the three-lists approach and O(1) for the in-place partitioning variant.

Comments

Next problem · similarPartition ListMedium
Now write it yourselfClose this page and solve Partition Array According to Given Pivot in the editor, without looking.
Practise Partition Array According to Given Pivot