LeetCode Entry

3644. Maximum K to Sort a Permutation

23.10.2026 medium 2026 kotlin rust

Max K to sort by swapping a&b=k

3644. Maximum K to Sort a Permutation medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1520

Problem TLDR

Max K to sort by swapping a&b=k

Intuition

Each unsorted position forms a cycle island. Walk the cycle and do the ‘and’ operation. Then join the islands with ‘and’ operation.

Approach

• we don’t have to walk islands, it is just all unsorted positions’s ‘and’ operation

Complexity

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

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

Code

    fun sortPermutation(n: IntArray) =
    n.filterIndexed{i,v->v!=i}.reduceOrNull(Int::and)?:0

    pub fn sort_permutation(n: Vec<i32>) -> i32 {
        let mut r=-1;for(i,v)in(0..).zip(n){if v!=i{r&=v}}r.max(0)
    }