"""
Misconception Library — common wrong approaches per DSA topic.
Used by the hint node to generate targeted, awareness-raising hints.
"""

MISCONCEPTION_LIBRARY: dict[str, list[str]] = {
    "two sum": [
        "Using O(N²) nested loops instead of a hashmap giving O(N)",
        "Sorting the array and using two pointers (works but misses the index requirement)",
    ],
    "dynamic programming": [
        "Recursive solution without memoization (exponential time)",
        "Filling DP table in the wrong order (top-down vs bottom-up confusion)",
        "Using 2D DP table when 1D rolling array suffices",
    ],
    "graph bfs": [
        "Not using a visited set — causes infinite loops in cyclic graphs",
        "Using DFS instead of BFS for shortest-path problems",
    ],
    "graph dfs": [
        "Forgetting to backtrack state in recursive DFS",
        "Not handling disconnected components",
    ],
    "sliding window": [
        "Shrinking the window incorrectly (off-by-one on left pointer)",
        "Recomputing window sum from scratch instead of incrementally updating",
    ],
    "binary search": [
        "Using wrong boundary: `mid < right` vs `mid <= right`",
        "Integer overflow: use `mid = left + (right - left) // 2`",
    ],
    "linked list": [
        "Losing the next pointer before reassignment",
        "Not handling the head node as a special case",
    ],
    "tree traversal": [
        "Mixing up in-order, pre-order, and post-order for the required output",
        "Forgetting base case for null nodes",
    ],
    "heap / priority queue": [
        "Using a max-heap when a min-heap is needed (or vice versa)",
        "Not heapifying after updating an element",
    ],
    "backtracking": [
        "Not undoing state changes before returning (missing 'undo' step)",
        "Pruning conditions placed after recursive call instead of before",
    ],
    "trie": [
        "Using a dict instead of a fixed-size array for children (slower but acceptable)",
        "Forgetting to mark end-of-word node",
    ],
    "union find": [
        "Using naive union without path compression (too slow for large N)",
        "Forgetting to check if two nodes share the same root before merging",
    ],
    "default": [
        "Incorrect time/space complexity analysis",
        "Not considering edge cases (empty input, single element, negative numbers)",
    ],
}


def get_misconceptions(topic: str) -> list[str]:
    """Return known misconceptions for the given topic (case-insensitive)."""
    key = topic.strip().lower()
    # Try exact match first, then partial match
    if key in MISCONCEPTION_LIBRARY:
        return MISCONCEPTION_LIBRARY[key]
    for lib_key, misconceptions in MISCONCEPTION_LIBRARY.items():
        if lib_key in key or key in lib_key:
            return misconceptions
    return MISCONCEPTION_LIBRARY["default"]