Intermediate Algorithm Problem Solving Questions

import heapq
from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def __repr__(self):
        return f"{self.val}"

def merge_k_lists(lists):
    """
    Merge k sorted linked lists using a heap.
    Time: O(N log k), Space: O(k) for heap (plus output list).
    """
    heap = []
    # Initialize heap with head nodes
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, id(node), node))  # id() as unique uid

    dummy = ListNode(0)
    tail = dummy

    while heap:
        val, _, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        # detach to avoid accidental cycles in some contexts (optional)
        next_node = node.next
        tail.next = None
        if next_node:
            heapq.heappush(heap, (next_node.val, id(next_node), next_node))

    return dummy.next

# Helper to build and print lists (for testing)
def build_list(arr):
    dummy = ListNode(0)
    t = dummy
    for x in arr:
        t.next = ListNode(x)
        t = t.next
    return dummy.next

def to_list(node):
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out

# Example:
lists = [build_list([1,4,5]), build_list([1,3,4]), build_list([2,6])]
merged = merge_k_lists(lists)
print(to_list(merged))  # [1,1,2,3,4,4,5,6]

import heapq
from typing import List

def k_smallest_heap(arr: List[int], k: int) -> List[int]:
    """
    Return k smallest elements from arr using a max-heap of size k (via negation).
    Expected time: O(n log k), space: O(k).
    """
    if k <= 0:
        return []
    n = len(arr)
    if k >= n:
        return list(arr)  # all elements

    # Build max-heap of first k elements by negating
    max_heap = [-x for x in arr[:k]]
    heapq.heapify(max_heap)  # O(k)
    
    for x in arr[k:]:
        if -max_heap[0] > x:       # current largest in heap > x
            heapq.heapreplace(max_heap, -x)  # pop and push in O(log k)
    
    # Convert back to positive values
    return [-v for v in max_heap]

def length_of_longest_substring(s: str) -> int:
    """
    Returns length of longest substring without repeating characters.
    O(n) time using sliding window and last-seen index map.
    """
    last_seen = {}  # char -> last index
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            # repeated inside current window -> move left past previous occurrence
            left = last_seen[ch] + 1
        last_seen[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len