A support inbox holds tickets tagged "urgent", "normal" or "later". Return a new list containing the same tags rearranged so that every "urgent" comes first, then every "normal", then every "later".
Do it in a single pass over the input plus one pass to build the output, using only a constant amount of extra bookkeeping (three counters is plenty). Calling a general-purpose sort is not the point of this exercise.
Examples
Input: tags = ["later", "urgent", "normal", "urgent"]
Output: ["urgent", "urgent", "normal", "later"]
Constraints
0 <= len(tags) <= 10**5- Every element is one of the three tags.
- Target complexity: O(n) time, O(1) extra space besides the output.
Goals
- Sort three categories in linear time without a comparison sort
- Count occurrences in one pass and rebuild the list
- Keep only O(1) extra bookkeeping