PracticeData Structures

Rebuild a Document's Token Index

Easy/MediumData Structurestraversalaccumulationstate tracking Time not estimated Not started

Context

A document archive stores the tokens from each note in the order they were captured. For an index-building step, the archive needs those tokens arranged alphabetically. Repeated words must remain repeated because their counts are meaningful. Create the ordered token stream using a priority queue rather than assuming the captured order is useful.

Problem

Write a function that receives the token list from one document and returns a new list containing the same tokens in nondecreasing lexicographic order. Every occurrence must be retained, including repeated tokens. The input may be empty, already ordered, reversed, or arranged unpredictably. Build a min-heap of pending tokens, then repeatedly remove its smallest token until no pending tokens remain. Do not change the input list.

Examples

Example 1

Input: tokens = []

Output: []

Explanation: For the empty token list, the executed function returns an empty list. (fact_ids: )

Example 2

Input: tokens = ["apple", "banana", "banana", "cherry"]

Output: ["apple", "banana", "banana", "cherry"]

Explanation: For the already ordered input with two occurrences of "banana", the executed function returns the same ordered list and retains both occurrences. (fact_ids: )

Example 3

Input: tokens = ["pear", "apple", "orange", "apple", "grape"]

Output: ["apple", "apple", "grape", "orange", "pear"]

Explanation: For the mixed input, the executed function returns ["apple", "apple", "grape", "orange", "pear"] in nondecreasing order while retaining both occurrences of "apple". (fact_ids: )

Constraints

0 <= len(tokens) <= 100000
1 <= len(tokens[i]) <= 30 for every i
tokens[i]: alphabet lowercase
Tokens contain lowercase English letters only.
Types: tokens is str[]; result is str[]

Function signature

def order_document_tokens(tokens: list[str]) -> list[str]

tokens list[str]: The captured tokens from one document, possibly empty and possibly containing repeated words.
returns list[str]: A new list containing exactly the input tokens, arranged in nondecreasing lexicographic order.

Adapted from MBPP problem task_635 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Code

Saved

Checking environment…Python SandboxLn 1, Col 1

tokens =