LeetCode Entry

3011. Find if Array Can Be Sorted

06.11.2024 medium 2024 kotlin rust

Can array be sorted by adjacent swap same-1-bits-nums

3011. Find if Array Can Be Sorted medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/792

Problem TLDR

Can array be sorted by adjacent swap same-1-bits-nums #medium

Intuition

Pay attention to the adjacent requirement, as it simplifies the problem: split nums by chunks and check for overlaps. (it’s note to myself as I spent time in the wrong direction)

The follow up of this problem would be removing the adjacent rule, now it becomes interesting:

    //          b
    // 0001  1  1
    // 0010  2  1
    // 0011  3  2
    // 0100  4  1
    // 0101  5  2

    // 42513
    // 11212   1: 1,2,4  2: 3,5
    //
    // 1     take smallest from `1`-b busket
    //  2
    //   3
    //    4
    //     5
    // adjucent!! < -- this is a different problem

We would have at most 8 buckets of the sorted numbers that we can hold in a PriorityQueue, for example:

        val g = nums.groupBy { it.countOneBits() }
            .mapValues { PriorityQueue(it.value) }
        var prev = 0
        return nums.none { n ->
            val n = g[n.countOneBits()]!!.poll()
            n < prev.also { prev = n }
        }

Approach

• read the description carefully
• sometimes the problem size (just 100 elements) didn’t hint about the actual solution

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    fun canSortArray(nums: IntArray): Boolean {
        var prevMax = 0; var b = 0; var max = 0
        return nums.none { n ->
            val bits = n.countOneBits()
            if (bits != b) { prevMax = max; b = bits }
            max = max(max, n)
            n < prevMax
        }
    }

    pub fn can_sort_array(nums: Vec<i32>) -> bool {
        nums.chunk_by(|a, b| a.count_ones() == b.count_ones())
        .map(|c|(c.iter().min(), c.iter().max()))
        .collect::<Vec<_>>()
        .windows(2).all(|w| w[0].1 < w[1].0)
    }

    bool canSortArray(vector<int>& nums) {
        int bp = 0, mp = 0, m = 0;
        return none_of(begin(nums), end(nums), [&](int x) {
            int b = __builtin_popcount(x);
            if (b != bp) mp = m, bp = b;
            m = max(m, x);
            return x < mp;
        });
    }