Stable Marriage Problem
HardUpdated: Aug 10, 2025
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:
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
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
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
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
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
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
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
C++
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
}
};
Python
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