Gale Shapley Algorithm for Stable Matching problem

Reading time: 30 minutes | Coding time: 10 minutes

Gale Shapley Algorithm is an efficient algorithm that is used to solve the Stable Matching problem. It takes O(N^2) time complexity where N is the number of people involved.

Stable Matching problem
Introduction

We have 2 sets of people:

The first set contains females
The second set contains males.

Each person in each set has a list of preferences which includes all the people from the opposite set. That is, every woman in the set has a pref...