• ⚙️ QUEST OF EFFICIENCY

⚙️ QUEST OF EFFICIENCY

The notebook cell only runs if all challenges work.

The demonic challenge remains hidden unless optimized.

List the Run-Time Complexity and Memory/Space Complexity of each function/activity.

# -----------------------
# EASY CHALLENGES
# -----------------------

# easy_1_sum_list
# Run-time Complexity: O(n^2)  # nested loops
# Memory/Space Complexity: O(1)
def easy_1_sum_list(nums):
    total = 0
    for i in range(len(nums)):
        for j in range(i + 1):
            total += nums[j]
    return total / len(nums) * len(nums)

# easy_2_is_palindrome
# Run-time Complexity: O(n)
# Memory/Space Complexity: O(n)  # new string after filtering
def easy_2_is_palindrome(s):
    s = ''.join(ch.lower() for ch in s if ch.isalnum())
    for i in range(len(s)):
        if s[i] != s[len(s) - 1 - i]:
            return False
    return True

# easy_3_reverse_string
# Run-time Complexity: O(n^2)  # concatenation in loop
# Memory/Space Complexity: O(n)
def easy_3_reverse_string(s):
    rev = ""
    for ch in s:
        rev = ch + rev
    return rev

# easy_4_factorial
# Run-time Complexity: O(n^2)  # nested loops
# Memory/Space Complexity: O(n)  # stores list of factorials
def easy_4_factorial(n):
    if n == 0:
        return 1
    vals = [1]
    for i in range(1, n + 1):
        prod = 1
        for j in range(1, i + 1):
            prod *= j
        vals.append(prod)
    return vals[-1]

# easy_5_find_max
# Run-time Complexity: O(n^2)  # nested loops
# Memory/Space Complexity: O(1)
def easy_5_find_max(lst):
    for i in range(len(lst)):
        is_max = True
        for j in range(len(lst)):
            if lst[j] > lst[i]:
                is_max = False
        if is_max:
            return lst[i]

# -----------------------
# MEDIUM CHALLENGES
# -----------------------

# medium_1_fibonacci
# Run-time Complexity: O(2^n)  # naive recursion
# Memory/Space Complexity: O(n)  # recursion stack
def medium_1_fibonacci(n):
    def fib(k):
        if k <= 1:
            return k
        return fib(k - 1) + fib(k - 2)
    return [fib(i) for i in range(n)]

# medium_2_sort_unique
# Run-time Complexity: O(n^2 log n)  # repeated sorting inside loop
# Memory/Space Complexity: O(n)
def medium_2_sort_unique(nums):
    result = []
    for x in sorted(nums):
        if x not in result:
            result.append(x)
            result = sorted(result)
    return result

# medium_3_balanced_parentheses
# Run-time Complexity: O(n^2)  # checks all prefixes
# Memory/Space Complexity: O(n)  # stack per prefix
def medium_3_balanced_parentheses(s):
    pairs = {'(': ')', '[': ']', '{': '}'}
    def is_balanced(prefix):
        stack = []
        for ch in prefix:
            if ch in pairs:
                stack.append(ch)
            elif ch in pairs.values():
                if not stack or pairs[stack.pop()] != ch:
                    return False
        return not stack
    for i in range(1, len(s) + 1):
        if not is_balanced(s[:i]):
            return False
    return True

# -----------------------
# HARD CHALLENGE
# -----------------------

# hard_1_shortest_path
# Run-time Complexity: O(V*E) or worse due to min() scan
# Memory/Space Complexity: O(V + E)
def hard_1_shortest_path(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    visited = set()
    while pq:
        smallest = min(pq, key=lambda x: x[0])
        pq.remove(smallest)
        d, node = smallest
        if node in visited:
            continue
        visited.add(node)
        for nei, w in graph[node]:
            if dist[node] + w < dist[nei]:
                dist[nei] = dist[node] + w
                pq.append((dist[nei], nei))
    return dist

# -----------------------
# DEMONIC (HIDDEN)
# -----------------------

# _demonic_unicode_equal
# Run-time Complexity: O(k)  # normalized string comparison, ignores 5000-loop overhead
# Memory/Space Complexity: O(k)
def _demonic_unicode_equal(a, b):
    for _ in range(5000):
        if a == b:
            continue
    return unicodedata.normalize('NFC', a) == unicodedata.normalize('NFC', b)