[Bug] Arrange Event Attendees by Priority - Solution Does Not Preserve Relative Order

[akashsv01]

Hello CodePath team,

While working through TIP103 Unit 3, I noticed that the solution provided for the "Arrange Event Attendees by Priority" problem does not preserve the relative order within each priority group, which contradicts the problem statement.

The problem statement states that the output is the attendees list rearranged such that attendees with lower priority appear first, followed by those with the exact priority, and finally those with higher priority, while preserving the relative order within each group.

Issue with Current Solution:
The provided solution uses the Dutch National Flag algorithm with in-place swapping. While this is O(1) space and O(n) time, swapping inherently disrupts relative order because elements get "teleported" across the array without respecting their original sequence.

Example Cases Where Current Solution Fails:

Example 1:
attendees = [5, 1, 8, 3, 9, 2]
priority = 4

# Expected (preserving relative order):
# Less than 4: [1, 3, 2] (original order preserved)
# Equal to 4: []
# Greater than 4: [5, 8, 9] (original order preserved)
# Result: [1, 3, 2, 5, 8, 9]

# Current solution produces: [2, 1, 3, 5, 9, 8]
# Less-than group is [2, 1, 3] instead of [1, 3, 2] ❌
# Greater-than group is [5, 9, 8] instead of [5, 8, 9] ❌

Example 2:
attendees = [4, 1, 3, 2, 5]
priority = 3

# Expected (preserving relative order):
# Less than 3: [1, 2]
# Equal to 3: [3]
# Greater than 3: [4, 5]
# Result: [1, 2, 3, 4, 5]

# Current solution produces: [2, 1, 3, 4, 5]
# Less-than group is [2, 1] instead of [1, 2] ❌

Example 3:
attendees = [6, 4, 2, 4, 8, 1]
priority = 4

# Expected (preserving relative order):
# Less than 4: [2, 1]
# Equal to 4: [4, 4]
# Greater than 4: [6, 8]
# Result: [2, 1, 4, 4, 6, 8]

# Current solution does not guarantee this order
# Current solution produces: [1, 2, 4, 4, 6, 8]
# Less-than group is [1, 2] instead of [2, 1] ❌

Proposed Fix:
To preserve relative order, we need to use a stable partitioning approach with O(n) extra space:

def arrange_attendees_by_priority(attendees, priority):
    less = []
    equal = []
    greater = []
    
    for attendee in attendees:
        if attendee < priority:
            less.append(attendee)
        elif attendee == priority:
            equal.append(attendee)
        else:
            greater.append(attendee)
    
    return less + equal + greater

Thanks for all the great content - happy to discuss further!

Best Regards,
Akash S Vora