Question:

Stable Matching ?

a matching is stable if there is no pair

(man,woman)

who are not married to each other but both prefer each other over their current partners.

The Gale-Shapley Algorithm (Men-Proposing)

Since the problem asks for the result from the men's perspective, we will implement the version where men propose to women.

1. Initialize: All men and women are initially "free" (not engaged).
2. Loop: While there is a free man who still has women he hasn't proposed to:
   • The man proposes to the most preferred woman on his list to whom he hasn't yet proposed.
   • If the woman is free: She becomes engaged to him.
   • If the woman is already engaged to another man: She compares the new proposer with her current fiancé.
     • If she prefers the new man, she breaks up with her current fiancé (who becomes "free" again) and engages the new man.
     • If she prefers her current fiancé, she rejects the new man.
3. Result: When everyone is paired up, the resulting matching is guaranteed to be stable and man-optimal.

Approach: Two-Pointer Technique

1. Initialize two pointers: left at the beginning of the array (index 0) and right at the end of the array (index ).

   n−1
   

2. While left is less than right:

   • Increment the left pointer as long as it points to a 0.
   • Decrement the right pointer as long as it points to a 1.
   • If left < right, it means we found a 1 on the left side and a 0 on the right side. Swap them (or simply set arr[left] to 0 and arr[right] to 1).
   • Move both pointers one step closer after the swap.

Alternative Approach: Counting (Simpler)

Another simple

O(N)

way is to count the number of zeros and then overwrite the array.