LeetCode Entry

2161. Partition Array According to Given Pivot

03.03.2025 medium 2025 kotlin rust

Partition around p

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

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;
    }