Recall how the standard 2-way partition (Lomuto or Hoare) handles duplicates and why it can degrade to O(n²) when many duplicates exist.

Consider how a 3-way partition (Dutch National Flag) divides the array into three regions: elements less than, equal to, and greater than the pivot.

Design the partitioning logic to place all duplicates of the pivot into their correct final positions in a single pass, ensuring O(n) time for the partitioning step.