data_algorithms_2.py

def parse_intervals(line):
    try:
        if not line: return False
        pairs = line.strip().split(",")
        p1_start, p1_end = map(int, pairs[0].split("-"))
        p2_start, p2_end = map(int, pairs[1].split("-"))
        if p1_start <= p2_end and p1_end >= p2_end or p2_start <= p1_end and p2_end >= p1_end: return True 
        #if p1_start <= p2_end and p2_start <= p1_end: return True
    except (ValueError, IndexError): return False
    return False

def parse_line(line): #time O(1), space O(1)
    """Transforms a raw text line into a structured dictionary. Includes error handling to ensure the 'pipeline' doesn't crash on bad data."""
    clean_line = line.strip()
    if not clean_line or clean_line.startswith("TIMESTAMP"): return None # Clean the string (remove newline characters and extra whitespace)
    parts = clean_line.split(',') # Split the data (assuming comma-separated)
    if len(parts) < 4: return None  # Check for 'Non-Trivial' errors (missing columns)
    try:
         return {"timestamp": parts[0].strip(), "symbol": parts[1].strip(), "price": float(parts[2]), "quantity": int(parts[3])  }
    except ValueError: return None

def process_large_file(filename):
    with open(filename, 'r') as f:
        for line in f:
            yield parse_line(line) # Processes one line at a time

def read_text(file_name):
    try:
        counter = 0
        with open(file_name, "r") as file_content:
            for line in file_content:
                data = parse_intervals(line)
                if data: counter += 1
                print(data)
            print(f"Intersects: {counter}")
    except ValueError: return "Error reading the file"

def parse_diff_net_change(diff_lines, bucket_size=10): #time O(N), space O(B)
    current_original_line = 0; buckets = {}
    for line in diff_lines:
        if not line: continue
        prefix = line[0]
        bucket_id = current_original_line // bucket_size # Calculate which 10-line block this belongs to
        if prefix == ' ': current_original_line += 1 # No change, but we move to the next original line
        elif prefix == '-':
            buckets[bucket_id] = buckets.get(bucket_id, 0) - 1 # Deletion: counts as -1 for the current original index
            current_original_line += 1
        elif prefix == '+':
            buckets[bucket_id] = buckets.get(bucket_id, 0) + 1 # Addition: counts as +1. It is "attached" to the current original line position
    return buckets

from collections import defaultdict
def process_diff_file(file_path, bucket_size=10):
    """Reads a diff file line-by-line and yields net changes for each 10-line bucket of the original file."""
    current_original_line = 0
    buckets = defaultdict(int)
    try:
        with open(file_path, 'r', encoding='utf-8') as f:
            for line in f:
                line = line.rstrip('\n')
                if not line: continue
                prefix = line[0]
                bucket_id = current_original_line // bucket_size
                if prefix == ' ':
                    current_original_line += 1 # No change, just increment index
                elif prefix == '-':
                    buckets[bucket_id] -= 1 # Deletion in original file
                    current_original_line += 1
                elif prefix == '+':
                    buckets[bucket_id] += 1 # Addition to the new version
        return dict(buckets)
    except FileNotFoundError: return {}

import json, csv

def flatten_json(data, prefix=""):
    items = {}
    for key, value in data.items():
        new_key = f"{prefix}{key}"
        if isinstance(value, dict): items.update(flatten_json(value, f"{new_key}_"))
        else: items[new_key] = value
    return items

def json_to_csv(input_file, output_file):
    with open(input_file, "r", encoding="utf8") as f:
        raw_data = json.load(f)
    flat_data = flatten_json(raw_data)
    print(flat_data)
    with open(output_file, "w", newline= "", encoding="utf-8") as f:
        writer = csv.DictWriter(f, fieldnames=flat_data.keys()) # header
        writer.writeheader()
        writer.writerow(flat_data) # row

from collections import deque
def analyze_sensor_stream(file_path, k=5): # Reads sensor data from a file and yields the Moving Average of the last K values
    window = deque()
    running_sum = 0.0
    try:
        with open(file_path, "r", encoding="utf-8") as f:
            for line in f:
                line = line.strip()
                if not line: continue
                new_val = float(line)
                window.append(new_val) # add to window 
                running_sum += new_val
                if len(window) > k:
                    oldest_val = window.popleft()
                    running_sum -= oldest_val
                current_avg = running_sum / len(window)
                yield current_avg
    except FileNotFoundError: print("File not found")
    except ValueError: print("Non numeric data founded in stream file")

def mergeIntervals(arr):
    if not arr: return []
    arr.sort(key=lambda x: x[0]) # sort by time
    merged = [arr[0]] # initialize array with first interval[0]
    for i in range(1, len(arr)): # begin from interval 1
        current_start, current_end = arr[i]
        last_merged_start, last_merged_end = merged[-1]
        if current_start <= last_merged_end: # Check for overlap
            merged[-1][1] = max(last_merged_end, current_end) # Merge by updating the end time
        else:
            merged.append([current_start, current_end]) # No overlap, start a new interval in the result
    return merged

from collections import defaultdict

def groupAnagrams(arr):
    anagram_map = defaultdict(list) # Using defaultdict(list) avoids checking if a key exists
    for word in arr:
        sorted_key = "".join(sorted(word)) # Sort the word to create a canonical key 'cat' -> ['a', 'c', 't'] -> 'act'
        anagram_map[sorted_key].append(word) # Group the original word under its sorted key
    return list(anagram_map.values()) # Return all grouped lists as the final result

import re
raw_logs = [
    "[DEBUG] 2023-05-25 10:15:32: Initializing application...",
    "[INFO] 2023-05-25 10:15:35: User 'John' logged in.",
    "[ERROR] 2023-05-25 10:15:40: Database connection failed.",
    "[DEBUG] 2023-05-25 10:15:45: Processing request...",
    "[INFO] 2023-05-25 10:15:50: Request completed successfully."
]
log_pattern = r'\[(\w+)\] (\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}): (.*)'

def clean_logs(raw_logs):
    cleaned_logs = []
    for log in raw_logs:
        match = re.match(log_pattern, log)
        if match:
            log_level, timestamp, message = match.group(1), match.group(2), match.group(3)
            if log_level != 'DEBUG': 
                cleaned_logs.append({'level': log_level, 'timestamp': timestamp, 'message': message})
        else: print("Log entry does not match the expected format:", log)
    return cleaned_logs

import re
from collections import Counter
from datetime import datetime

def aggregate_log_errors(file_path):
    log_pattern = re.compile(r'(\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}) \[(.*?)\]') # Regex breakdown: (\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}) -> Group 1: Timestamp, \[(.*?)\] -> Group 2: Level (inside brackets)
    error_counts = Counter()
    try:
        with open(file_path, 'r', encoding='utf-8') as f:
            for line in f:
                match = log_pattern.search(line)
                if match:
                    timestamp_str, level = match.groups()
                    if level == "ERROR":
                        dt = datetime.strptime(timestamp_str, '%Y-%m-%d %H:%M:%S')
                        hour_bucket = dt.replace(minute=0, second=0)    
                        error_counts[hour_bucket] += 1
        return dict(error_counts)
    except FileNotFoundError:
        print("Log file not found.")
        return {}

stats = aggregate_log_errors('system.log')
for hour, count in sorted(stats.items()): print(f"{hour.strftime('%Y-%m-%d %H:00')} -> {count} errors")

def minWindow(s, p): # p string chars must be in s
    n = len(s)
    if len(p) > n: return ""
    p_map = Counter(p) # char_p: freq
    required = len(p_map) # required len of chars
    window_map, formed = {}, 0 # cur window state, unique chars from p in current window
    res = (float("inf"), None, None) # (len, left, right) len of result, left and right index
    l_i = 0 # start index from left
    for r_i in range(n):
        char = s[r_i]
        window_map[char] = window_map.get(char, 0) + 1 # adding new or increment char in s
        if char in p_map and window_map[char] == p_map[char]: formed += 1 # check char in p_map + same frequency
        while l_i <= r_i and formed == required: # while if formed == reuired and l index <= r index
            char = s[l_i]
            if r_i - l_i + 1 < res[0]: res = (r_i - l_i + 1, l_i, r_i) # save the smallest window indexes
            window_map[char] -= 1 # rem char at left
            if char in p_map and window_map[char] < p_map[char]: formed -= 1
            l_i += 1 # move the pointer
    if res[0] == float("inf"): return ""
    return s[res[1] : res[2] + 1]

print(minWindow("timetopractice", "toc"))

from collections import deque
class Node:
    def __init__(self, val):
        self.data, self.left, self.right = val, None, None
        
class Solution:
    def serialize(self, root):
        if not root: return []
        res, queue = [], deque([root]) #print(queue)
        while queue:
            curr = queue.popleft()
            print(f"Popped left index from queue")
            if not curr:
                res.append(-1)
                print(f"Appended null node into queue {res}")
                continue
            res.append(curr.data)
            queue.append(curr.left)
            queue.append(curr.right)
            print(f"Appended right and left index into queue {res}")
        return res
        
    def deSerialize(self, arr):
        if not arr or arr[0] == -1: return None
        root = Node(arr[0])
        queue = deque([root])
        i = 1
        while queue and i < len(arr):
            curr = queue.popleft()
            if arr[i] != -1: # process left child
                curr.left = Node(arr[i])
                queue.append(curr.left)
            i += 1
            if arr[i] != -1: # process right child
                curr.right = Node(arr[i])
                queue.append(curr.right)
            i += 1
        return root
    
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.right, self.left = val, left, right
        
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string."""
        res = []
        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left), dfs(node.right)
        dfs(root)
        return ",".join(res)

    def deserialize(self, data): # tree data
        """Decodes your encoded data to tree."""
        vals = data.split(",") # split values from tree nodes
        self.i = 0 # Use an iterator to track our position across recursive calls
        def dfs():
            if vals[self.i] == "N":
                self.i += 1
                return None 
            node = TreeNode(int(vals[self.i])) # Create the current node (main operation)
            self.i += 1
            node.left, node.right = dfs(), dfs() # Recursively build left and right subtrees
            return node
        return dfs()
    
def print_tree(node, level=0, prefix="Root: "):
    if node is not None:
        print("  " * level + prefix + str(node.val))
        if node.left or node.right:
            print_tree(node.left, level + 1, "L--- ")
            print_tree(node.right, level + 1, "R--- ")

import re, sys
from collections import Counter
from datetime import datetime

def aggregate_logs(file_path):
    # Pattern to handle messy spacing or slight variations, Handles: 2026-04-24 18:00:00 [ERROR] message
    log_pattern = re.compile(r'(\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2})\s+\[(ERROR|INFO|WARN)\]', re.IGNORECASE)
    error_counts, line_count = Counter(), 0
    try:
        with open(file_path, 'r', encoding='utf-8') as f: # 'with' handles the file closure even if an error occurs
            for line in f:
                line_count += 1
                line = line.strip()
                if not line: continue # Edge case: Skip empty lines
                match = log_pattern.search(line)
                if match:
                    timestamp_str, level = match.groups()
                    if level.upper() == "ERROR":
                        try:
                            dt = datetime.strptime(timestamp_str, '%Y-%m-%d %H:%M:%S')
                            hour_bucket = dt.replace(minute=0, second=0, microsecond=0)
                            error_counts[hour_bucket] += 1
                        except ValueError: continue # Edge case: Valid pattern but invalid date (e.g. Feb 30)
        if not error_counts and line_count > 0: print("Notice: Processed file, but no ERROR logs were found.")
        return error_counts
    except FileNotFoundError: print(f"Error: File '{file_path}' not found."); sys.exit(1)
    except Exception as e: print(f"An unexpected error occurred: {e}"); sys.exit(1)

import heapq
from collections import deque, Counter
from random import randint
from typing import List
# This class maintains a sliding window of the last k prices and allows us to get the mean and median efficiently at any point in time. It uses two heaps to maintain the median and a running sum for the mean. When a new price is added, it adds it to the appropriate heap, removes the oldest price if the window exceeds size k, and then rebalances the heaps. The get_stats method returns the current mean and median of the prices in the window.
class TradingWindow:  # O(log k) time complexity for add_price, O(1) time complexity for get_stats, O(k) space complexity
    def __init__(self, k):
        self.k = k # Window size
        self.max_heap, self.min_heap = [], [] # Smaller half (negated) (we popping biggest number), Larger half (popping smallest number)
        self.to_remove = Counter()  # Lazy removal tracker
        self.window = deque()  # Tracks the actual order of arrival
        self.running_sum = 0.0 # For mean calculation
 
    def add_price(self, price): #time O(nlogk), space O(k)
        self.window.append(price)
        self.running_sum += price       
        heapq.heappush(self.max_heap, -price) if not self.max_heap or price <= -self.max_heap[0] else heapq.heappush(self.min_heap, price) #Add to heaps (same logic as before)
        print(f"max_heap: {self.max_heap} min_heap: {self.min_heap}")
        if len(self.window) > self.k: # Handle Sliding Window: Remove the oldest price
            old_price = self.window.popleft()
            self.running_sum -= old_price
            self.to_remove[old_price] += 1  
            self._clean_heaps() # Clean up tops of heaps if the "old_price" is at the top (Lazy Removal)
        self._rebalance() # Rebalance heaps
        self._clean_heaps() # Final cleanup after rebalance

    def _rebalance(self): #time O(nlogk), space O(1), Max-heap can have at most one more element than min-heap
        if len(self.max_heap) - self.to_remove_in_heap(self.max_heap) > len(self.min_heap) - self.to_remove_in_heap(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) - self.to_remove_in_heap(self.min_heap) > len(self.max_heap) - self.to_remove_in_heap(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def _clean_heaps(self): #time O(nlogk), space O(1)
        while self.max_heap and self.to_remove[-self.max_heap[0]] > 0: # Remove elements from top of max_heap if they are marked for removal
            self.to_remove[-self.max_heap[0]] -= 1
            heapq.heappop(self.max_heap)
        while self.min_heap and self.to_remove[self.min_heap[0]] > 0: # Remove elements from top of min_heap if they are marked for removal
            self.to_remove[self.min_heap[0]] -= 1
            heapq.heappop(self.min_heap)

    def to_remove_in_heap(self, heap): return 0 # tracking "valid" sizes to avoid O(N) heap counting, since we only need to know if we have more than 1 extra in max_heap or not

    def get_stats(self): #time O(1), space O(1)
        mean = self.running_sum / len(self.window)
        median = float(-self.max_heap[0]) if (len(self.max_heap) + len(self.min_heap)) % 2 == 1 else (-self.max_heap[0] + self.min_heap[0]) / 2.0
        return {"mean": mean, "median": median}

# problem: https://projecteuler.net/problem=1
def sum_multiples(n, limit): # time O(1), space O(1)
    k = (limit - 1) // n # Find how many multiples there are (k)
    return n * (k * (k + 1)) // 2 # Use the sum of arithmetic progression formula: n * (k * (k + 1) / 2)
    
def solve_efficiently(limit): return sum_multiples(3, limit) + sum_multiples(5, limit) - sum_multiples(15, limit) # sum of multiples of 3 and 5, but subtract multiples of 15 to avoid double counting

# problem: https://leetcode.com/problems/largest-product-in-a-grid/
def solve_grid_product(grid):
    max_prod = 0
    rows = len(grid); cols = len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if c + 3 < cols: # Check Horizontal (Right)
                prod = grid[r][c] * grid[r][c+1] * grid[r][c+2] * grid[r][c+3]
                max_prod = max(max_prod, prod)
            if r + 3 < rows: # Check Vertical (Down)
                prod = grid[r][c] * grid[r+1][c] * grid[r+2][c] * grid[r+3][c]
                max_prod = max(max_prod, prod)
            if r + 3 < rows and c + 3 < cols: # Down-Right diagonal
                prod = grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3]
                max_prod = max(max_prod, prod)
            if r + 3 < rows and c - 3 >= 0: # Down-Left diagonal
                prod = grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3]
                max_prod = max(max_prod, prod)
    return max_prod

grid_data = [[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8], [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0], [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65], [52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91], [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80], [24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50], [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70], [67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21], [24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72], [21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95], [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92], [16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57], [86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58], [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40], [4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66], [88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69], [4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36], [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16], [20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54], [1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48],]
print(f"The greatest product is: {solve_grid_product(grid_data)}")

import heapq
class MedianFinder: # O(log N) time complexity for addNum, O(1) time complexity for findMedian, O(N) space complexity
    def __init__(self):
        self.small, self.large = [], [] # Max-heap for smaller half, Min-heap for larger half
        
    def addNum(self, num: int) -> None:
        # Always add to small first, then move the largest of small to large
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # Keep small size >= large size. small can have at most ONE more element than large.
        heapq.heappush(self.small, -heapq.heappop(self.large)) if len(self.large) > len(self.small) else None
        
    def findMedian(self) -> float:
        return float(-self.small[0]) if len(self.small) > len(self.large) else (-self.small[0] + self.large[0]) / 2.0 

import heapq
from collections import defaultdict
class SlidingWindowMedian: 
    def medianSlidingWindow(self, nums, k): # O(N log k) time complexity, O(k) space complexity
        small, large = [], [] # Max-heap, Min-heap
        delayed, result = defaultdict(int), []
        def clean(heap, is_small): # clean the tops of heaps
            while heap:
                val = -heap[0] if is_small else heap[0]
                if delayed[val] > 0: 
                    delayed[val] -= 1; heapq.heappop(heap)
                else: break
        print(f"initializing window k={k}") # Initial window
        for i in range(k): heapq.heappush(small, -nums[i]) # Add all to small first
        for _ in range(k // 2): heapq.heappush(large, -heapq.heappop(small)) # Balance the heaps
        clean(small, True)
        clean(large, False)
        # Sliding the window - N is the array length, and logk is the cost of heap/set operations within the window
        for i in range(k, len(nums) + 1):
            median = float(-small[0]) if k % 2 == 1 else (-small[0] + large[0]) / 2.0 # Get current median        
            result.append(median)
            print(f"\n[Step {i-k+1}] Window: {nums[i-k:i]}")
            print(f"  Current Median: {median}")
            print(f"  Heaps: Small(Max)={[-x for x in small]}, Large(Min)={large}")
            if i == len(nums): break
            out_num, in_num = nums[i-k], nums[i] # Prepare to slide: out_num leaves, in_num enters
            print(f"  Action: Removing {out_num}, Adding {in_num}")
            balance = 0
            balance += -1 if out_num <= -small[0] else 1 # Track removal balance
            delayed[out_num] += 1
            if small and in_num <= -small[0]: # Insert new number
                balance += 1
                heapq.heappush(small, -in_num)
            else:
                balance -= 1
                heapq.heappush(large, in_num)
            if balance < 0: heapq.heappush(small, -heapq.heappop(large)) # Rebalance heaps
            elif balance > 0: heapq.heappush(large, -heapq.heappop(small))
            clean(small, True) # Actually clean the tops for the next iteration 
            clean(large, False)
            print(f"Delayed Removals Queue: {dict(delayed)}")
        return result

from collections import deque
def maxSlidingWindow(nums, k): # O(1) time complexity per element, O(1) space complexity
    dq = deque() # stores indices
    result = []
    for i in range(len(nums)):
        if dq and dq[0] < i - k + 1: dq.popleft() # Remove indices that are out of the current window range
        while dq and nums[dq[-1]] < nums[i]: dq.pop() # Remove indices of elements smaller than the current element (They will never be the maximum)
        dq.append(i)
        if i >= k - 1: result.append(nums[dq[0]]) # Add to result once we have a full window
        print(f"Window: {nums[max(0, i-k+1):i+1]}, Deque Values: {[nums[idx] for idx in dq]}")
    return result

from collections import defaultdict
from typing import List
def subarraySum(nums: List[int], k: int) -> int: # O(N) time complexity, O(N) space complexity
        count, current_sum, prefix_sums = 0, 0, {0: 1} # Dictionary to store (prefix_sum: frequency), We initialize with {0: 1} to handle cases where current_sum == k
        for num in nums:
            current_sum += num
            target = current_sum - k # check if current_sum - k has occured before
            if target in prefix_sums:
                count += prefix_sums[target]
            prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1 # record the current sum in the map
            print(f"Num: {num}, Current Sum: {current_sum}, Target: {target}, Count: {count}, Prefix Sums: {prefix_sums}")
        return count

def longestConsecutive(nums: List[int]) -> int: # O(N) time complexity, O(N) space complexity
        num_set = set(nums) # Convert to set fot O(1) lookups
        longest_streak = 0
        for num in num_set:
            if (num - 1) not in num_set: # check if it's the start of a sequence
                current_num = num
                current_streak = 1
                while (current_num + 1) in num_set: # build the sequence
                    current_num += 1
                    current_streak += 1                
                longest_streak = max(longest_streak, current_streak)
        return longest_streak

def areBracketsProperlyMatched(code_snippet): # O(N) time complexity, O(N) space complexity
    stack, mapping = [], {")": "(", "}": "{", "]": "["}
    for char in code_snippet:
        if char in "({[": stack.append(char)
        elif char in ")}]":
            if not stack or stack[-1] != mapping[char]: return(0) # stack empty or mismatch at top
            stack.pop()
        print(f"Char: {char}, Stack: {stack}")
    return 1 if not stack else 0 # valid only if stack is empty

def findTaskPairForSlot(taskDurations, slotLength): # O(N) time complexity, O(N) space complexity
    seen = {} # map to store {value: index}
    for i, duration in enumerate(taskDurations):
        complement = slotLength - duration
        print(f"Task Duration: {duration}, Complement: {complement}, Seen Map: {seen}, Index: {i}")
        if complement in seen: return [seen[complement], i] # look for the complemnt in our notebook
        seen[duration] = i # record this duration and its position
    return [-1, -1]

def findNextGreaterElementsWithDistance(readings): #O(N) time complexity, O(N) space complexity
    n = len(readings) # Write your code here
    result = [[-1, -1] for _ in range(n)] # initialize the result array with [-1, -1] for all indices
    stack = [] # This stack will store the indices of the readings that are 'waiting' to find their next greater element.
    for i in range(n):
        while stack and readings[i] > readings[stack[-1]]: # While the current reading is greater than the reading at the index stored at the top of the stack.
            popped_index = stack.pop() # We found the next greater element for the index at stack top
            next_greater_value = readings[i] # calculate the value and the distance 
            distance = i - popped_index
            result[popped_index] = [next_greater_value, distance] # store the result for that specific index
        stack.append(i) # push the current index into stack            
    return result

def computeMaxRectangleAreaWithOneRemoval(heights): # O(N) time complexity, O(N) space complexity
    n = len(heights)
    if n == 0: return 0
    if n == 1: return heights[0] # Removing it gives 0, keeping it gives heights[0]
    left, right = [-1] * n, [n] * n # standard boundaries
    stack = []
    for i in range(n): # find the nearest smaller to the left
        while stack and heights[stack[-1]] >= heights[i]: stack.pop()
        if stack: left[i] = stack[-1]
        stack.append(i)
    stack = []
    for i in range(n-1, -1, -1): # find nearest smaller to the right
        while stack and heights[stack[-1]] >= heights[i]: stack.pop()
        if stack: right[i] = stack[-1]
        stack.append(i)
    left2 = [-1] * n # second order boundaries, next smaller element
    for i in range(n):
        idx = left[i]
        if idx != -1: left2[i] = left[idx]    
    right2 = [n] * n
    for i in range(n):
        idx = right[i]
        if idx != n: right2[i] = right[idx]
    max_area = 0
    for i in range(n): # calculate max area for each bar
        w1 = right[i] - left[i] - 1 # standard area
        max_area = max(max_area, heights[i] * w1)      
        if left[i] != -1: # Remove left boundary bar
            w2 = right[i] - left2[i] - 2
            max_area = max(max_area, heights[i] * w2)
        if right[i] != n: # remove the right boundary bar
            w3 = right2[i] - left[i] - 2
            max_area = max(max_area, heights[i] * w3)
    return max_area

def getTopKFrequentEvents(events, k): # O(N) keys calculated, O(N log N) time complexity due to sorting, O(N) space complexity
    if not events or k == 0: return []
    first_occurence = {} # map to store first occurence index
    for i, val in enumerate(events):
        if val not in first_occurence:
            first_occurence[val] = i
            print(f"First occurence of event {val} at index {i}")
    counts = Counter(events) # count frequencies
    unique_elemnents = list(counts.keys()) # get unique elemnets
    unique_elemnents.sort(key=lambda x: (-counts[x], first_occurence[x])) # sort with custom key, -counts[x] makes it descending for frequency
    print(f"Events: {events}, Counts: {counts}, First Occurence: {first_occurence}, Sorted Unique Elements: {unique_elemnents}")
    return unique_elemnents[:k] # return top k

from collections import OrderedDict
class PriorityLRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.cache = {} # map: key -> [value, priority]
        self.priority_lists = {} #priority_map: priority -> OrderedDict(key -> None)
        self.min_priority = float("inf") # # To keep eviction O(1), we need to track the lowest priority
    
    def get(self, key):
        if key not in self.cache: return -1
        val, prio = self.cache[key]
        self.priority_lists[prio].move_to_end(key) # refresh LRU status within its priority list
        return val
    
    def _evict(self):
        min_prio = min(self.priority_lists.keys()) # To keep this O(1), we'd ideally use a sorted tracker
        evict_key, _ = self.priority_lists[min_prio].popitem(last=False) # pop the oldest (first) item from the lowest priority list
        del self.cache[evict_key]
        if not self.priority_lists[min_prio]: # clean up empty priority lists
            del self.priority_lists[min_prio]
        self.size -= 1
        
    def put(self, key, value, priority):
        if key in self.cache:
            old_val, old_prio = self.cache[key] # remove from old priority list
            del self.priority_lists[old_prio][key]
            if not self.priority_lists[old_prio]:
                del self.priority_lists[old_prio]
            self.size -= 1        
        if self.size >= self.capacity: self._evict()
    
        self.cache[key] = [value, priority]
        if priority not in self.priority_lists:
            self.priority_lists[priority] = OrderedDict()
        self.priority_lists[priority][key] = None
        self.size += 1
    
    def updatePriority(self, key, new_prio):
        if key not in self.cache: return
        val, old_prio = self.cache[key]
        del self.priority_lists[old_prio][key] # move between priority lists
        if not self.priority_lists[old_prio]: 
            del self.priority_lists[old_prio]   
        self.cache[key] = [val, new_prio]
        if new_prio not in self.priority_lists:
            self.priority_lists[new_prio] = OrderedDict()
        self.priority_lists[new_prio][key] = None
    
def simulatePriorityCache(capacity, numOperations, operationTypes, keys, values, priorities):
    cache = PriorityLRUCache(capacity)
    results = []
    for i in range(numOperations):
        op, k, v, p = operationTypes[i], keys[i], values[i], priorities[i]
        if op == "put": cache.put(k, v, p) #  time O(P), space O(C)
        elif op == "get": results.append(cache.get(k))  # time O(1), space O(1)
        elif op == "updatePriority": cache.updatePriority(k, p) # time O(1), space O(1)
    return results

# problem: https://leetcode.com/problems/number-of-1-bits/
def hammingWeight(n: int) -> int: 
    count = 0
    while n:
        n &= (n - 1) # This flips the rightmost set bit to 0
        count += 1
        print(f"Current n: {n}, Count: {count}")
    return count

def reverseBits(n: int) -> int:     
    result = 0
    for _ in range(32):
        result <<= 1        # Shift result left to make space
        result |= (n & 1)   # Grab the last bit of n and put it in the new space
        n >>= 1             # Shift n right to get the next bit ready
        print(f"result: {result}, n: {n}")
    return result

class MyQueue:
    def __init__(self):
        self.stack_in, self.stack_out = [], []
    def enqueue(self, x):
        self.stack_in.append(x)
    def _transfer(self):
        if not self.stack_out: # Only transfer if stack_out is empty to preserve FIFO order
            while self.stack_in: self.stack_out.append(self.stack_in.pop())
    def dequeue(self): # When we dequeue or peek, we first transfer elements from stack_in to stack_out if stack_out is empty. This way, the oldest element (the one that was enqueued first) will be on top of stack_out, allowing us to maintain the correct order for the queue operations.
        self._transfer()
        if self.stack_out: return self.stack_out.pop()
    def peek(self): # The peek operation is similar to dequeue, but instead of popping the element from stack_out, we just return it. This allows us to see the front of the queue without modifying it.
        self._transfer()
        if self.stack_out: return self.stack_out[-1]
    def empty(self):
        return not self.stack_in and not self.stack_out

from collections import defaultdict
def freqQuery(queries):
    counts = defaultdict(int) #number(number of occurrences) -> frequency(how many numbers have that occurrence)
    frequencies = defaultdict(int) #frequency(frequency of occurrences) -> count of numbers having that frequency
    results = []
    for op, val in queries:
        if op == 1: # insert x
            if counts[val] > 0: frequencies[counts[val]] -= 1
            counts[val] += 1
            frequencies[counts[val]] += 1 # Add one instance of new frequency
        elif op == 2: # delete one occurrence of y
            if counts[val] > 0:
                frequencies[counts[val]] -= 1 # Remove one instance of old frequency
                counts[val] -= 1
                if counts[val] > 0: # If still > 0, add to the lower frequency level
                    frequencies[counts[val]] += 1
        elif op == 3: # check z occurs with exactly z frequency
            if frequencies[val] > 0: results.append(1)
            else: results.append(0)
        print(f"Operation: {op}, Value: {val}, Counts: {dict(counts)}, Frequencies: {dict(frequencies)}, Results: {results}")
    return results

if __name__ == "__main__":
    print(parse_intervals("5-7,7-9")) # True, if intervals intersecting, time O(1), space O(1)
    read_text("data/assignment_pairs.txt") # parsing intervals from file, time O(N), space O(1)
    changes = process_diff_file('data/changes.diff') #time O(N), space O(B)
    for bucket, net in sorted(changes.items()): # lines in buckets
         print(f"Original Lines {bucket*10}-{(bucket+1)*10-1}: Net Change {net}")
    json_to_csv("data/data.json", "data/output.csv") # time O(K), space O(K) converting recursively data from json to csv with headers and values, 
    for moving_avg in analyze_sensor_stream("data/sensors.txt", k=3): # counting moving average from input file window, time O(N), space O(k) 
        print(f"Current signal: {moving_avg:.2f}")
    print(mergeIntervals([[1, 3], [2, 4], [6, 8], [9, 10]])) 
    print(groupAnagrams(["act", "god", "cat", "dog", "tac"]))
    cleaned_logs = clean_logs(raw_logs) #time O(NL), space O(N)
    for log in cleaned_logs: print(log)
    tree = Solution()
    reconstructed_array = tree.deSerialize([10, 20, 30, 40, 60, "N", "N"])
    deserialized_array = tree.serialize(reconstructed_array)
    print(f"Reconstructed array: {deserialized_array}")
    root = TreeNode(1) # create a tree from nodes, define root node
    root.left, root.right = TreeNode(2), TreeNode(3) # define left and right nodes in root node  
    root.right.left, root.right.right = TreeNode(4), TreeNode(5) # define right and left nodes in the right node of root node
    print_tree(root)
    codec = Codec()
    serialized_data = codec.serialize(root)
    print(f"\n--- Serialized String (Text Data) ---\n{serialized_data}")
    reconstructed_root = codec.deserialize(serialized_data)
    print("\n--- Reconstructed Tree Structure ---")
    print_tree(reconstructed_root)
    tracker = TradingWindow(k=3) 
    for p in [randint(1, 100) for _ in range(10)]:
        tracker.add_price(p)
        print(f"Price: {p} -> {tracker.get_stats()}")
    print(solve_efficiently(1000)) #time O(1), space O(1)
    import math; print(math.comb(40, 20)) # problem: https://leetcode.com/problems/sliding-window-median/
    median = MedianFinder() 
    for num in [1, 2, 3, 4]:
        median.addNum(num) # time O(logn), space O(N)
        print(f"Added {num}, current median: {median.findMedian()}") #time O(1), space O(1)   
    SlidingWindowMedian().medianSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) #time O(nlogk), space O(k)
    maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) #time O(N), space O(k)
    print(subarraySum([1, 1, 1], 2)) #time O(N), space O(N)
    print(subarraySum([1, 2, 3], 3))
    print(longestConsecutive([100, 4, 200, 1, 3, 2])) #time O(N), space O(N)
    print(longestConsecutive([0,3,7,2,5,8,4,6,0,1]))
    print(longestConsecutive([1,2,0,1]))
    print(int(areBracketsProperlyMatched("()"))) # time O(N), space O(N)
    print(findTaskPairForSlot([2, 7, 11, 15], 9)) # time O(N), space O(N)
    print(findTaskPairForSlot([1, 2, 3, 4], 8))
    print(findNextGreaterElementsWithDistance([4, 5, 2, 10, 8])) # time O(N), space O(N)
    print(computeMaxRectangleAreaWithOneRemoval([5, 5, 1, 5, 5])) # time O(N), space O(N)
    print(getTopKFrequentEvents([4, 4, 1, 2, 2, 3, 1, 3, 2], 3)) # time O(nlogn), space O(N)
    print(simulatePriorityCache(2, 9, ['put', 'put', 'get', 'put', 'get', 'updatePriority', 'put', 'get', 'get'], [1, 2, 1, 3, 2, 3, 4, 3, 4], [10, 20, 0, 30, 0, 0, 40, 0, 0], [1, 2, 0, 1, 0, 3, 1, 0, 0])) 
    hammingWeight(11) # 1011 in binary has 3 set bits,  time O(log n), space O(1)
    hammingWeight(128) 
    import numpy as np
    signal = np.array([11, 128, 255], dtype=np.uint8)
    print(np.vectorize(lambda x: bin(x).count('1'))(signal))
    print(reverseBits(43261596)) #  time O(1), space O(1)
    print("Testing MyQueue implementation: ")    
    queue = MyQueue() 
    queue.enqueue(42); print(queue.peek()) # Should print 42, time O(1), space O(1)
    queue.dequeue(); print(queue.empty()) # Should print True,  time O(N) amortized O(1), space O(1)
    queue.enqueue(14); print(queue.peek()) # time O(N) amortized O(1), space O(1) 
    queue.enqueue(28); print(queue.peek())
    queue.enqueue(60) 
    queue.enqueue(78)
    queue.dequeue(); print(queue.peek()) # Should print 28
    queue.dequeue(); print(queue.peek()) # Should print 60
    print(freqQuery([[1, 5],[1, 6],[3, 2],[1, 10],[1, 10],[1, 6],[2, 5],[3, 2]])) # # time O(Q), space O(N)