Minimum Swaps to Avoid Forbidden Values solution and explanation
9 more videos on this problem
Leetcode Weekly Contest 481 || Q3. Minimum Swaps to Avoid Forbidden Values || Pigeonhole || Watch2X🚀Rajan Keshari ( CSE - IIT Dhanbad ) · 10:25 · 1K views
Minimum Swaps to Avoid Forbidden Values | LeetCode 3785 | Weekly Contest 481Sanyam IIT Guwahati · 20:06 · 1K views
Minimum Swaps to Avoid Forbidden Values 🔥 LeetCode 3785 | Weekly Contest 481 | Hard Problem Study Placement · 15:00 · 677 views
Leetcode 3785 | Minimum Swaps to Avoid Forbidden Values | Leetcode Weekly Contest 481CodeWithMeGuys · 14:30 · 421 views
LeetCode Weekly Contest 481 | Minimum Swaps to Avoid Forbidden Values | 3785 ExplainedDSA with Kumar K · 42:52 · 416 views
Leetcode 3785. Minimum Swaps to Avoid Forbidden Values | Greedy | O(N) | HardLeet's Code · 26:37 · 171 views
3785. Minimum Swaps to Avoid Forbidden Values (Leetcode Hard)Programming Live with Larry · 39:11 · 96 views
3785. Minimum Swaps to Avoid Forbidden Values LeetCode Weekly 481 Easiest Approach C++BEASTCODES · 18:58 · 59 views
LeetCode Weekly Contest 481 | 3785. Minimum Swaps to Avoid Forbidden Values | Optimal SolutionDesiCoding · 25:59 · 39 views
3785. Leetcode. Minimum swaps to avoid forbidden values Aryan · 40:16 · 20 views
The problem
You are given two integer arrays, nums and forbidden, each of length n.
You may perform the following operation any number of times (including zero):
- Choose two distinct indices
iandj, and swapnums[i]withnums[j].
Return the minimum number of swaps required such that, for every index i, the value of nums[i] is not equal to forbidden[i]. If no amount of swaps can ensure that every index avoids its forbidden value, return -1.
Example 1:
Input: nums = [1,2,3], forbidden = [3,2,1]
Output: 1
Explanation:
One optimal set of swaps:
- Select indices
i = 0andj = 1innumsand swap them, resulting innums = [2, 1, 3]. - After this swap, for every index
i,nums[i]is not equal toforbidden[i].
Example 2:
Input: nums = [4,6,6,5], forbidden = [4,6,5,5]
Output: 2
Explanation:
One optimal set of swaps:- Select indices
i = 0andj = 2innumsand swap them, resulting innums = [6, 6, 4, 5]. - Select indices
i = 1andj = 3innumsand swap them, resulting innums = [6, 5, 4, 6]. - After these swaps, for every index
i,nums[i]is not equal toforbidden[i].
Example 3:
Input: nums = [7,7], forbidden = [8,7]
Output: -1
Explanation:
It is not possible to makenums[i] different from forbidden[i] for all indices.Example 4:
Input: nums = [1,2], forbidden = [2,1]
Output: 0
Explanation:
No swaps are required because nums[i] is already different from forbidden[i] for all indices, so the answer is 0.
Constraints:
1 <= n == nums.length == forbidden.length <= 1051 <= nums[i], forbidden[i] <= 109
Approach overview
Problem Overview: You are given an array and a list of forbidden values for each index. The goal is to rearrange the array using the minimum number of swaps so that nums[i] never equals the forbidden value for that position. If multiple positions violate the rule, you must strategically swap elements so both indices become valid.
Approach 1: Brute Force Swap Checking (O(n²) time, O(1) space)
Scan the array and collect indices where nums[i] equals the forbidden value. For every such index i, try swapping with every other index j and check whether both positions become valid after the swap. This requires simulating swaps and validating conditions repeatedly. The approach works for small inputs but becomes slow because every bad position may attempt up to n candidate swaps. It’s mainly useful to understand the constraints before optimizing.
Approach 2: Greedy with Hash Counting (O(n) time, O(n) space)
Track positions where the constraint is violated using a simple scan. Maintain a frequency map of values and record indices where nums[i] == forbidden[i]. The key insight: a swap fixes two positions if each element is acceptable in the other’s index. Using a hash table, quickly locate candidate indices whose values resolve the conflict. Pair up incompatible positions greedily so one swap fixes both. When direct pairing isn’t possible, route through an intermediate index whose value is valid in both positions. This reduces unnecessary swaps and guarantees minimal operations in most cases.
Approach 3: Counting Conflicts and Cycle Resolution (O(n) time, O(n) space)
Model the problem as a mismatch graph. Each index with a forbidden conflict points to the position where its value can legally go. These mappings form cycles similar to permutation correction. Using ideas from array rearrangement and greedy placement, each cycle of length k requires k-1 swaps. Build a mapping from values to indices and resolve cycles while marking visited nodes. This method guarantees minimal swaps because every swap moves an element closer to a valid position.
Recommended for interviews: The greedy counting or cycle-based solution is what interviewers expect. Brute force demonstrates the core constraint—identifying forbidden matches—but it does not scale. The optimal solution shows that you recognize the structure of mismatches and reduce the problem to pairing or resolving permutation cycles in linear time.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Swap Checking | O(n²) | O(1) | Useful for understanding constraints or very small arrays |
| Greedy with Hash Counting | O(n) | O(n) | General case; quickly pairs conflicting positions using hash lookups |
| Cycle Resolution on Mismatches | O(n) | O(n) | Best when swaps form permutation-like cycles and minimal swaps must be guaranteed |
Frequently asked questions
Is Minimum Swaps to Avoid Forbidden Values easy or hard?
Minimum Swaps to Avoid Forbidden Values is typically classified as a hard problem because it combines greedy reasoning, counting conflicts, and permutation-style cycle resolution. Recognizing that swaps correspond to cycles is the main challenge.
Minimum Swaps to Avoid Forbidden Values Python/Java solution
Most implementations iterate through the array, store conflicting indices, and use a hash map to locate valid swap targets. The same logic translates directly across Python, Java, C++, and Go with O(n) time complexity.
How to solve Minimum Swaps to Avoid Forbidden Values in O(n)?
First record all indices where nums[i] equals the forbidden value. Use a hash map from values to indices to find swap partners that resolve two conflicts simultaneously. If conflicts form dependency chains, resolve them as permutation cycles where a cycle of length k requires k-1 swaps.
What is the best approach for Minimum Swaps to Avoid Forbidden Values?
The most efficient solution uses a greedy strategy with hash table tracking or cycle detection. Identify indices where nums[i] equals the forbidden value, then swap elements so both positions become valid. This approach runs in O(n) time with O(n) auxiliary space.
Is Minimum Swaps to Avoid Forbidden Values asked at Google/Amazon/Meta?
Problems involving minimum swaps, derangements, and conflict resolution appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve avoiding specific positions or minimizing swaps while respecting constraints.
What data structure is used in Minimum Swaps to Avoid Forbidden Values?
Hash tables are commonly used to map values to indices and quickly find valid swap partners. Arrays or visited sets help track processed positions when resolving cycles in the mismatch graph.
What is the time complexity of Minimum Swaps to Avoid Forbidden Values?
The optimal solution runs in O(n) time because the array is scanned once to detect conflicts and each index participates in at most one swap or cycle resolution. Extra storage such as a hash map or visited array requires O(n) space.