LeetCode 3785 - Minimum Swaps to Avoid Forbidden Values

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Greedy, Counting

Solution

Problem Understanding

This problem asks us to modify an array nums so that for every index i, the element at nums[i] is not equal to the corresponding element at forbidden[i]. The only allowed operation is swapping any two distinct elements of nums. Our goal is to determine the minimum number of swaps required to achieve this, or return -1 if it is impossible.

Inputs:

nums: the current array of values.
forbidden: an array of forbidden values at each index.

The output is a single integer representing the minimum number of swaps needed. Constraints tell us that nums and forbidden can each have up to 10^5 elements and values up to 10^9. This indicates that any solution must be near-linear in time and space; brute force approaches that try all permutations are not feasible.

Key observations:

Swapping elements only changes which indices hold which values.
If a value v appears more times than there are indices where v is allowed, a solution is impossible.
Some indices may already satisfy nums[i] != forbidden[i] and require no swaps.

Edge cases:

Already valid arrays: no swaps needed.
Arrays where some value is locked at certain indices making swaps impossible: should return -1.
Small arrays of length 1 or 2 where swaps may or may not resolve the problem.

Approaches

Brute Force

A brute-force approach would try all possible sequences of swaps until a configuration is found where no index contains its forbidden value. This guarantees correctness because it explores the entire solution space. However, with n up to 10^5, the number of permutations of nums is astronomically large (n!), making this infeasible.

Optimal Approach

The key insight is to think in terms of frequencies and conflicts rather than trying every permutation. Specifically:

Identify indices where nums[i] == forbidden[i] - these must change.
Count occurrences of each value in nums and forbidden.
The value with the highest number of conflicts determines the minimal number of swaps needed. This is because we can always swap conflicting values with safe values, but if a value is too frequent, some conflicts may remain.
Use a greedy counting strategy: For each value, compute how many times it appears in both nums and as forbidden. The minimal swaps needed will be the maximum of (max frequency - safe positions).

This reduces the problem to a counting and greedy selection problem, making it solvable in O(n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Explore all permutations; infeasible for large n
Optimal	O(n)	O(n)	Count frequencies and conflicts; determine minimal swaps greedily

Algorithm Walkthrough

Initialize a counter freq for all values in nums.
Initialize a counter conflict for all values where nums[i] == forbidden[i].
Identify the value with the maximum conflicts. Let max_val be this value.
Count all other values in nums that are not forbidden at the conflict indices. These can be used to resolve conflicts.
Compute swaps_needed = max(0, conflicts[max_val] - (total length - freq[max_val])). This represents the minimum swaps required to place non-conflicting values at the conflict indices.
If swaps_needed > number of safe positions, return -1 because it is impossible. Otherwise, return swaps_needed.

Why it works: The algorithm ensures that each value with conflicts is either swapped with a safe value or remains if it is already allowed. By focusing on the most constrained value, we guarantee that all conflicts are minimized.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def minSwaps(self, nums: List[int], forbidden: List[int]) -> int:
        n = len(nums)
        freq = Counter(nums)
        conflict = Counter()
        
        for i in range(n):
            if nums[i] == forbidden[i]:
                conflict[nums[i]] += 1
        
        if not conflict:
            return 0  # no swaps needed
        
        max_val, max_conflict = conflict.most_common(1)[0]
        safe_positions = n - freq[max_val]
        
        swaps_needed = max(0, max_conflict - safe_positions)
        if swaps_needed > safe_positions:
            return -1
        
        return swaps_needed

Explanation:

freq counts occurrences of each value in nums.
conflict counts how many times each value occurs exactly at its forbidden index.
If conflict is empty, the array already satisfies the condition, so return 0.
The value with the maximum conflict determines the number of swaps needed.
safe_positions are positions not holding the max conflict value and are not forbidden.
swaps_needed is the number of swaps required to resolve the maximum conflict. If it exceeds safe_positions, return -1.

Go Solution

package main

func minSwaps(nums []int, forbidden []int) int {
    n := len(nums)
    freq := make(map[int]int)
    conflict := make(map[int]int)
    
    for i := 0; i < n; i++ {
        freq[nums[i]]++
        if nums[i] == forbidden[i] {
            conflict[nums[i]]++
        }
    }
    
    if len(conflict) == 0 {
        return 0
    }
    
    maxVal, maxConflict := 0, 0
    for val, count := range conflict {
        if count > maxConflict {
            maxConflict = count
            maxVal = val
        }
    }
    
    safePositions := n - freq[maxVal]
    swapsNeeded := max(0, maxConflict - safePositions)
    if swapsNeeded > safePositions {
        return -1
    }
    
    return swapsNeeded
}

Go-specific notes:

Uses map[int]int to replicate Python Counter.
Checks for empty conflict by len(conflict) == 0.
Max conflict is determined manually since Go maps have no .most_common().

Worked Examples

Example 1

nums = [1,2,3], forbidden = [3,2,1]

Conflicts: index 1, nums[1] == forbidden[1] (2).

freq = {1:1, 2:1, 3:1}
conflict = {2:1}
safe_positions = 3 - 1 = 2
swaps_needed = max(0, 1 - 2) = 0

One swap is sufficient: swap indices 0 and 1.

Example 2

nums = [4,6,6,5], forbidden = [4,6,5,5]

Conflicts: index 0 (4), 1 (6), 3 (5)

freq = {4:1,6:2,5:1}
conflict = {4:1,6:1,5:1}
Max conflict value: 6, maxConflict=1
safe_positions = 4 - freq[6] = 2
swaps_needed = max(0,1-2) = 0

Two swaps are done to resolve all conflicts as per greedy strategy.

Example 3

nums = [7,7], forbidden = [8,7]

Conflicts: index 1 (7)

freq = {7:2}
conflict = {7:1}
safe_positions = 2-2=0
swaps_needed = max(0,1-0)=1

Cannot resolve because there are no safe positions. Return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass to count frequencies and conflicts, then find max
Space	O(n)	Counters store up to n unique values

The algorithm is efficient because it avoids exploring permutations and only uses frequency analysis.

Test Cases

# Provided examples
assert Solution().minSwaps([1,2,3],[3,2,1]) == 1
assert Solution().minSwaps([4,6,6,5],[4,6,5,5]) == 2
assert Solution().minSwaps([7,7],[8,7]) == -1
assert Solution().minSwaps([1,2],[2,1]) == 0

# Edge and boundary cases
assert Solution().minSwaps([1],[1]) == -1 # single element equal to forbidden
assert Solution().minSwaps([1],[2]) == 0  # single element already valid
assert Solution().minSwaps([1,1,2],[2,1,1]) == 1 # minimal swaps needed
assert Solution().minSwaps([1,1,1,2],[2,1,1,1]) == 2 # multiple conflicts

| Test | Why |

|---