Flatten Nested Objects and Lists into Full Leaf Paths

Flatten Nested Objects and Lists into Full Leaf Paths

In enterprise platforms like Salesforce, data models often contain deeply nested structures combining maps, objects, and arrays. You are tasked with writing a function that traverses an arbitrary JSON-like data structure and extracts all paths leading to leaf nodes whose values are strings.

Requirements

1. Path Construction:
   • Dictionary/map keys are appended using dot notation (e.g., user.address.city).
   • List indices are appended using bracket notation (e.g., items[0].name).
   • If a list is located at the root of the data structure, it starts with index notation (e.g., [0].id).
   • Consecutive list nesting must chain brackets directly (e.g., matrix[0][1]).
   • Consecutive object nesting inside a list item should attach directly after the bracket without a preceding dot for the list, but with a dot before the child key (e.g., users[0].name).
2. Filtering:
   • Only leaves that are of type str must be included. Other primitives (such as integers, floats, booleans, and None) or empty containers ({} or []) should not produce leaf entries.
3. Ordering:
   • The resulting list of paths must be returned in lexicographical (alphabetical) order.
4. Traversal:
   • You should design the traversal using an iterative approach (e.g., using an explicit stack).

Function Signature

def flatten_paths(data: Any) -> list[str]:
    pass

Input and Output Format

• Input: A Python object (data) composed of nested dict, list, str, int, float, bool, or None.
• Output: A list of strings (list[str]), sorted lexicographically, representing all valid paths to string leaf values.

Constraints

• Total number of elements/nodes across the structure <= 10^4.
• Nesting depth <= 100.
• Object keys are non-empty alphanumeric strings without spaces, ., [, or ].
• Leaf strings may be empty ("").

Examples

Example 1

data = {
    "user": {
        "name": "Alice",
        "age": 30,
        "tags": ["admin", "dev"],
        "profile": {
            "bio": "Engineer"
        }
    }
}

flatten_paths(data)
# Output:
# [
#   "user.name",
#   "user.profile.bio",
#   "user.tags[0]",
#   "user.tags[1]"
# ]

Explanation: user.age is skipped because its value is an integer (30). The remaining paths point to strings and are returned in lexicographical order.

Example 2

data = [
    {"title": "Root", "metadata": None},
    {"items": [["leaf1"], 42]}
]

flatten_paths(data)
# Output:
# [
#   "[0].title",
#   "[1].items[0][0]"
# ]

Explanation: data[0]["metadata"] is None and data[1]["items"][1] is 42, so neither is included. The two string leaves produce paths "[0].title" and "[1].items[0][0]".