data_algorithms.py

# arrays, datastructures, prefix_sums, heaps, stacks queue, strings, bits, sorting, sliding windows, binary search
def subarraySum(arr, target):
    prefix_sum = 0; seen_sums = {0: 0} # map stores sum_value: index, indicating with 0: -1 to starting at index 0
    for i, num in enumerate(arr):
        current_idx = i + 1
        prefix_sum += num
        needed = prefix_sum - target # previuos sum = prefix_sum - target
        #print(f"Iteration: {i}, Prefix_sum: {prefix_sum}, needed: {needed}, seen sums: {seen_sums}")
        if needed in seen_sums:
            start_index = seen_sums[needed] + 1
            return [start_index, current_idx]
        if prefix_sum not in seen_sums: seen_sums[prefix_sum] = current_idx
    return [-1]

def maxSubarraySum(arr):
    max_so_far, current_max = arr[0], arr[0]
    for i in range(1, len(arr)): # start from second element
        current_max = max(arr[i], current_max + arr[i]) # Is the current number better off alone, or joined with previous subarray
        print(f"max: {current_max}")
        max_so_far = max(max_so_far, current_max) # update global maximum if the current "local" maximum is higher
        print(f"max_so_far: {max_so_far}")
    return max_so_far

def minJumps(arr):
    n = len(arr)
    if n <= 1: return 0 
    if arr[0] == 0: return -1
    farthest, current_end, jumps = 0, 0, 0
    for i in range(n-1): # we dont need to jump once on last index
        farthest = max(farthest, i + arr[i]) # update the farthest point reachable from current index i
        print(f"Farthest: {farthest}")
        if i == current_end: # if we reached the end of the range for the current map
            jumps += 1; current_end = farthest; 
            if current_end <= i and i < n - 1: return -1 # check if we stuck and cannot reach the end
        print(f"Current end: {current_end}, Jumps: {jumps}")
    return jumps if current_end >= n - 1 else -1

def mergeIntervals(arr):
    if not arr: return []
    arr.sort(key=lambda x: x[0]) # sort by time
    merged = [arr[0]]
    for i in range(1, len(arr)):
        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

def findPlatform(arr, dep):
    arr.sort(); dep.sort()
    n = len(arr)
    i, j, platforms_needed, max_platforms = 0, 0, 0, 0
    while i < n:
        if arr[i] <= dep[j]: # If a train arrives before (or at the same time) the next departure
            platforms_needed += 1
            i += 1
        else: # If a train departs before the next arrival
            platforms_needed -= 1
            j += 1
        print(f"i = {i}, j = {j}, platforms needed: {platforms_needed}, max_platforms: {max_platforms}")
        max_platforms = max(max_platforms, platforms_needed) # Update the global peak    
    return max_platforms

import bisect
def maximum_profit(n, intervals):
    intervals.sort(key=lambda x: x[1]) # Sort intervals by end time - O(n log n)
    end_times = [x[1] for x in intervals] # Extract end times to use for Binary Search
    dp = [0] * (n+1) # dp[i] will store the max profit using up to the i-th interval, We use a 1-based DP array for easier indexing    
    for i in range(1, n+1):
        start, end, profit = intervals[i-1]
        res_exclude = dp[i-1] 
        idx = bisect.bisect_right(end_times, start) # bisect_right finds the first index where end_time > current_start, Moving one index back gives us the latest valid interval
        res_include = profit + dp[idx]
        dp[i] = max(res_exclude, res_include) # Maximize the result for the current state
    return dp[n]

def missingIntervals(arr, l, r):
    results, current_expected = [], l
    for num in arr:
        if num < current_expected: continue
        if num > r: break
        if num > current_expected: results.append([current_expected, num - 1])
        current_expected = num + 1
    if current_expected <= r: results.append(([current_expected, r]))
    return results if results else [[-1, -1]]

def minRemoval(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[1])
    count_keep, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end: # If no overlap, we keep this interval
            count_keep += 1
            last_end = end 
        # If there is an overlap, we implicitly "remove" it by doing nothing
    return len(intervals) - count_keep # Result is Total Intervals - Intervals we kept

from collections import deque
def firstNonRepeating(s):
    char_count, queue, result = [0] * 26, deque(), [] # frequency array for 'a'-'z'
    for char in s:
        char_count[ord(char) - ord('a')] += 1
        queue.append(char) # Add to sequence queue
        while queue: # Remove characters from front that are now repeating
            front_char = queue[0]
            if char_count[ord(front_char) - ord('a')] > 1: queue.popleft()
            else: break # Found the first non-repeating
        if not queue: result.append('#')  # Append result for this prefix
        else: result.append(queue[0])
    return "".join(result)

def longestSubarray(arr, k):
    prefix_map, current_sum, max_len = {}, 0, 0
    for i, num in enumerate(arr):
        current_sum += num    
        print(f"Current sum: {current_sum}")
        if current_sum == k: max_len = i + 1  # The current prefix itself equals k
        target = current_sum - k # Check if (current_sum - k) exists in our map
        if target in prefix_map: max_len = max(max_len, i - prefix_map[target]) # Calculate length and update max_len
        print(f"Target: {target}, Max length: {max_len}")
        if current_sum not in prefix_map: prefix_map[current_sum] = i # This preserves the earliest index, ensuring we find the LONGEST subarray.
        print(f"Prefix map: {prefix_map}")
    return max_len

def maxLen(arr):
    prefix_map, current_sum, max_length = {}, 0, 0 # map: prefix_sum -> earliest_index
    for i, num in enumerate(arr):
        current_sum += num
        if current_sum == 0: max_length = i + 1 # The sum from the start is 0
        if current_sum in prefix_map: # We have seen this sum before
            length = i - prefix_map[current_sum] # The subarray between the previous occurrence and now sums to 0
            max_length = max(max_length, length)
        else:
            prefix_map[current_sum] = i # New sum, store its index, We ONLY store if it's not present to keep the earliest index
        print(f"Index: {i}, Num: {num}, CurrentSum: {current_sum}")
    return max_length

from collections import deque
def max_of_subarrays(arr, k):
    n, q, result = len(arr), deque(), []; print(arr)
    for i in range(n):
        if q and q[0] <= i - k: q.popleft() # Remove indices that are out of this window    
        while q and arr[q[-1]] <= arr[i]: q.pop() # Remove indices of elements smaller than current element because they will never be the maximum again
        q.append(i) # Add current element's index
        if i >= k - 1: result.append(arr[q[0]]) # Once we have hit the first full window, record the max nasledujicí index
        print(f"i = {i}, q = {q}, result = {result}")    
    return result

def findLongestConseqSubseq(arr):
    s, longest_streak = set(arr), 0
    for num in s:
       if (num - 1) not in s:
            current_num = num
            current_streak = 1  # 2. Check if 'num' is the start of a sequence, If num - 1 is not in the set, then num is a starting point
            while (current_num + 1) in s: # 3. Count how long the sequence goes
                current_num += 1
                current_streak += 1
            longest_streak = max(longest_streak, current_streak) # Update the global maximum
    return longest_streak

class Node:
    def __init__(self, key, value):
        self.key, self.value = key, value
        self.prev, self.next = None, None

class LRUCache:
    def __init__(self, cap):
        self.cap = cap
        self.cache = {} # Map: key -> Node
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head
    def _remove(self, node):
        """Unlink a node from its current position in the DLL."""
        p, n = node.prev, node.next
        p.next, n.prev = n, p # node.prev.next = node.next, node.next.prev = node.prev
    def _add(self, node):
        """Always add new node right after the head (Most Recently Used)."""
        after_head = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = after_head
        after_head.prev = node
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node); self._add(node)
            print(f"DEBUG GET: Key {key} with value found. Moving to Head.")
            return node.value
        print(f"DEBUG GET: Key {key} not found.")
        return -1
    def put(self, key, value):
        if key in self.cache: # Update existing key
            node = self.cache[key]
            node.value = value
            self._remove(node); self._add(node)
            print(f"DEBUG PUT: Updated Key {self.cache[key]}. Moving to Head.")
        else:
            if len(self.cache) >= self.cap: # Add new key
                lru = self.tail.prev # Evict Least Recently Used (node before tail)
                print(f"DEBUG PUT: Capacity reached. Evicting LRU Key: {lru.key}")
                self._remove(lru)
                del self.cache[lru.key]    
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add(new_node)
            print(f"DEBUG PUT: Inserted Key {key}.")

def remAnagram(s1, s2):
    freq = [0] * 26 # Use a frequency array of size 26 for 'a'-'z'
    for char in s1: freq[ord(char) - ord('a')] += 1 # Increment for string 1
    for char in s2: freq[ord(char) - ord('a')] -= 1 # Decrement for string 2
    print(f"{freq}")
    deletions = 0 # The total deletions needed is the sum of absolute differences
    for count in freq: deletions += abs(count)
    return deletions

def nonRepeatingChar(s):
    char_count = [0] * 26
    for char in s: char_count[ord(char)-ord("a")] += 1
    for char in s: 
        if char_count[ord(char)-ord("a")] == 1: return char
    return -1

def reverseWords(s):
    words = s.split('.') # Split the string by dots, Result for "..geeks..for.": ['', '', 'geeks', '', 'for', ''] 
    valid_words = [w for w in words if w] # Filter out empty strings (caused by extra dots) Using a list comprehension is highly optimized in Python
    valid_words.reverse() # Reverse the order of the list
    return ".".join(valid_words) # Join with a single dot

def reverseString(s): return s[::-1]

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]: return False
        left += 1
        right -= 1
    return True

import math
def factorial(n):
    result = math.prod(range(1, n+1))
    digit_list = [int(d) for d in str(result)]
    return digit_list 

def nextGreaterElement(arr):
    n = len(arr); result, stack = [-1] * n, [] # store indices
    #print(n, result, stack)
    for i in range(n): # 2*n, current_element = arr[i%n]
        while stack and arr[i] > arr[stack[-1]]: # While current element is greater than the element corresponding to the index at the top of the stack
            result[stack.pop()] = arr[i]    
        stack.append(i) # Push current index onto stack to find its NGE later
    return result

def nextGreaterElementCircular(arr):
    n = len(arr); result, stack = [-1] * n, [] # store indices
    #print(n, result, stack)
    for i in range(2 * n): # Iterate twice to simulate circularity
        num = arr[i % n]
        while stack and arr[stack[-1]] < num: result[stack.pop()] = num
        if i < n: stack.append(i) # Only push to stack during the first pass            
    return result

def getMaxArea(arr):
    n, stack, max_area = len(arr), [], 0
    for i in range(n + 1):
        current_height = arr[i] if i < n else 0 # We use a 'dummy' height of 0 at the end to clear the stack
        while stack and current_height < arr[stack[-1]]: # While the current bar is shorter than the bar at stack top
            height = arr[stack.pop()]
            width = i if not stack else i - stack[-1] - 1 #Width is determined by the distance between the current index (right boundary) and the new top of the stack (left boundary)
            print(f"i: {i}, width: {width} height: {height}")
            max_area = max(max_area, height * width)
        stack.append(i)
        print(stack)
    return max_area

def trappingWater(arr):
    if not arr: return 0
    n = len(arr)
    left, right = 0, n - 1
    l_max, r_max, total_water = 0, 0, 0
    while left <= right:
        if arr[left] <= arr[right]: # We always process the side with the lower boundary
            if arr[left] >= l_max: l_max = arr[left] # Update the left wall
            else: total_water += l_max - arr[left] # Water trapped here
            left += 1
        else:
            if arr[right] >= r_max: r_max = arr[right] # Update the right wall
            else: total_water += r_max - arr[right] # Water trapped here
            right -= 1
    return total_water

def calculateSpan(arr):
    n = len(arr)
    span, stack = [0] * n, [] # Stores indices, LIFO
    for i in range(n):
        while stack and arr[stack[-1]] <= arr[i]: stack.pop() # Pop elements from stack while they are smaller than or equal to current price
        if not stack: span[i] = i + 1 # If stack is empty, current price is the greatest so far
        else: span[i] = i - stack[-1] # Span is the distance between current index and the nearest greater index
        stack.append(i) # Push current index to stack
    return span

import heapq
def getMedian(arr):
    small_heap, large_heap = [], [] # max-heap, min-heap
    result = []
    for num in arr:
        heapq.heappush(small_heap, -num)
        heapq.heappush(large_heap, -heapq.heappop(small_heap))
        if len(large_heap) > len(small_heap): heapq.heappush(small_heap, -heapq.heappop(large_heap))
        median = float(-small_heap[0]) if len(small_heap) > len(large_heap) else (-small_heap[0] + large_heap[0]) / 2.0
        print(f"i={num}, {small_heap}, {large_heap}")
        result.append(median)
    return result

import heapq
def kthLargest(k, arr):
    min_heap, result = [], [] 
    for num in arr:
        heapq.heappush(min_heap, num) # Add current element to the pool
        #print(min_heap)
        if len(min_heap) > k: heapq.heappop(min_heap) # pop the smallest element 
        if len(min_heap) < k: result.append(-1) # If we havent reached k elements, the top is the kth largest
        else: result.append(min_heap[0]) # from left of the heap
        #print(result)  
    return result

from collections import deque
def firstNegativeInWindow(arr, k):
    n, q, result = len(arr), deque(), []
    for i in range(n): # 0-n
        if arr[i] < 0: q.append(i) # Add current element's index if it is negative    
        if q and q[0] <= i - k: q.popleft() # Remove indices that are out of the window [i-k+1, i], An index is out of bounds if it is <= i - k    
        if i >= k - 1: # Once we hit the first full window, record the first negative
            if q: result.append(arr[q[0]])
            else: result.append(0)
    return result

from collections import deque
class myStack:
    def __init__(self):
        self.q = deque()
    def push(self, x):
        n = len(self.q)
        self.q.append(x)
        print(f"Appended x: {x} to {self.q}")
        for _ in range(n):
            self.q.append(self.q.popleft())
        print(f"Rearranged: {self.q}")
    def pop(self):
        if not self.q: return
        self.q.popleft()
        print(f"Popped from list: {self.q}")
    def top(self):
        if not self.q: return -1
        return self.q[0]
    def size(self):
        return len(self.q)

import heapq
def mergeKArrays(mat):
    n, m = len(mat), len(mat[0]) #rows len, column len
    print(f"rows: {n}, column: {m}")
    min_heap, result = [], []
    for i in range(n): heapq.heappush(min_heap, (mat[i][0], i, 0)) # Push the first element of each row into the heap (value, row_index, element_index)
    #print(min_heap)
    while min_heap:
        val, r, c = heapq.heappop(min_heap)
        #result.append(val)    
        print(min_heap)
        if c + 1 < m: heapq.heappush(min_heap, (mat[r][c+1], r, c+1)) #print(min_heap) If there is a next element in the same row, push it  
    return result

def heapify(arr, n, i):
    """Restores the Max-Heap property for a subtree rooted at index i."""
    largest = i; left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]: largest = left # Check if left child exists and is greater than root
    if right < n and arr[right] > arr[largest]: largest = right # Check if right child exists and is greater than current largest
    if largest != i: # If largest is not root, swap and continue heapifying
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Build Max-Heap Start from last non-leaf node: (n//2 - 1)
    for i in range(n - 1, 0, -1): # Extract elements one by one
        arr[i], arr[0] = arr[0], arr[i] # Swap current root to the end
        heapify(arr, i, 0) # Heapify the reduced heap
    return arr

def countSetBits(n):
    count = 0
    while n > 0:
        n = n & (n - 1) #;print(n) summing bit numbers
        count += 1
    return count

def findUnique(arr):
    unique = 0
    for num in arr:
        unique ^= num
    return unique

def isPowerOfTwo(n):
    if n <= 0: return False # Power of 2 must be greater than 0
    return (n & (n - 1)) == 0 # Bitwise trick: n & (n - 1) removes the only set bit. If the result is 0, it was a power of 2.

def bitMultiply(N):
    original_n, bit_count = N, 0
    n = N # Count set bits (O(log N) complexity) The number of iterations is equal to the number of set bits
    while n > 0:
        n = n & (n - 1)
        bit_count += 1    
    return original_n * bit_count # Return the product

def canPlace(stalls, k, dist): # Can we place k cows such that every cow is at least mid distance apart?
    count, last_pos = 1, stalls[0] # Place the first cow in the first stall
    for i in range(1, len(stalls)):
        if stalls[i] - last_pos >= dist:
            print(f"{stalls[i] - last_pos} is >= {dist}, thus count+=1 and last_post = {stalls[i]}({i})")
            count += 1; last_pos = stalls[i]
            if count >= k: return True
    return False
        
def aggressiveCows(stalls, k):
    stalls.sort() # O(N log N)
    low, high = 1, stalls[-1] - stalls[0]
    print(f"Sorted: {stalls}, low: {low}, high number: {high}")
    pos = 0
    while low <= high: # while number high is <= 0 number
        mid_dist = (low + high) // 2 # mid number distance from array 
        print(f"mid_dist: {mid_dist}")
        if canPlace(stalls, k, mid_dist): # can place between neighbor positions >= mid nuber
            print("Now count >= k")
            pos = mid_dist  # Potential answer found
            low = mid_dist + 1 # Try to find a larger minimum distance
        else:
            high = mid_dist - 1  # Distance too large, decrease it
    return pos

def minSum(arr):
    arr.sort()
    n, s1, s2 = len(arr), [], []
    for i in range(n):
        if i % 2 == 0: s1.append(arr[i])
        else: s2.append(arr[i])
    i, j = len(s1) - 1, len(s2) - 1 
    res, carry = [], 0
    while i >= 0 or j >= 0 or carry:
        val1 = s1[i] if i >= 0 else 0
        val2 = s2[j] if j >= 0 else 0
        total = val1 + val2 + carry
        res.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    final_str = "".join(res[::-1]).lstrip('0')
    return final_str if final_str else "0"

def findMinimum(arr):
    low, high = 0, len(arr) - 1
    while (high - low) > 3: # We narrow down the range until it's very small
        m1, m2 = (high - low)//3 + low, -(high - low) // 3 + high 
        print(f"m1: {m1}, m2: {m2}, high: {high}, low: {low}")
        if arr[m1] < arr[m2]: high = m2 # Minimum is in the first two segments
        else: low = m1 # Minimum is in the last two segments
    min_idx = low # Exhaustive search for the last remaining elements
    for i in range(low + 1, high + 1):
        if arr[i] < arr[min_idx]: min_idx = i
    return min_idx

def findPages(arr, k):
    if k > len(arr): return -1
    def is_possible(mid_limit):
        students, current_sum = 1, 0
        for pages in arr:
            if current_sum + pages > mid_limit:
                students += 1
                current_sum = pages
            else:
                current_sum += pages
        print(f"Possible students: {students}, current sum: {current_sum}")
        return students <= k
    low, high = max(arr), sum(arr)
    print(f"Founded low(max(arr)): {low} and high(sum(arr)): {high}")
    pos_ans = high
    while low <= high: # binary search
        mid = (low + high) // 2
        print(f"Mid: {mid}")
        if is_possible(mid):
            pos_ans = mid
            high = mid - 1
            print(f"New high: {high}")
        else:
            low = mid + 1
            print(f"New low: {low}")
    return pos_ans

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

from collections import Counter
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]

def startStation(gas, cost):
    if sum(gas) < sum(cost): return -1
    total_tank, start_index, current_tank = 0, 0, 0
    for i in range(len(gas)):
        current_tank += gas[i] - cost[i]
        print(f"We are at: {current_tank}")
        total_tank += gas[i] - cost[i]
        if current_tank < 0:
            start_index = i + 1 # Move the start to the next station, update index until cost is less that gas
            current_tank = 0 # Reset current tank for the new starting attempt
    print(f"Total round sum: {total_tank}, Starting index station at: {start_index} ")
    return start_index

from collections import defaultdict
def countSubarrays(arr, k):
    prefix_sums = defaultdict(int) # prefix_sum: freq
    prefix_sums[0] = 1 # empty prefix, has been seen once
    current_sum, count = 0, 0 
    for x in arr:
        current_sum += x
        if (current_sum - k) in prefix_sums: # If (current_sum - k) exists in our map, it means there are subarrays ending here that sum to k.
            count += prefix_sums[current_sum - k] # Sj = Si - k
            print(f"Count increased: {count}")
        prefix_sums[current_sum] += 1 # Add the current_sum to the map for future encounters
        print(f"Actual sums: {prefix_sums}")
    #print(f"Founded in {arr}, with sums {prefix_sums}, {count} subarrays equal: {k}")    
    return count

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """Inserts a word into the trie."""
        node = self.root #TrieNode() instance
        for char in word: # go through all chars in word
            if char not in node.children:
                node.children[char] = TrieNode() # if dont esist create new
            node = node.children[char] # move node to the child node 
        node.is_end_of_word = True # if Im at the end of the node

    def search(self, word):
        """Returns True if the word is in the trie."""
        node = self.root
        for char in word:
            if char not in node.children: return False
            node = node.children[char]
        return node.is_end_of_word

    def isPrefix(self, prefix):
        """Returns True if there is any word in the trie that starts with the given prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children: return False
            node = node.children[char]
        return True

def print_trie(node, word_fragment="", indent=0):
    status = "*" if node.is_end_of_word else "" # Mark the end of a full word with '*' for clarity
    if word_fragment: print("  " * indent + "|-- " + word_fragment + status)
    for char in sorted(node.children.keys()): print_trie(node.children[char], char, indent + 1)

def minNumber(arr, low_i, high_i):
    if arr[low_i] <= arr[high_i]: return arr[low_i]
    while low_i < high_i: # 0, 9
        mid_i = low_i + (high_i - low_i) // 2 # differ round number if smaller it is 0
        print(mid_i)
        if arr[mid_i] > arr[high_i]: low_i = mid_i + 1# If middle element is greater than the last element, the minimum must be in the right half.    
        else: high_i = mid_i # Otherwise, the minimum is in the left half (including mid)
    print(f"Min element is at index {low_i} which is {arr[low_i]}")
    return arr[low_i]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left, self.right = 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):
        """Decodes your encoded data to tree."""
        vals = data.split(",")
        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
            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--- ")

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, i = deque([root]), 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

if __name__ == "__main__":
    print(subarraySum([1, 2, 3, 7, 5], 12)) # time O(N), space O(N) find subarray sum equal target number
    print(subarraySum([0, 0, 1, 4], 5),"\n")
    print(maxSubarraySum([2, 3, -8, 7, -1, 2, 3])) # time O(N), space O(1) find maximal subarray sum
    #print(maxSubarraySum([1, 2, 3, -2, 5]))
    print(minJumps([1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9])) # 3, time O(N), space O(1) min jumps needed for the farthest point
    print(mergeIntervals([[1, 3], [2, 4], [6, 8], [9, 10]])) # time O(nlogn), space O(N) merging intersecting intervals in list
    print(findPlatform([900, 940, 950, 1100, 1500, 1800],[910, 1200, 1120, 1130, 1900, 2000])) # 3, time O(nlogn), space O(1), finding departure needed maximal count of arrivals
    print(maximum_profit(3, [[1, 2, 4],[1, 5, 7],[2, 4, 4]]),"\n") # time O(nlogn), space O(N), 8, finding maximum profit by bisection in sorted intervals [start_time, end_time, profit]
    print(missingIntervals([1, 5, 6, 7, 9], 1, 9)) # time O(N), space O(N) finding missing intervals index ranges in a sorted list on numbers from lowest to maximal number in list
    print(missingIntervals([3, 4, 5, 5], 3, 5),"\n")
    print(minRemoval([[1, 2], [2, 3], [3, 4], [1, 3]])) # time O(nlogn), space O(1) finding minRemoval intervals which not intersect in list
    print(minRemoval([[1, 3], [1, 3], [1, 3]]),"\n")
    print(firstNonRepeating("aabc")) # time O(N), space O(1) finding first non repeating char in word
    print(longestSubarray([10, 5, 2, 7, 1, -10], 15)) # time O(N), space O(N) finding the subarray max counts to equal n number 
    print(longestSubarray([-5, 8, -14, 2, 4, 12], -5))
    print(maxLen([15, -2, 2, -8, 1, 7, 10, 23])) # time O(N), space O(N) finding maxLen sum, len of index which have max sum in list
    print(maxLen([-72, 68, -88, -7, 80, -80, 99, 21]))
    print(max_of_subarrays([1, 2, 3, 1, 4, 5, 2, 3, 6],3)) # time O(N), space O(K) finding maximal index value of subarrays in window k
    queries = [["PUT", 1, 2], ["PUT", 2, 3], ["PUT", 1, 5], ["PUT", 4, 5], ["PUT", 6, 7], ["GET", 4], ["PUT", 1, 2], ["GET", 3]]
    lru_ = LRUCache(2) #creating nodes, time O(1), space O(1) 
    for query in queries:
        if query[0] == "PUT": lru_.put(query[1], query[2])
        elif query[0] == "GET": lru_.get(query[1])
    print(lru_.get(4)); print(lru_.get(3))
    print(remAnagram("bcadeh", "hea")) # time O(N+M), space O(1) find b, c, d 3 letters that are not in s1, deletions needed to be the anagram
    print(nonRepeatingChar("geeksforgeeks")) # time O(N), space O(1) find first non repeating char in word
    print(reverseWords("i.like.this.program.very.much")) # time O(N), space O(N) reverse words divided by dot
    print(reverseString("heap")) # time O(N), space O(N)
    print(isPalindrome("saas")) # time O(N), space O(1) have same reversed characters sequence
    print(factorial(5)) # time O(N), space O(d) find multiples of factorial
    print(nextGreaterElement([1, 3, 2, 4])) # time O(N), space O(N), find next greater element index in stack, which is higher than the last element index value added to the list
    print(nextGreaterElement([6, 8, 0, 1, 3]))
    print(nextGreaterElementCircular([1, 3, 2, 4])) # time O(N), space O(N) we will iterate circulary numbers and their indexes in list finding their next greater element
    print(nextGreaterElementCircular([6, 8, 0, 1, 3]), "\n")
    print(getMaxArea([3, 5, 1, 7, 5, 9])) # time O(N), space O(N) finding max area between histogram bars
    print(getMaxArea([60, 20, 50, 40, 10, 50, 60]))
    print(trappingWater([3, 0, 1, 0, 4, 0, 2])) # time O(N), space O(1) trapping water between indexes
    print(trappingWater([3, 0, 2, 0, 4]))
    print(calculateSpan([100, 80, 90, 120])) # time O(N), space O(N) count the span distance between current index and nearest greater index
    print(getMedian([5, 15, 1, 3, 2, 8])) # time O(nlogn), space O(N) find median with max heap and min heap
    print(kthLargest(4, [1, 2, 3, 4, 5, 6])) # time O(nlogk), space O(k) find kth largest element in heap, add maximal value from left heap
    print(kthLargest(2, [3, 2, 1, 3, 3]),"\n")
    print(firstNegativeInWindow([-8, 2, 3, -6, 10], 2)) # time O(N), space O(k) finding negative number in current k window
    q = myStack() # deque stack with pushing, poping elements
    for query in [[1, 5], [1, 3], [1, 4], [3], [2], [4]]:
        if query[0] == 1: q.push(query[1]) # time O(N), space O(N)
        if query[0] == 2: q.pop() #time O(1), space O(1)
        if query[0] == 3: print(q.top()) #time O(1), space O(1)
        if query[0] == 4: print(q.size()) #time O(1), space O(1)
    print(mergeKArrays([[1, 3, 5, 7], [2, 4, 6, 8], [0, 9, 10, 11]])) # time O(nmlogn), space O(N) merging arrays with length of k
    print(countSetBits(6)) # time O(nlogn), space O(1) count number of bits in the actual number
    print(findUnique([1, 2, 1, 5, 5])) # time O(N), space O(1) find unique number in list by unique ^= num for num in list
    print(isPowerOfTwo(8)) # time O(1), space O(1) realize by xor if number is power of 2 if (n & (n - 1)) == 0
    print(isPowerOfTwo(6),"\n")
    print(bitMultiply(3),"\n") # time O(logn), space O(1) finding count of bits in number n where n = n & (n - 1), multiplied by n: 6
    print(aggressiveCows([1, 2, 4, 8, 9], 3)) # time O(nlogn+nlogd), space O(1) aggresive cows if I can place them of k in mid distance of list
    print(aggressiveCows([10, 1, 2, 7, 5], 3))
    print(findMinimum([9, 7, 5, 2, 3, 6, 10])) # time O(logn), space O(1) find minimum in array by ternary search
    print(findPages([12, 34, 67, 90], 2)) # find minimum count of sum of pages for 2 people
    print(findPages([15, 17, 20], 5))
    print(groupAnagrams(["act", "god", "cat", "dog", "tac"])) # time O(nwlogw), space O(nw) grouping anagrams in list
    print(groupAnagrams(["no", "on", "is"]))
    print(groupAnagrams(["listen", "silent", "enlist", "abc", "cab", "bac", "rat", "tar", "art"]))
    print(minWindow("timetopractice", "toc")) # time O(s+p), space O(s+p) find minimum subarray window in string which contains all words from second string
    print(startStation([4, 5, 7, 4], [6, 6, 3, 5])) # time O(N), space O(1) circular tank with cost for gas
    print(countSubarrays([10, 2, -2, -20, 10], -10)) # time O(N), space O(N) find count of subarray with the N sum
    queries = [[1, "abcd"], [1, "abc"], [1, "bcd"], [2, "bc"], [3, "bc"], [2, "abc"]]
    search_tree = Trie() # space O(1) 
    for query in queries:
        print(f"Operation: {query}")
        if query[0] == 1: print(search_tree.insert(query[1])) # time O(L), space O(L)
        if query[0] == 2: print(search_tree.search(query[1])) # time O(L), space O(1)
        if query[0] == 3: print(search_tree.isPrefix(query[1])) # time O(L), space O(1)
    print({object_: [object_ for object_ in search_tree.root.children[object_].children if object_] for object_ in search_tree.root.children})
    print_trie(search_tree.root)
    N = 10
    print(minNumber([2,3,4,5,6,7,8,9,10,1], 0, N - 1),"\n") # find the minimum number in  the array of len N
    root = TreeNode(1) # space O(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(5)
    print_tree(root)
    codec = Codec()
    serialized_data = codec.serialize(root) #time O(N), space O(N)
    print(f"\n--- Serialized String (Text Data) ---\n{serialized_data}")
    reconstructed_root = codec.deserialize(serialized_data) #time O(N), space O(N)
    print("\n--- Reconstructed Tree Structure ---")
    print_tree(reconstructed_root)
    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}")
    print(subarraySum([1, 2, 3, 7, 5], 12))