Stable Matching Problem

def gale_shapley(students, hospitals):
    """
    Gale-Shapley algorithm for stable matching.
    Time: O(n²), Space: O(n)
    """
    n = len(students)
    # Track current proposals
    student_proposals = [0] * n
    # Track current engagements
    hospital_partners = [-1] * n
    # Track if student is free
    student_free = [True] * n
    
    while any(student_free):
        # Find a free student
        student = next(i for i in range(n) if student_free[i])
        
        if student_proposals[student] >= len(students[student]):
            break  # No more preferences
        
        # Get next preferred hospital
        hospital = students[student][student_proposals[student]]
        student_proposals[student] += 1
        
        if hospital_partners[hospital] == -1:
            # Hospital is free, engage
            hospital_partners[hospital] = student
            student_free[student] = False
        else:
            # Check if hospital prefers this student
            current_student = hospital_partners[hospital]
            if hospitals[hospital].index(student) < hospitals[hospital].index(current_student):
                # Hospital prefers new student
                hospital_partners[hospital] = student
                student_free[student] = False
                student_free[current_student] = True
    
    return hospital_partners