The Gale-Shapley algorithm provides a solution to the Stable Matching Problem, a challenge that also finds real-world application in scenarios like the National Resident Matching Program (NRMP). In the medical field, this algorithm known as "The Match," efficiently connects medical students with schools each year.

Understanding the Gale-Shapley Algorithm

At its core, the Gale-Shapley algorithm acts as a reliable matchmaker, particularly in scenarios involving medical students and hospitals. It excels in maintaining stability even when pairs of participants consider changing their current match.

Let's consider a practical example; 3 hospitals (Hospital A, Hospital B, Hospital C) 3 medical students (Alice, Bob, Carol)

Hospital Preferences

Student Preferences

Let's see how the Gale-Shapley algorithm unfolds, creating stable pairings in a series of rounds;

1. Round 1:
   • Hospital A offers to Alice. They tentatively pair up.
   • Hospital B offers to Bob. They tentatively pair up.
   • Hospital C offers to Carol. They tentatively pair up.

Result after Round 1:

1. Round 2:
   • Hospital A offers to Alice again, but Alice is already paired and declines.
   • Hospitals B and C have no rejections.

Result after Round 2:

1. Round 3:
   • No changes; all hospitals are stably paired.

Final Result:

The Gale-Shapley algorithm ensures stable pairings, with each hospital and student content with their partners, illustrating its effectiveness in real-world scenarios.

Analyzing the Worst and Best Cases

• Worst Case Scenario: In the worst-case scenario, if there are 'n' hospitals, each with 'n' candidates on their ranked preference lists, the algorithm's worst-case number of rounds becomes O(n^2).
• Best Case Scenario: Conversely, in the best-case scenario, where all 'n' hospitals rank different candidates first, the algorithm completes in O(n) rounds.

For those eager to delve deeper into the Gale-Shapley algorithm, Kevin Wayne's insightful lecture provides an excellent resource Stable Matching Algorithm Lecture.

In essence, the Gale-Shapley algorithm provides a playground for practicing the manipulation of 2D arrays, as demonstrated in the tables above. Preferences showcase the algorithm's elegance in pairing individuals while maintaining stability.

LeetCode 1583 - Count Unhappy Friends

To dive right into the problem, click here.

Understanding LeetCode's 1583 - Count Unhappy Friends

Now, let's take a closer look at the challenge presented.

Imagine a group of friends – Friend 0, Friend 1, Friend 2, and Friend 3 – each with their unique preferences for hanging out. LeetCode's 1583 problem throws them into pairs and challenges us to find the number of unhappy friends.

Friend Preferences

Pairs

Unhappy Scenarios

• Friend 1 is unhappy because he is paired with Friend 0, but he prefers Friend 3 over Friend 0, and Friend 3 prefers Friend 1 over Friend 2.
• Friend 3 is unhappy because she is paired with Friend 2, but she prefers Friend 1 over Friend 2, and Friend 1 prefers Friend 3 over Friend 0.

Let's explore how we can tackle this problem using C#.

Thank you for joining me on this journey through the LeetCode's 1583 - Count Unhappy Friends solution in C#!

I find joy in diving into the depths of original algorithms when tackling these problems. I hope you enjoyed the introduction to the Gale-Shapley algorithm and its application in the context of stable matching.

Feel free to follow my coding adventures on;

GitHub: https://github.com/sercandumansiz
LinkedIn: https://www.linkedin.com/in/sercan-dumansiz-96606b1bb/.

Happy coding and stay curious! 😎