LeetCode Entry
2471. Minimum Number of Operations to Sort a Binary Tree by Level
Min swaps to sort tree layers
2471. Minimum Number of Operations to Sort a Binary Tree by Level medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/841
Problem TLDR
Min swaps to sort tree layers #medium #cycle-sort #bfs
Intuition
Can’t solve without a hint. The hint: cycle-sort has optimal swaps count.
// 0 1 2 3 4 5
// 4 5 1 0 3 2
// 0 4
// 1 5
// 2 5
// 3 4
//
// 7 6 5 4
// 0 1 2 3
// 3 2 1 0
To do the cycle-sort, we convert the layer numbers into indices sorted accordingly, then do swap(ix[i], ix[ix[i]]) until all indices at their places.
Approach
- we can use a hashmap or just an array for indices to value mapping
Complexity
-
Time complexity: \(O(nlog(n))\) to sort layers
-
Space complexity: \(O(n)\)
Code
fun minimumOperations(root: TreeNode?): Int {
val q = ArrayDeque<TreeNode>(listOf(root ?: return 0))
var res = 0
while (q.size > 0) {
val s = ArrayList<Int>()
repeat(q.size) {
val n = q.removeFirst(); s += n.`val`
n.left?.let { q += it }; n.right?.let { q += it }
}
val ix = s.indices.sortedBy { s[it] }.toIntArray()
for (i in 0..<ix.size) while (ix[i] != i) {
ix[i] = ix[ix[i]].also { ix[ix[i]] = ix[i] }; res++
}
}
return res
}
pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let Some(r) = root else { return 0 };
let (mut q, mut r) = (VecDeque::from([r]), 0);
while q.len() > 0 {
let mut s = vec![];
for _ in 0..q.len() {
let n = q.pop_front().unwrap(); let n = n.borrow(); s.push(n.val);
if let Some(n) = n.left.clone() { q.push_back(n) }
if let Some(n) = n.right.clone() { q.push_back(n) }
}
let mut ix: Vec<_> = (0..s.len()).collect();
ix.sort_unstable_by_key(|&i| s[i]);
for i in 0..ix.len() { while ix[i] != i {
let t = ix[i]; ix[i] = ix[t]; ix[t] = t; r += 1
}}
}; r
}
int minimumOperations(TreeNode* root) {
int r = 0; vector<TreeNode*> q{root};
while (q.size()) {
vector<TreeNode*> q1; vector<int> s, ix(q.size());
for (auto n: q) {
s.push_back(n->val);
if (n->left) q1.push_back(n->left);
if (n->right) q1.push_back(n->right);
}
iota(begin(ix), end(ix), 0);
sort(begin(ix), end(ix), [&](int i, int j){ return s[i] < s[j];});
for (int i = 0; i < ix.size(); ++i) for (; ix[i] != i; ++r)
swap(ix[i], ix[ix[i]]);
swap(q, q1);
} return r;
}