# 03.03.2025 [2161. Partition Array According to Given Pivot]

Partition around p #medium

03.03.2025

2161. Partition Array According to Given Pivot medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/913

Problem TLDR

Partition around p #medium

Intuition

In-place solution is possible, but O(nlog(n)). Otherwise, there are two-pass solution with two pointers tracking, or 3-pass with a single pointer.

Approach

• golf it in Kotlin

• in-place in Rust

• 2-pass in C++

Complexity

• Time complexity: $$O(n)$$, or NlogN for sorting

• Space complexity: $$O(n)$$, or O(1) for in-place sorting

Code

    fun pivotArray(n: IntArray, p: Int) =
        n.filter { it < p } + n.filter { it == p } + n.filter { it > p }

    pub fn pivot_array(mut n: Vec<i32>, p: i32) -> Vec<i32> {
        n.sort_by_key(|&x| x.cmp(&p)); n
    }

    vector<int> pivotArray(vector<int>& a, int p) {
        int n = size(a), i = 0; vector<int> r(n); 
        for (auto& x: a) if (x < p) r[i++] = x; else n -= x > p;
        while (i < n) r[i++] = p;
        for (auto& x: a) if (x > p) r[i++] = x;
        return r;
    }