LeetCode 3644: Maximum K to Sort a Permutation

Maximum K to Sort a Permutation (LeetCode 3644), explained properly in 8:08. Two values may swap only when their bitwise AND is exactly k. Find the largest k that still lets you sort the permutation. The pattern: Only the movers matter. The rule limits which pairs may swap, and asks for the best rule that still sorts. A number already at its own index never has to move. So the question is only about the numbers that are out of place, and what they all have in common. 1. Every value that is out of place must take part in at least one swap, so k can only use bits that every misplaced value has. 2. The largest number whose bits sit inside all of them is their AND. 3. That AND always works: the value equal to k ANDs to exactly k with every misplaced value, so it can ferry each one home. We build up 3 approaches, in the order you would actually reach them in an interview: 1. Try every k 2. Test the misplaced 3. AND the misplaced Final answer: AND the Misplaced Values — O(n) time, O(1) space. 🔗 Problem: https://leetcode.com/problems/maximum... CHAPTERS 0:00 Intro 0:25 The problem 1:22 How to think about it 4:47 Approach 1: Try every k 5:53 Approach 2: Test the misplaced 6:41 Approach 3: AND the misplaced 7:19 Recap 7:42 Outro #LeetCode #CodingInterview #DSA #Algorithms