Data Structure Complexity

# =============================================================================
#Filename: 01_list_complexity.py
#Description: Measure the time complexity of list operations using timeit
#Time complexity: append O(1) amortized, insert(0) O(n), pop() O(1), pop(0) O(n)
#Space complexity: O(n) — list size
# =============================================================================

import timeit
import time


# ---------------------------------------------------------------------------
#Comparison of append vs insert(0)
# ---------------------------------------------------------------------------
def benchmark_append_vs_insert(n: int = 10_000) -> None:
    """Compares the speed of appending at the end and inserting at the front (insert(0))."""
    print(f"\n[append vs insert(0)] performed n={n:,} times")
    print("-" * 50)

    #append — O(1) amortized
    t_append = timeit.timeit(
        stmt='lst.append(0)',
        setup='lst = []',
        number=n
    )

    #insert(0) — O(n): shift all elements one position to the right
    t_insert = timeit.timeit(
        stmt='lst.insert(0, 0)',
        setup='lst = []',
        number=n
    )

    ratio = t_insert / t_append if t_append > 0 else float('inf')
    print(f"append:    {t_append:.6f} seconds  (O(1) amortized)")
    print(f"insert(0): {t_insert:.6f} seconds  (O(n))")
    print(f"insert(0) is {ratio:.1f} times slower")

    #Check if the difference increases as the list size grows
    print(f"\n  Change in insert(0) time by list size:")
    for size in [1_000, 5_000, 10_000, 50_000]:
        t = timeit.timeit(
            stmt='lst.insert(0, 0)',
            setup=f'lst = list(range({size}))',
            number=1000
        )
        print(f"size={size:>6,}: {t:.6f} seconds (1000 times)")


# ---------------------------------------------------------------------------
#Comparison of pop() vs pop(0)
# ---------------------------------------------------------------------------
def benchmark_pop_vs_pop0(n: int = 5_000) -> None:
    """Compares the speed of removal from the end (pop()) and removal from the front (pop(0))."""
    print(f"[pop() vs pop(0)] n={n:,} times executed")
    print("-" * 50)

    #pop() — O(1): remove the last element
    t_pop = timeit.timeit(
        stmt='lst.pop()',
        setup=f'lst = list(range({n * 2}))',
        number=n
    )

    #pop(0) — O(n): remove the first element and shift all elements to the left
    t_pop0 = timeit.timeit(
        stmt='lst.pop(0)',
        setup=f'lst = list(range({n * 2}))',
        number=n
    )

    ratio = t_pop0 / t_pop if t_pop > 0 else float('inf')
    print(f"pop():  {t_pop:.6f} seconds  (O(1))")
    print(f"pop(0): {t_pop0:.6f} seconds  (O(n))")
    print(f"pop(0) is {ratio:.1f} times slower")


# ---------------------------------------------------------------------------
#Index access vs linear search
# ---------------------------------------------------------------------------
def benchmark_index_vs_search(n: int = 100_000) -> None:
    """Compares index access (O(1)) and linear search (O(n))."""
    print(f"[Index Access vs Linear Search] n={n:,}")
    print("-" * 50)

    #Index access — O(1)
    t_index = timeit.timeit(
        stmt=f'_ = lst[{n // 2}]',
        setup=f'lst = list(range({n}))',
        number=10_000
    )

    #Linear search (worst case: last element) — O(n)
    t_search = timeit.timeit(
        stmt=f'_ = {n - 1} in lst',
        setup=f'lst = list(range({n}))',
        number=1_000
    )

    print(f"lst[n//2] (index):     {t_index:.6f} seconds (10,000 times)")
    print(f"n-1 in lst (linear search): {t_search:.6f} seconds (1,000 times)")
    print(f"[Note] set membership is O(1) on average → faster")


# ---------------------------------------------------------------------------
#Slicing copy — O(k) (proportional to slice size)
# ---------------------------------------------------------------------------
def benchmark_slicing(n: int = 100_000) -> None:
    """Checking the time complexity of slicing."""
    print(f"[Slicing Complexity] n={n:,}")
    print("-" * 50)
    lst = list(range(n))

    for k in [10, 1_000, 10_000, n]:
        t0 = time.perf_counter()
        for _ in range(1000):
            _ = lst[:k]     #O(k) — copy k elements
        elapsed = time.perf_counter() - t0
        print(f"lst[:{k:>7,}] slicing 1,000 times: {elapsed:.4f} seconds")

    print("[Conclusion] Slicing is O(k) — proportional to slice size")


def main():
    print("=" * 55)
    print("Measured list operation time complexities")
    print("=" * 55)

    benchmark_append_vs_insert(n=10_000)
    benchmark_pop_vs_pop0(n=5_000)
    benchmark_index_vs_search(n=100_000)
    benchmark_slicing(n=100_000)

    print("\n" + "=" * 55)
    print("Key summary")
    print("=" * 55)
    print("append(x)     : O(1) amortized  ← add to the end")
    print("insert(0, x)  : O(n)           ← add to the front (avoid)")
    print("pop()         : O(1)           ← remove from the end")
    print("pop(0)        : O(n)           ← remove from the front (avoid)")
    print("lst[i]        : O(1)           ← random access")
    print("x in lst      : O(n)           ← linear search")
    print("Alternative: If O(1) operations are needed at both ends, use deque!")


if __name__ == "__main__":
    main()

# =============================================================================
#File name: 02_dict_set_ops.py
#Description: Measuring dict/set operation time complexity and examples using Counter
#Time complexity: dict/set lookup O(1) on average, list search O(n)
#Space complexity: O(n) — proportional to the number of stored elements
# =============================================================================

import timeit
import time
import random
from collections import Counter, defaultdict


# ---------------------------------------------------------------------------
#Comparison of set vs list membership check
# ---------------------------------------------------------------------------
def benchmark_membership(n: int = 100_000) -> None:
    """Compares the membership testing speed of set and list."""
    print(f"[set vs list membership check] n={n:,}")
    print("-" * 55)

    random.seed(42)
    data = random.sample(range(n * 2), n)  #n unique integers

    #list membership — O(n)
    repeat = 1_000
    t_list = timeit.timeit(
        stmt=f'{n - 1} in lst',
        setup=f'lst = {data}',
        number=repeat
    )

    #set membership — O(1) on average
    t_set = timeit.timeit(
        stmt=f'{n - 1} in s',
        setup=f's = set({data})',
        number=repeat
    )

    ratio = t_list / t_set if t_set > 0 else float('inf')
    print(f"list ({repeat} times): {t_list:.6f} seconds  O(n)")
    print(f"set  ({repeat} times): {t_set:.6f} seconds  O(1) on average")
    print(f"set is {ratio:.1f} times faster")

    #Difference between list vs set by size
    print(f"Membership check time by size (100 times, worst case):")
    print(f"{'Size':>10}  {'list(sec)':>12}  {'set(sec)':>12}  {'Ratio':>8}")
    for size in [1_000, 10_000, 100_000]:
        sample = list(range(size))
        target = size - 1  #Worst case: last element

        t_l = timeit.timeit(
            stmt=f'{target} in lst',
            setup=f'lst = list(range({size}))',
            number=100
        )
        t_s = timeit.timeit(
            stmt=f'{target} in s',
            setup=f's = set(range({size}))',
            number=100
        )
        r = t_l / t_s if t_s > 0 else float('inf')
        print(f"  {size:>10,}  {t_l:>12.6f}  {t_s:>12.6f}  {r:>8.1f}x")


# ---------------------------------------------------------------------------
#Demo of basic dict operations
# ---------------------------------------------------------------------------
def demo_dict_operations() -> None:
    """Demonstrates the main operations of a dict."""
    print("[Basic dict operations demo]")
    print("-" * 55)

    #Insertion — O(1) on average
    d = {}
    d['apple'] = 3
    d['banana'] = 1
    d['cherry'] = 5
    print(f"After insertion dict: {d}")

    #Lookup — O(1) on average
    print(f"  d['apple'] = {d['apple']}")

    #Safe lookup — using get() (prevents KeyError)
    print(f"  d.get('grape', 0) = {d.get('grape', 0)}")  #Default value 0

    #Key existence check — O(1) on average
    print(f"  'banana' in d: {'banana' in d}")
    print(f"  'grape' in d:  {'grape' in d}")

    #Deletion — O(1) on average
    del d['banana']
    print(f"After del d['banana']: {d}")

    #defaultdict — automatically creates default value
    word_count = defaultdict(int)
    text = "apple banana apple cherry banana apple"
    for word in text.split():
        word_count[word] += 1  #No KeyError on first access
    print(f"Counting frequency with defaultdict(int):")
    for word, count in sorted(word_count.items()):
        print(f"    {word}: {count}")


# ---------------------------------------------------------------------------
#Example of using Counter
# ---------------------------------------------------------------------------
def demo_counter() -> None:
    """Shows an example of using collections.Counter."""
    print("[Counter usage example]")
    print("-" * 55)

    #Basic usage
    words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
    cnt = Counter(words)
    print(f"  Counter(words) = {cnt}")

    #Most frequently occurring element
    print(f"  most_common(2) = {cnt.most_common(2)}")

    #Counting frequencies in a list of integers
    nums = [1, 2, 3, 2, 1, 3, 3, 4, 4, 4, 4]
    num_cnt = Counter(nums)
    print(f"\n  Counter([1,2,3,2,1,3,3,4,4,4,4]) = {num_cnt}")
    print(f"Number of times 4 appears: {num_cnt[4]}")

    #Counter operations
    c1 = Counter({'a': 3, 'b': 2, 'c': 1})
    c2 = Counter({'a': 1, 'b': 2, 'd': 3})
    print(f"\n  c1 + c2 = {c1 + c2}")  #Addition
    print(f"  c1 - c2 = {c1 - c2}")  #Difference (positive only)
    print(f"  c1 & c2 = {c1 & c2}")  #Minimum
    print(f"  c1 | c2 = {c1 | c2}")  #Maximum value

    #Checking string anagrams
    def is_anagram(s1: str, s2: str) -> bool:
        """Check if two strings are anagrams. O(n)"""
        return Counter(s1) == Counter(s2)

    print(f"\n  is_anagram('listen', 'silent') = {is_anagram('listen', 'silent')}")
    print(f"  is_anagram('hello', 'world')   = {is_anagram('hello', 'world')}")


def main():
    print("=" * 55)
    print("dict / set operation time complexity demo")
    print("=" * 55)

    benchmark_membership(n=100_000)
    demo_dict_operations()
    demo_counter()

    print("\n" + "=" * 55)
    print("Key summary")
    print("=" * 55)
    print("x in list  : O(n)   ← avoid this (iterative search)")
    print("x in set   : O(1)   ← use for membership check")
    print("d[k]       : O(1)   ← key-value mapping")
    print("Counter    : O(n)   ← optimal for counting frequency")


if __name__ == "__main__":
    main()

# =============================================================================
#Filename: 03_deque_vs_list.py
#Description: deque vs list queue operation speed comparison
#Time complexity: deque.popleft() O(1), list.pop(0) O(n)
#Space complexity: O(n) — number of stored elements
# =============================================================================

import time
import timeit
from collections import deque


# ---------------------------------------------------------------------------
#BFS queue simulation: using list.pop(0) — O(n²)
# ---------------------------------------------------------------------------
def bfs_with_list(graph: dict, start: int) -> list:
    """BFS using a list as a queue. Time complexity: O(V + E) but pop(0) is O(V²)"""
    visited = []
    order = []
    queue = [start]         #Using list as a queue

    while queue:
        node = queue.pop(0)  #O(n) — moving all elements forward
        if node in visited:
            continue
        visited.append(node)
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)

    return order


# ---------------------------------------------------------------------------
#BFS queue simulation: using deque.popleft() — O(V + E)
# ---------------------------------------------------------------------------
def bfs_with_deque(graph: dict, start: int) -> list:
    """BFS using deque as a queue. Time complexity: O(V + E)"""
    visited = set()
    order = []
    queue = deque([start])  #Using deque as a queue

    while queue:
        node = queue.popleft()  #O(1) — remove immediately from the front
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                queue.append(neighbor)

    return order


# ---------------------------------------------------------------------------
#deque operation demo
# ---------------------------------------------------------------------------
def demo_deque_operations() -> None:
    """Demonstrates the main operations of a deque."""
    print("[deque Basic Operations Demo]")
    print("-" * 50)

    dq = deque()

    #Add to both ends
    dq.append(3)         #Add to the right: [3]
    dq.append(4)         #Add to the right: [3, 4]
    dq.appendleft(2)     #Add to the left:  [2, 3, 4]
    dq.appendleft(1)     #Add to the left:  [1, 2, 3, 4]
    print(f"After append/appendleft: {list(dq)}")

    #Remove from both ends
    right = dq.pop()     #Remove from the right: [1, 2, 3]
    left = dq.popleft()  #Remove from the left:  [2, 3]
    print(f"  pop() = {right}, popleft() = {left}")
    print(f"After removal: {list(dq)}")

    #Rotate
    dq = deque([1, 2, 3, 4, 5])
    dq.rotate(2)   #Rotate 2 to the right
    print(f"After rotate(2): {list(dq)}")  # [4, 5, 1, 2, 3]
    dq.rotate(-2)  #Rotate 2 to the left
    print(f"After rotate(-2): {list(dq)}")  # [1, 2, 3, 4, 5]

    #maxlen option — maximum size limit
    fixed = deque(maxlen=3)
    for i in range(5):
        fixed.append(i)
        print(f"  append({i}) → {list(fixed)}")


# ---------------------------------------------------------------------------
#Performance benchmark
# ---------------------------------------------------------------------------
def benchmark_queue_operations(n: int = 10_000) -> None:
    """Compares the queue operation speeds of list and deque."""
    print(f"[Queue Operation Benchmark] n={n:,} times append + popleft")
    print("-" * 50)

    #list: append + pop(0) — O(n²) overall
    t0 = time.perf_counter()
    lst = []
    for i in range(n):
        lst.append(i)
    for _ in range(n):
        lst.pop(0)           #O(n) each time
    t_list = time.perf_counter() - t0

    #deque: append + popleft — O(n) overall
    t0 = time.perf_counter()
    dq = deque()
    for i in range(n):
        dq.append(i)
    for _ in range(n):
        dq.popleft()         #O(1) each time
    t_deque = time.perf_counter() - t0

    ratio = t_list / t_deque if t_deque > 0 else float('inf')
    print(f"list (pop(0)):   {t_list:.4f} seconds  O(n²)")
    print(f"deque (popleft): {t_deque:.6f} seconds  O(n)")
    print(f"deque is {ratio:.1f} times faster (at n={n})")


def main():
    print("=" * 55)
    print("deque vs list queue operation comparison")
    print("=" * 55)

    #deque basic operation demonstration
    demo_deque_operations()

    #BFS correctness verification
    print("[BFS Accuracy Verification]")
    graph = {
        1: [2, 3],
        2: [4, 5],
        3: [5, 6],
        4: [],
        5: [6],
        6: []
    }
    result_list = bfs_with_list(graph, 1)
    result_deque = bfs_with_deque(graph, 1)
    print(f"  list BFS:  {result_list}")
    print(f"  deque BFS: {result_deque}")
    print(f"Result match: {result_list == result_deque}")

    #Performance benchmark
    benchmark_queue_operations(n=10_000)

    print("\n" + "=" * 55)
    print("Key summary")
    print("=" * 55)
    print("BFS with list.pop(0) as queue → O(n²) overall [Not recommended]")
    print("BFS with deque.popleft() as queue → O(n) overall [Recommended]")
    print("Always use from collections import deque!")


if __name__ == "__main__":
    main()

# =============================================================================
#File name: 04_choosing_structure.py
#Description: Guide to Choosing Appropriate Data Structures for Different Situations — Practical Examples
#Time Complexity: See comments in each example
#Space Complexity: O(n) — proportional to data size
# =============================================================================

import heapq
from collections import deque, Counter, defaultdict


# ---------------------------------------------------------------------------
#Situation 1: Remove duplicates + fast membership test → set
# ---------------------------------------------------------------------------
def scenario_dedup_membership() -> None:
    """A situation where duplicate removal and membership checking are needed. Data structure: set"""
    print("\n[Situation 1] Remove duplicates + fast membership test → set")
    print("-" * 50)

    #Track visited nodes (graph traversal)
    visited = set()  #Use set instead of list!

    nodes = [1, 3, 2, 5, 3, 2, 7, 1]
    for node in nodes:
        if node not in visited:   #O(1) on average
            visited.add(node)     #O(1) on average

    unique = sorted(visited)
    print(f"Input: {nodes}")
    print(f"Visited nodes (set): {unique}")
    print(f"Time complexity: O(n) — n operations of O(1)")

    #Intersection of two sets (common elements)
    a = {1, 2, 3, 4, 5}
    b = {3, 4, 5, 6, 7}
    print(f"Intersection a & b = {a & b}")
    print(f"Union a | b = {a | b}")
    print(f"Difference a - b = {a - b}")


# ---------------------------------------------------------------------------
#Situation 2: Count frequencies → Counter / defaultdict
# ---------------------------------------------------------------------------
def scenario_frequency_count() -> None:
    """A situation where frequency counting is needed. Data structure: Counter or defaultdict"""
    print("[Scenario 2] Counting frequency → Counter / defaultdict")
    print("-" * 50)

    #Count word frequencies
    text = "the quick brown fox jumps over the lazy dog the fox"
    words = text.split()

    #Using Counter — O(n)
    cnt = Counter(words)
    top3 = cnt.most_common(3)
    print(f"Top 3 words: {top3}")

    #Using defaultdict — O(n)
    freq = defaultdict(int)
    for w in words:
        freq[w] += 1
    print(f"Occurrences of 'the': {freq['the']}")

    #Find the majority element in an array
    nums = [3, 2, 3, 1, 2, 4, 5, 5, 6, 7, 5, 3, 4, 5]
    num_cnt = Counter(nums)
    most_common = num_cnt.most_common(1)[0]
    print(f"Most frequent number in array: {most_common[0]} ({most_common[1]} times)")


# ---------------------------------------------------------------------------
#Situation 3: Queue where order matters (BFS) → deque
# ---------------------------------------------------------------------------
def scenario_bfs_queue() -> None:
    """A situation where a BFS queue is needed. Data structure: deque"""
    print("[Scenario 3] BFS Queue → deque")
    print("-" * 50)

    #Maze exploration example
    maze = [
        [0, 0, 1, 0, 0],
        [0, 0, 0, 1, 0],
        [1, 0, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0],
    ]
    #0: passable, 1: wall
    rows, cols = len(maze), len(maze[0])
    start, end = (0, 0), (4, 4)

    def bfs_maze(start: tuple, end: tuple) -> int:
        """Returns the length of the shortest path using BFS. O(V)"""
        queue = deque([(start, 0)])  #(position, distance)
        visited = {start}
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while queue:
            (r, c), dist = queue.popleft()  # O(1)
            if (r, c) == end:
                return dist
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and maze[nr][nc] == 0
                        and (nr, nc) not in visited):
                    visited.add((nr, nc))
                    queue.append(((nr, nc), dist + 1))
        return -1  #No path

    dist = bfs_maze(start, end)
    print(f"Start {start} → End {end}: Shortest distance = {dist}")


# ---------------------------------------------------------------------------
#Situation 4: Handle priority → heapq
# ---------------------------------------------------------------------------
def scenario_priority_queue() -> None:
    """A situation that requires a priority queue. Data structure: heapq"""
    print("[Scenario 4] Priority Queue → heapq")
    print("-" * 50)

    #Min-heap
    heap = []
    tasks = [(3, 'Write report'), (1, 'Emergency call'), (2, 'Prepare meeting')]

    for priority, task in tasks:
        heapq.heappush(heap, (priority, task))  # O(log n)

    print("Task processing order (lower priority goes first):")
    while heap:
        p, t = heapq.heappop(heap)  # O(log n)
        print(f"Priority {p}: {t}")

    #Max-heap — negative conversion trick
    max_heap = []
    scores = [85, 92, 78, 95, 88]
    for s in scores:
        heapq.heappush(max_heap, -s)  #Store as negative

    print(f"Score list: {scores}")
    print(f"Top 3 scores:", end="")
    top3 = []
    for _ in range(3):
        top3.append(-heapq.heappop(max_heap))
    print(top3)


# ---------------------------------------------------------------------------
#Situation 5: Key-value mapping → dict
# ---------------------------------------------------------------------------
def scenario_mapping() -> None:
    """A situation where key-value mapping is needed. Data structure: dict"""
    print("[Scenario 5] Key-value mapping → dict")
    print("-" * 50)

    #Manage student grades
    grades = {'Alice': 95, 'Bob': 82, 'Charlie': 90}

    #Find pairs whose sum equals target (Two Sum problem)
    def two_sum(nums: list, target: int):
        """O(n) solution — store complementary values using a dict"""
        seen = {}  #{value: index}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:   #O(1) lookup
                return (seen[complement], i)
            seen[num] = i
        return None

    nums = [2, 7, 11, 15]
    result = two_sum(nums, 9)
    print(f"Two Sum [2,7,11,15], target=9: Indices {result}")
    print(f"Time complexity: O(n) — Thanks to dict O(n²) → O(n)")


def main():
    print("=" * 55)
    print("Guide for selecting data structures by scenario")
    print("=" * 55)

    scenario_dedup_membership()
    scenario_frequency_count()
    scenario_bfs_queue()
    scenario_priority_queue()
    scenario_mapping()

    print("\n" + "=" * 55)
    print("Summary of data structure selection")
    print("=" * 55)
    print("Remove duplicates / Membership check → set      O(1)")
    print("Counting frequency        → Counter  O(n)")
    print("BFS queue (bidirectional) → deque    O(1) both ends")
    print("Priority handling         → heapq    O(log n)")
    print("Key-value mapping         → dict     O(1)")
    print("Index access / slicing    → list     O(1) / O(k)")


if __name__ == "__main__":
    main()