Stable Marriage Problem

Problem

The stable marriage problem is defined as follows:

Suppose you have N men and N women, and each person has ranked their prospective opposite-sex partners in order of preference.

For example, if N = 3, the input could be something like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


guy_preferences = {
    'andrew': ['caroline', 'abigail', 'betty'],
    'bill': ['caroline', 'betty', 'abigail'],
    'chester': ['betty', 'caroline', 'abigail'],
}
gal_preferences = {
    'abigail': ['andrew', 'bill', 'chester'],
    'betty': ['bill', 'andrew', 'chester'],
    'caroline': ['bill', 'chester', 'andrew']
}

Write an algorithm that pairs the men and women together in such a way that no two people of opposite sex would both rather be with each other than with their current partners.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


Input: 
guy_preferences = {
    'andrew': ['caroline', 'abigail', 'betty'],
    'bill': ['caroline', 'betty', 'abigail'],
    'chester': ['betty', 'caroline', 'abigail']
}
gal_preferences = {
    'abigail': ['andrew', 'bill', 'chester'],
    'betty': ['bill', 'andrew', 'chester'],
    'caroline': ['bill', 'chester', 'andrew']
}

Output: {('andrew', 'abigail'), ('bill', 'caroline'), ('chester', 'betty')}

Explanation:
- andrew gets abigail (his 2nd choice, her 1st choice)
- bill gets caroline (his 1st choice, her 1st choice)  
- chester gets betty (his 1st choice, her 2nd choice)
This is stable - no pair would prefer each other over current partners.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input:
guy_preferences = {
    'A': ['X', 'Y'],
    'B': ['Y', 'X']
}
gal_preferences = {
    'X': ['A', 'B'],
    'Y': ['B', 'A']
}

Output: {('A', 'X'), ('B', 'Y')}

Explanation:
- A gets X (his 1st choice, her 1st choice)
- B gets Y (his 1st choice, her 1st choice)
Perfect matching where everyone gets their first choice.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


Input:
guy_preferences = {
    'M1': ['W1', 'W2', 'W3'],
    'M2': ['W2', 'W1', 'W3'],
    'M3': ['W1', 'W2', 'W3']
}
gal_preferences = {
    'W1': ['M2', 'M3', 'M1'],
    'W2': ['M1', 'M3', 'M2'],
    'W3': ['M1', 'M2', 'M3']
}

Output: {('M1', 'W2'), ('M2', 'W1'), ('M3', 'W3')}

Explanation:
Gale-Shapley algorithm finds stable matching where:
- M1 gets W2 (his 2nd choice, her 1st choice)
- M2 gets W1 (his 2nd choice, her 1st choice)  
- M3 gets W3 (his 3rd choice, her 1st choice)

Example 4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input:
guy_preferences = {
    'G1': ['W1'],
    'G2': ['W2']
}
gal_preferences = {
    'W1': ['G1'],
    'W2': ['G2']
}

Output: {('G1', 'W1'), ('G2', 'W2')}

Explanation:
Simple case where everyone has only one choice, leading to obvious stable matching.

Example 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


Input:
guy_preferences = {
    'Alpha': ['One', 'Two', 'Three', 'Four'],
    'Beta': ['Two', 'One', 'Four', 'Three'],
    'Gamma': ['Three', 'Four', 'One', 'Two'],
    'Delta': ['Four', 'Three', 'Two', 'One']
}
gal_preferences = {
    'One': ['Beta', 'Alpha', 'Gamma', 'Delta'],
    'Two': ['Alpha', 'Beta', 'Gamma', 'Delta'],
    'Three': ['Gamma', 'Delta', 'Alpha', 'Beta'],
    'Four': ['Delta', 'Gamma', 'Beta', 'Alpha']
}

Output: {('Alpha', 'Two'), ('Beta', 'One'), ('Gamma', 'Three'), ('Delta', 'Four')}

Explanation:
Complex 4x4 matching demonstrating the algorithm's ability to handle larger preference matrices.

Solution

Method 1 - Gale-Shapley Algorithm

Intuition

The Gale-Shapley algorithm solves the stable marriage problem by having men propose to women in order of their preferences. Women tentatively accept the best proposal they’ve received so far, rejecting previous proposals if they get a better one. The algorithm guarantees a stable matching where no pair of people would prefer each other over their current partners.

Approach

Initialize all men as free and all women as free
Create preference rankings for quick lookup of preferences
While there exists a free man:
- The free man proposes to the woman he prefers most among those he hasn’t proposed to yet
- If the woman is free, she accepts tentatively
- If the woman is already engaged, she compares the new proposer with her current partner
- If she prefers the new proposer, she breaks the current engagement and accepts the new proposal
- The rejected man becomes free again
Continue until all men are matched
Return the final stable matching

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


class Solution {
public:
    vector<pair<string, string>> stableMarriage(
        unordered_map<string, vector<string>>& guyPrefs,
        unordered_map<string, vector<string>>& galPrefs) {
        
        int n = guyPrefs.size();
        
        // Create preference rankings for quick lookup
        unordered_map<string, unordered_map<string, int>> galRankings;
        for (auto& [gal, prefs] : galPrefs) {
            for (int i = 0; i < prefs.size(); i++) {
                galRankings[gal][prefs[i]] = i;
            }
        }
        
        // Track current proposals and engagements
        unordered_map<string, int> guyNextProposal;
        unordered_map<string, string> galPartner;
        unordered_map<string, string> guyPartner;
        queue<string> freeGuys;
        
        // Initialize all guys as free
        for (auto& [guy, _] : guyPrefs) {
            freeGuys.push(guy);
            guyNextProposal[guy] = 0;
        }
        
        while (!freeGuys.empty()) {
            string guy = freeGuys.front();
            freeGuys.pop();
            
            string gal = guyPrefs[guy][guyNextProposal[guy]];
            guyNextProposal[guy]++;
            
            if (galPartner.find(gal) == galPartner.end()) {
                // Gal is free, accept proposal
                galPartner[gal] = guy;
                guyPartner[guy] = gal;
            } else {
                // Gal is engaged, check if she prefers new guy
                string currentPartner = galPartner[gal];
                if (galRankings[gal][guy] < galRankings[gal][currentPartner]) {
                    // Gal prefers new guy
                    galPartner[gal] = guy;
                    guyPartner[guy] = gal;
                    guyPartner.erase(currentPartner);
                    freeGuys.push(currentPartner);
                } else {
                    // Gal prefers current partner, guy remains free
                    freeGuys.push(guy);
                }
            }
        }
        
        vector<pair<string, string>> result;
        for (auto& [guy, gal] : guyPartner) {
            result.push_back({guy, gal});
        }
        
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


func stableMarriage(guyPrefs map[string][]string, galPrefs map[string][]string) [][]string {
    n := len(guyPrefs)
    
    // Create preference rankings for quick lookup
    galRankings := make(map[string]map[string]int)
    for gal, prefs := range galPrefs {
        galRankings[gal] = make(map[string]int)
        for i, guy := range prefs {
            galRankings[gal][guy] = i
        }
    }
    
    // Track current proposals and engagements
    guyNextProposal := make(map[string]int)
    galPartner := make(map[string]string)
    guyPartner := make(map[string]string)
    var freeGuys []string
    
    // Initialize all guys as free
    for guy := range guyPrefs {
        freeGuys = append(freeGuys, guy)
        guyNextProposal[guy] = 0
    }
    
    for len(freeGuys) > 0 {
        guy := freeGuys[0]
        freeGuys = freeGuys[1:]
        
        gal := guyPrefs[guy][guyNextProposal[guy]]
        guyNextProposal[guy]++
        
        currentPartner, galIsEngaged := galPartner[gal]
        
        if !galIsEngaged {
            // Gal is free, accept proposal
            galPartner[gal] = guy
            guyPartner[guy] = gal
        } else {
            // Gal is engaged, check if she prefers new guy
            if galRankings[gal][guy] < galRankings[gal][currentPartner] {
                // Gal prefers new guy
                galPartner[gal] = guy
                guyPartner[guy] = gal
                delete(guyPartner, currentPartner)
                freeGuys = append(freeGuys, currentPartner)
            } else {
                // Gal prefers current partner, guy remains free
                freeGuys = append(freeGuys, guy)
            }
        }
    }
    
    var result [][]string
    for guy, gal := range guyPartner {
        result = append(result, []string{guy, gal})
    }
    
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


class Solution {
    public List<List<String>> stableMarriage(
            Map<String, List<String>> guyPrefs,
            Map<String, List<String>> galPrefs) {
        
        int n = guyPrefs.size();
        
        // Create preference rankings for quick lookup
        Map<String, Map<String, Integer>> galRankings = new HashMap<>();
        for (Map.Entry<String, List<String>> entry : galPrefs.entrySet()) {
            String gal = entry.getKey();
            List<String> prefs = entry.getValue();
            Map<String, Integer> rankings = new HashMap<>();
            for (int i = 0; i < prefs.size(); i++) {
                rankings.put(prefs.get(i), i);
            }
            galRankings.put(gal, rankings);
        }
        
        // Track current proposals and engagements
        Map<String, Integer> guyNextProposal = new HashMap<>();
        Map<String, String> galPartner = new HashMap<>();
        Map<String, String> guyPartner = new HashMap<>();
        Queue<String> freeGuys = new LinkedList<>();
        
        // Initialize all guys as free
        for (String guy : guyPrefs.keySet()) {
            freeGuys.offer(guy);
            guyNextProposal.put(guy, 0);
        }
        
        while (!freeGuys.isEmpty()) {
            String guy = freeGuys.poll();
            String gal = guyPrefs.get(guy).get(guyNextProposal.get(guy));
            guyNextProposal.put(guy, guyNextProposal.get(guy) + 1);
            
            if (!galPartner.containsKey(gal)) {
                // Gal is free, accept proposal
                galPartner.put(gal, guy);
                guyPartner.put(guy, gal);
            } else {
                // Gal is engaged, check if she prefers new guy
                String currentPartner = galPartner.get(gal);
                if (galRankings.get(gal).get(guy) < galRankings.get(gal).get(currentPartner)) {
                    // Gal prefers new guy
                    galPartner.put(gal, guy);
                    guyPartner.put(guy, gal);
                    guyPartner.remove(currentPartner);
                    freeGuys.offer(currentPartner);
                } else {
                    // Gal prefers current partner, guy remains free
                    freeGuys.offer(guy);
                }
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        for (Map.Entry<String, String> entry : guyPartner.entrySet()) {
            result.add(Arrays.asList(entry.getKey(), entry.getValue()));
        }
        
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


from collections import deque
from typing import Dict, List, Tuple

class Solution:
    def stable_marriage(self, guy_prefs: Dict[str, List[str]], 
                       gal_prefs: Dict[str, List[str]]) -> List[Tuple[str, str]]:
        n = len(guy_prefs)
        
        # Create preference rankings for quick lookup
        gal_rankings = {}
        for gal, prefs in gal_prefs.items():
            gal_rankings[gal] = {guy: i for i, guy in enumerate(prefs)}
        
        # Track current proposals and engagements
        guy_next_proposal = {guy: 0 for guy in guy_prefs}
        gal_partner = {}
        guy_partner = {}
        free_guys = deque(guy_prefs.keys())
        
        while free_guys:
            guy = free_guys.popleft()
            gal = guy_prefs[guy][guy_next_proposal[guy]]
            guy_next_proposal[guy] += 1
            
            if gal not in gal_partner:
                # Gal is free, accept proposal
                gal_partner[gal] = guy
                guy_partner[guy] = gal
            else:
                # Gal is engaged, check if she prefers new guy
                current_partner = gal_partner[gal]
                if gal_rankings[gal][guy] < gal_rankings[gal][current_partner]:
                    # Gal prefers new guy
                    gal_partner[gal] = guy
                    guy_partner[guy] = gal
                    del guy_partner[current_partner]
                    free_guys.append(current_partner)
                else:
                    # Gal prefers current partner, guy remains free
                    free_guys.append(guy)
        
        return [(guy, gal) for guy, gal in guy_partner.items()]

Complexity

⏰ Time complexity: O(N²), where N is the number of men/women. In worst case, each man proposes to all women once
🧺 Space complexity: O(N²), for storing preference rankings and tracking engagements

Method 2 - Irving’s Algorithm with Stability Verification

Intuition

This approach implements the Gale-Shapley algorithm with explicit stability verification. After finding a matching, we verify that no blocking pairs exist - pairs where both individuals prefer each other over their current partners. This provides additional confidence in the solution’s correctness.

Approach

Run the standard Gale-Shapley algorithm to find a matching
After getting the initial matching, verify stability by checking all possible pairs
For each unmatched pair (m, w), check if both m prefers w over his current partner AND w prefers m over her current partner
If such a blocking pair exists, the matching is unstable (this should never happen with correct Gale-Shapley)
Return the verified stable matching along with stability confirmation

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117


class Solution {
public:
    pair<vector<pair<string, string>>, bool> stableMarriageWithVerification(
        unordered_map<string, vector<string>>& guyPrefs,
        unordered_map<string, vector<string>>& galPrefs) {
        
        // First, find matching using Gale-Shapley
        auto matching = galeShapley(guyPrefs, galPrefs);
        
        // Convert to maps for easier verification
        unordered_map<string, string> guyToGal, galToGuy;
        for (auto& [guy, gal] : matching) {
            guyToGal[guy] = gal;
            galToGuy[gal] = guy;
        }
        
        // Verify stability
        bool isStable = verifyStability(guyPrefs, galPrefs, guyToGal, galToGuy);
        
        return {matching, isStable};
    }
    
private:
    vector<pair<string, string>> galeShapley(
        unordered_map<string, vector<string>>& guyPrefs,
        unordered_map<string, vector<string>>& galPrefs) {
        
        // Create preference rankings
        unordered_map<string, unordered_map<string, int>> galRankings;
        for (auto& [gal, prefs] : galPrefs) {
            for (int i = 0; i < prefs.size(); i++) {
                galRankings[gal][prefs[i]] = i;
            }
        }
        
        unordered_map<string, int> guyNextProposal;
        unordered_map<string, string> galPartner, guyPartner;
        queue<string> freeGuys;
        
        for (auto& [guy, _] : guyPrefs) {
            freeGuys.push(guy);
            guyNextProposal[guy] = 0;
        }
        
        while (!freeGuys.empty()) {
            string guy = freeGuys.front();
            freeGuys.pop();
            
            string gal = guyPrefs[guy][guyNextProposal[guy]];
            guyNextProposal[guy]++;
            
            if (galPartner.find(gal) == galPartner.end()) {
                galPartner[gal] = guy;
                guyPartner[guy] = gal;
            } else {
                string currentPartner = galPartner[gal];
                if (galRankings[gal][guy] < galRankings[gal][currentPartner]) {
                    galPartner[gal] = guy;
                    guyPartner[guy] = gal;
                    guyPartner.erase(currentPartner);
                    freeGuys.push(currentPartner);
                } else {
                    freeGuys.push(guy);
                }
            }
        }
        
        vector<pair<string, string>> result;
        for (auto& [guy, gal] : guyPartner) {
            result.push_back({guy, gal});
        }
        return result;
    }
    
    bool verifyStability(unordered_map<string, vector<string>>& guyPrefs,
                        unordered_map<string, vector<string>>& galPrefs,
                        unordered_map<string, string>& guyToGal,
                        unordered_map<string, string>& galToGuy) {
        
        // Create rankings for efficient preference comparison
        unordered_map<string, unordered_map<string, int>> guyRankings, galRankings;
        
        for (auto& [guy, prefs] : guyPrefs) {
            for (int i = 0; i < prefs.size(); i++) {
                guyRankings[guy][prefs[i]] = i;
            }
        }
        
        for (auto& [gal, prefs] : galPrefs) {
            for (int i = 0; i < prefs.size(); i++) {
                galRankings[gal][prefs[i]] = i;
            }
        }
        
        // Check for blocking pairs
        for (auto& [guy, guyPrefList] : guyPrefs) {
            for (auto& [gal, galPrefList] : galPrefs) {
                if (guyToGal[guy] == gal) continue;  // Already matched
                
                string guyCurrentPartner = guyToGal[guy];
                string galCurrentPartner = galToGuy[gal];
                
                // Check if guy prefers gal over his current partner
                bool guyPrefers = guyRankings[guy][gal] < guyRankings[guy][guyCurrentPartner];
                
                // Check if gal prefers guy over her current partner
                bool galPrefers = galRankings[gal][guy] < galRankings[gal][galCurrentPartner];
                
                if (guyPrefers && galPrefers) {
                    return false;  // Blocking pair found
                }
            }
        }
        
        return true;  // No blocking pairs found
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


class Solution:
    def stable_marriage_with_verification(self, guy_prefs: Dict[str, List[str]], 
                                        gal_prefs: Dict[str, List[str]]) -> Tuple[List[Tuple[str, str]], bool]:
        # Find matching using Gale-Shapley
        matching = self._gale_shapley(guy_prefs, gal_prefs)
        
        # Convert to maps for easier verification
        guy_to_gal = {guy: gal for guy, gal in matching}
        gal_to_guy = {gal: guy for guy, gal in matching}
        
        # Verify stability
        is_stable = self._verify_stability(guy_prefs, gal_prefs, guy_to_gal, gal_to_guy)
        
        return matching, is_stable
    
    def _gale_shapley(self, guy_prefs: Dict[str, List[str]], 
                     gal_prefs: Dict[str, List[str]]) -> List[Tuple[str, str]]:
        # Create preference rankings
        gal_rankings = {}
        for gal, prefs in gal_prefs.items():
            gal_rankings[gal] = {guy: i for i, guy in enumerate(prefs)}
        
        guy_next_proposal = {guy: 0 for guy in guy_prefs}
        gal_partner = {}
        guy_partner = {}
        free_guys = deque(guy_prefs.keys())
        
        while free_guys:
            guy = free_guys.popleft()
            gal = guy_prefs[guy][guy_next_proposal[guy]]
            guy_next_proposal[guy] += 1
            
            if gal not in gal_partner:
                gal_partner[gal] = guy
                guy_partner[guy] = gal
            else:
                current_partner = gal_partner[gal]
                if gal_rankings[gal][guy] < gal_rankings[gal][current_partner]:
                    gal_partner[gal] = guy
                    guy_partner[guy] = gal
                    del guy_partner[current_partner]
                    free_guys.append(current_partner)
                else:
                    free_guys.append(guy)
        
        return [(guy, gal) for guy, gal in guy_partner.items()]
    
    def _verify_stability(self, guy_prefs: Dict[str, List[str]], 
                         gal_prefs: Dict[str, List[str]],
                         guy_to_gal: Dict[str, str], 
                         gal_to_guy: Dict[str, str]) -> bool:
        # Create rankings for efficient preference comparison
        guy_rankings = {}
        for guy, prefs in guy_prefs.items():
            guy_rankings[guy] = {gal: i for i, gal in enumerate(prefs)}
        
        gal_rankings = {}
        for gal, prefs in gal_prefs.items():
            gal_rankings[gal] = {guy: i for i, guy in enumerate(prefs)}
        
        # Check for blocking pairs
        for guy in guy_prefs:
            for gal in gal_prefs:
                if guy_to_gal[guy] == gal:
                    continue  # Already matched
                
                guy_current_partner = guy_to_gal[guy]
                gal_current_partner = gal_to_guy[gal]
                
                # Check if guy prefers gal over his current partner
                guy_prefers = guy_rankings[guy][gal] < guy_rankings[guy][guy_current_partner]
                
                # Check if gal prefers guy over her current partner
                gal_prefers = gal_rankings[gal][guy] < gal_rankings[gal][gal_current_partner]
                
                if guy_prefers and gal_prefers:
                    return False  # Blocking pair found
        
        return True  # No blocking pairs found

Complexity

⏰ Time complexity: O(N²), for the Gale-Shapley algorithm plus O(N²) for stability verification
🧺 Space complexity: O(N²), for storing preference rankings and verification structures

Notes

The Gale-Shapley algorithm always produces a stable matching when one exists
The algorithm is “man-optimal” - it gives the best possible stable partner to each man
There exists a “woman-optimal” version where women propose instead of men
The stable marriage problem has applications in medical residency matching, college admissions, and kidney exchange programs
Method 1 provides the core algorithm implementation
Method 2 adds explicit verification for educational purposes and additional confidence
The algorithm guarantees termination in O(N²) time and always finds a stable matching
Every instance of the stable marriage problem has at least one stable matching

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Gale-Shapley Algorithm#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Irving’s Algorithm with Stability Verification#

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Gale-Shapley Algorithm

Intuition

Approach

Code

Complexity

Method 2 - Irving’s Algorithm with Stability Verification

Intuition

Approach

Code

Complexity

Notes