my_list = [1, 2, 3]
my_list.append(4) # add one element at the end of list
print(my_list)  # Output: [1, 2, 3, 4] 
my_list.extend([5, 6])
# Or: my_list += [5, 6] # concatinate with another list
print(my_list)  # Output: [1, 2, 3, 4, 5, 6]
my_list.insert(0, 10) # insert value at a specific index
print(my_list)  # Output: [10, 1, 2, 3, 4, 5, 6]
my_list.remove(3) # remove first occurance of value
print(my_list)  # Output: [10, 1, 2, 4, 5, 6]
my_list.pop(2) # remove value at specific index, default removal of last value
print(my_list)  # Output: [10, 1, 4, 5, 6]
del my_list[1:3] # remove slice
print(my_list)  # Output: [1, 6]
my_list.clear()
print(my_list)  # Output: []

visit = set()
visit.add((r, c)) # add tuple to set, cant add list they are immutable
visit.remove((r, c))

Collection to be sorted: {(6, 3), (5, 5), (6, 1), (1, 3)}
Stable Sorted: {(1, 3), (5, 5), (6, 3), (6, 1)}
Regular Sorted: Either {(1, 3), (5, 5), (6, 3), (6, 1)}, or {(1, 3), (5, 5), (6, 1), (6, 3)}

from collections import defaultdict

freq = defaultdict(int) # defaultdict(lambda: 1) for default 1 frequency instead of 0
nums = [1, 2, 2, 3, 3, 3]

for i, num in enumarate(nums):
    freq[num] += 1  # No need for if-else check of key
print(dict(freq)) # {1: 1, 2: 2, 3: 3}

from collections import Counter

nums = [5, 1, 2, 2, 3, 3, 3, 4]
freq = Counter(nums)
print(dict(freq))   # Output: {5: 1, 1: 1, 2: 2, 3: 3, 4: 1}
# Sort by key (ascending)
print(sorted(freq.items()))  # [(1, 1), (2, 2), (3, 3), (4, 1), (5, 1)]

# Sort ONLY by frequency (ascending)
print(sorted(freq.items(), key=lambda x: x[1]))
# Output: [(5, 1), (1, 1), (4, 1), (2, 2), (3, 3)]

# Sort ONLY by frequency (descending)
print(sorted(freq.items(), key=lambda x: -x[1]))
# Output: [(3, 3), (2, 2), (5, 1), (1, 1), (4, 1)]

# Sort by frequency (descending), then by key (ascending)
print(sorted(freq.items(), key=lambda x: (-x[1], x[0])))

diff = ["aaa", "aa", "a"]
freq2 = Counter(diff)
print(dict(freq2))  # Output: {'aaa': 1, 'aa': 1, 'a': 1}

nums = [1, 2, 3, 4, 5]
nums = [x for x in nums if x % 2 == 0]  # Removes odd numbers
squares = [x * x for x in nums]

nums = [10, 20, 30]
for i, num in enumerate(nums):
    print(i, num)  # 0 10, 1 20, 2 30

names = ["Alice", "Bob", "Charlie"]
ages = [25, 30, 22]
for name, age in zip(names, ages):
    print(name, age)

arr = [1, 3, 5, 7, 9]
windows = list(zip(arr, arr[1:], arr[2:]))  
print(windows)  # [(1, 3, 5), (3, 5, 7), (5, 7, 9)]

import math

print(math.ceil(4.7))    # Output: 5
print(math.ceil(-10.7))  # Output: -10

print(math.floor(2.3))   # Output: 2
print(math.floor(-33.89))# Output: -34

words = ["hello", "world"]
sentence = " ".join(words)  # Efficient
sentence = words[0] + " " + words[1]  # Slow in loops

"""
Only for ascending order
"""
import bisect

arr = [1, 3, 5, 7, 9]
# Returns First Element >= 5 -> if target = 5 is there then Binary Search, if not then it returns the position where the target would be inserted.
target = bisect.bisect_left(arr, 5)  # 2
lower_bound_index = bisect.bisect_left(arr, 6)  # 3
# Returns First Element > 7
upper_bound_index = bisect.bisect_right(arr, 7)  # 4

from itertools import combinations, permutations

arr = [1, 2, 3]
print(list(combinations(arr, 2)))  # [(1,2), (1,3), (2,3)]
print(list(permutations(arr, 2)))  # [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]

from collections import deque
stack = []

# Push O(1)
stack.append(10)
stack.append(20)
# Pop O(1)
stack.pop()     # 20
stack.pop()     # 10

queue = deque()
# Enqueue elements
queue.append(1)
queue.append(2)

# Dequeue elements (removes from front)
front = queue.popleft() # O(1)

# O(1) time complexity for both append (to the right) and popleft (from the left)

"""
Min-heap has smallest element on top - use it for finding k largest, Max-heap has largest element on top - used to find k smallest.
Poping from heap of size k is log(k).

The k-th largest element is the smallest element among the top k largest elements. This means we only need to maintain k elements in our Min-Heap to efficiently determine the k-th largest element. Whenever the size of the Min-Heap exceeds k, we remove the smallest element by popping from the heap. 

heapify() - Used when you have an existing unsorted list and want to convert it into a heap all at once. Runs in O(n) time. You only call this once, then you can use heappop or heappush.

heappush() - Used to insert one element into an already valid heap. Maintains heap property by reordering as needed. Runs in O(log n) time per push. If you build a heap by pushing elements one after another, no need to call heapify().
"""
import heapq

nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)  # Convert to heap
print(heapq.heappop(nums))  # Removes smallest element (1)
# Convert to a max-heap in-place
nums = [-num for num in nums]  # Negate all values
heapq.heapify(nums)  # Convert to min-heap (which acts as max-heap)

# Example list of pairs
nums = [[1, 2], [7, 3], [4, 1], [2, 5]]
k = 2

# Create an empty list to use as a heap
heap = []

# Push all elements into the heap with their sum as the priority
for pair in nums:
    # tuple: (priority, actual_value)
    heapq.heappush(heap, (pair[0] + pair[1], pair))

# Pop the smallest k elements from the heap
result = []
for _ in range(min(k, len(heap))):
    sum_val, pair = heapq.heappop(heap)
    result.append(pair)

print(result)  # [[1, 2], [4, 1]]  → smallest sums

import heapq
"""
Time complexity: O(klog⁡n)
Space complexity: O(k)
Heapify in O(n) and we pop k times O(logn)

For a list of lists or tuples, it uses the first element of each sub-list/tuple unless specified otherwise. 
"""
# O(n + k log n)
def kth_largest_heap(arr, k):
    # returns a list of the k largest, sorted largest to smallest
    ans = heapq.nlargest(k, arr)
    return ans[-1] # the last element is kth largest

# O(n + k log n)
def kth_smallest_heap(arr, k):
    # returns a list of the k largest, sorted smallest to largest
    ans = heapq.nsmallest(k, arr)
    return ans[-1]  

data = [(2, "B"), (1, "C"), (3, "A")]
# Get 2 "smallest" by first value
out = heapq.nsmallest(2, data, key=lambda x: x[0])  # [(1, 'C'), (2, 'B')]
# Get 2 "largest" by the string, alphabetically
out2 = heapq.nlargest(2, data, key=lambda x: x[1])  # [(3, 'A'), (2, 'B')]

    first_largest = float('-inf')
    second_largest = float('-inf')
    third_largest = float('-inf')

    for num in nums:
"""
If num is greater than first_largest: This means we've found a new largest number. We update third_largest to the previous second_largest, second_largest to the previous first_largest, and first_largest to the current num.
"""
        if num > first_largest:
            third_largest = second_largest
            second_largest = first_largest
            first_largest = num
"""
Else if num is greater than second_largest: This means num is the new second largest (but not the largest). We update third_largest to the previous second_largest and second_largest to num.
"""
        elif num > second_largest:
            third_largest = second_largest
            second_largest = num
"""
Else if num is greater than third_largest: This means num is the new third largest (but not larger than the first or second). We update third_largest to num.
"""
        elif num > third_largest:
            third_largest = num

from collections import deque

queue = deque([1, 2, 3, 4, 5])
queue.popleft()  # Removes 1 in O(1), NO shifting required!

s = "abracadabra"
freq = [0] * 26
for ch in s:
    freq[ord(ch) - ord('a')] += 1

def factorial(n, memo=None):
    # Use memo dictionary to store previously computed factorials
    if memo is None:
        memo = {}

    # Base case
    if n == 0 or n == 1:
        return 1

    # Check memo
    if n in memo:
        return memo[n]

    # Recursive computation with memoization
    memo[n] = n * factorial(n - 1, memo)
    return memo[n]

def is_odd(x):
    return (x & 1) == 1  # Odd if last bit is 1

def is_even(x):
    return (x & 1) == 0  # Even if last bit is 0

nums = [1, 2, 2, 3, 3]
unique = 0

for num in nums:
    unique ^= num  # XOR accumulates and cancels out duplicates

print(unique)  # Output: 1

def rotate(arr, k):
    k %= len(arr)  # Handle cases where k > len(arr)
    return arr[-k:] + arr[:-k]  # Move last k elements to the front
    return arr[k:] + arr[:k]  # Move first k elements to the back

def reverse_after_m(arr, m):
    arr[m+1:] = arr[m+1:][::-1]  # Reverse portion after m
    return arr

"""
prefix[i] stores the sum of all elements from index 0 to i-1.
prefix = 0 represents the sum before any elements.
This lets you get the sum of any subarray arr[l:r] using:
sum(l,r) = prefix[r+1] − prefix[l]
This reduces querying subarray sums from O(n) to O(1) in time, using O(n) in space for prefix sum array
"""
def prefix_sum(self, arr):
    n = len(arr)
    prefix = [0] * (n + 1) # prefix sum array has added element as sum of all numbers at last
    for i in range(n): # iterate till n - 1
       prefix[i+1] = prefix[i] + arr[i]
    return prefix

# iterating across all l and r is O(n^2)
def range_sum(self, prefix, l, r):
    return prefix[r+1] - prefix[l]

# instead find target - l from map of prefix sums
count = 0
prefix = self.prefix_sum(nums)

prefix_counts = defaultdict(int) 
prefix_counts[0] = 1  # sum = 0 before starting {0 : 1}

for i in range(1, len(prefix)):
    curr_sum = prefix[i]
    needed = curr_sum - sum(l, r)
    count += prefix_counts.get(needed, 0)
    prefix_counts[curr_sum] += 1

return count

def apply_range_updates(array_length, updates):
    """
O(1) per update
    """

    # Step 1: Create a difference array of size (n + 1) initialized to 0
    diff_array = [0] * (array_length + 1)

    # Step 2: Apply each update in O(1) using the diff array
    for start, end, increment in updates:
        diff_array[start] += increment
        if end + 1 < array_length:
            diff_array[end + 1] -= increment

    # Step 3: Convert the diff array to the final result using prefix sum
    final_array = [0] * array_length
    final_array[0] = diff_array[0]

    for i in range(1, array_length):
        final_array[i] = final_array[i - 1] + diff_array[i]

    return final_array

def is_isomorphic_single_direction(s: str, t: str) -> bool:
    """
    Checks if string s can be transformed into string t following the
    isomorphic string rules (one-to-many mapping, preserving order).
    """
    if len(s) != len(t):
        return False

    s_to_t_map = {}
    t_to_s_map = {}

    for i in range(len(s)):
        char_s = s[i]
        char_t = t[i]

        # Check mapping from s to t
        if char_s in s_to_t_map:
            if s_to_t_map[char_s] != char_t:
                return False
        else:
            if char_t in t_to_s_map:
                return False  # t_char is already mapped to another s_char
            s_to_t_map[char_s] = char_t
            t_to_s_map[char_t] = char_s

    return True

def is_isomorphic(s: str, t: str) -> bool:
    """
    Determines if two strings s and t are isomorphic by checking the
    isomorphism in both directions.
    """
    return is_isomorphic_single_direction(s, t) and is_isomorphic_single_direction(t, s)

def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums) # no need to worry about duplicates in between, we are hopping 
        longest = 0

        for num in numSet: # O(1)
            if (num - 1) not in numSet:
                length = 1
                while (num + length) in numSet: # consecutives are in set
                    length += 1
                longest = max(length, longest)
        return longest

def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        
        # Find the pivot: first index where nums[i] < nums[i+1]
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        # If pivot found (i >= 0), find successor to swap
        if i >= 0:
            j = n - 1
            # Find smallest element greater than nums[i] from the end
            while j > i and nums[j] <= nums[i]:
                j -= 1
            # Swap pivot with successor
            nums[i], nums[j] = nums[j], nums[i]
        
        # Reverse the suffix starting from i+1 to end
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

"""
In case of having integers this solution is valid, but incase of whole numbers we can further optimize by using greedy + two pointers exploiting the monotonicity. When all elements are positive, increasing the end pointer (right) of a window will always increase the sum, and moving the start pointer (left) forward will always decrease the sum. With negative numbers or zeros, increasing the window size can decrease or not change the sum, so the sliding window property breaks. 
In both cases, time complexity is O(n)
"""
def longest_subarray_sum_k(arr, k):
    # Dictionary to store the earliest index of each prefix sum
    prefix_sum_indices = {0: -1}
    prefix_sum = 0
    max_length = 0      # Length of the longest subarray with sum = k
    count = 0           # Number of longest subarrays with sum = k

    for i, num in enumerate(arr):
        prefix_sum += num
        # Check if there is a prefix sum that, when subtracted, gives sum = k
        if prefix_sum - k in prefix_sum_indices:
            length = i - prefix_sum_indices[prefix_sum - k]
            # If found a longer subarray, update max_length and reset count
            if length > max_length:
                max_length = length
                count = 1
            # If found another subarray of same max_length, increment count
            elif length == max_length:
                count += 1
        # Only store the earliest index for each prefix sum to maximize subarray length
        if prefix_sum not in prefix_sum_indices:
            prefix_sum_indices[prefix_sum] = i

    return max_length, count

def kadane(arr):
        """Maximum subarray sum"""
        max_current = max_global = arr[0]
        for i in range(1, len(arr)):
            max_current = max(arr[i], max_current + arr[i])
            max_global = max(max_global, max_current)
        return max_global

def max_sliding_window(nums: list[int], k: int) -> list[int]:
        """Maximum in sliding window using deque"""
        if not nums:
            return []
        
        result = []
        window = deque()
        
        for i in range(len(nums)):
            while window and window[0] < i - k + 1:
                window.popleft()
            
            while window and nums[window[-1]] < nums[i]:
                window.pop()
            
            window.append(i)
            if i >= k - 1:
                result.append(nums[window[0]])
        
        return result

"""
O(n) Space and Time
Bucket sort is an algorithm which involves grouping numbers based on their frequency. Use the bucket sort algorithm to create n buckets, grouping numbers based on their frequencies from 1 to n. Then, pick the top k numbers from the buckets, starting from n down to 1.

Heap solution is better than sorting as it will O(klogn) compared to O(nlogn) but have O(n+k) space compared to O(n).
"""
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = freq = [[] for i in range(len(nums) + 1)] # finite upto lenght of array

        for num in nums:
            count[num] = 1 + count.get(num, 0)
        for num, cnt in count.items():
            # count is index for array of nums there!
            freq[cnt].append(num)

        res = []
        for i in range(len(freq) - 1, 0, -1): # reverse traversal for top k
            for num in freq[i]:
                res.append(num)
                if len(res) == k:
                    return res

"""
There are two valid alternating patterns for any string of length n:
    Starting with '0': e.g. "010101..."
    Starting with '1': e.g. "101010..."
"""
def minOperations(self, s: str) -> int:
        flips_start_with_0 = 0
        flips_start_with_1 = 0

        for i, ch in enumerate(s):
            expected_0 = '0' if i % 2 == 0 else '1'
            expected_1 = '1' if i % 2 == 0 else '0'
            
            if ch != expected_0:
                flips_start_with_0 += 1
            if ch != expected_1:
                flips_start_with_1 += 1

        return min(flips_start_with_0, flips_start_with_1)

"""
Time: O(n) — each character is visited at most twice
Space: O(min(n, m)) — where m is the alphabet size (26 when only lowercase)
"""
def lengthOfLongestSubstring(self, s: str) -> int:
        char_index_map = {}  # stores character → last seen index
        start = 0  # start index of current window
        max_length = 0  # result

        for end, char in enumerate(s):
            # If the character is already seen and is in the current window
            if char in char_index_map and char_index_map[char] >= start:
                start = char_index_map[char] + 1  # shrink window from left

            char_index_map[char] = end  # update last seen index
            max_length = max(max_length, end - start + 1)

        return max_length

"""
O(n+m) Time and O(1) space
If given that the input consists only of lowercase English letters then frequency counting tuple is most optimal. Otherwise just simply append tuple in hashmap.
"""

from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        if m > n:
            return []

        res = []
        # a-z has 26 characters
        pCount = [0] * 26
        sCount = [0] * 26

        # Build frequency counts for the first window and target
        for i in range(m):
            pCount[ord(p[i]) - ord('a')] += 1
            sCount[ord(s[i]) - ord('a')] += 1

        # Track how many characters match in frequency
        matches = sum(pCount[i] == sCount[i] for i in range(26))

        # Initial match
        if matches == 26:
            res.append(0)

        for i in range(m, n):
            left = ord(s[i - m]) - ord('a')
            right = ord(s[i]) - ord('a')

            # Remove the outgoing character
            if sCount[left] == pCount[left]:
                matches -= 1
            sCount[left] -= 1
            if sCount[left] == pCount[left]:
                matches += 1

            # Add the new character
            if sCount[right] == pCount[right]:
                matches -= 1
            sCount[right] += 1
            if sCount[right] == pCount[right]:
                matches += 1

            if matches == 26:
                res.append(i - m + 1)

        return res

      # Grouping the anagram 
      d = defaultdict(findAnagrams())
      for s in strs:  # O(N)
        d[tuple(sorted(s))].append(s)
        return d.values()

"""
Score = zero_in_left + (total_ones - ones_in_left)
Time - O(N) in one pass through array
"""
def maxScore(self, s: str) -> int:
        # Initialize left and right counts
        left_zeros = 1 if s[0] == '0' else 0
        right_ones = s[1:].count('1')
        max_score = left_zeros + right_ones

        for i in range(1, len(s) - 1):
            if s[i] == '0':
                left_zeros += 1
            else:
                right_ones -= 1
            max_score = max(max_score, left_zeros + right_ones)

        return max_score

"""
O(n) Time and O(1) Space - in-place modification

"a" → just "a" (not "a1")
"a","a" → "a","2"
"a","b" → "a","b" (no numbers needed)
"""
from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        write = 0  # Where we write next
        left = 0   # Start of current group

        for right in range(len(chars) + 1):  # Extra step to flush last group
            # Check group break (or end of list)
            if right == len(chars) or chars[right] != chars[left]:
                count = right - left
                chars[write] = chars[left]
                write += 1

                if count > 1:
                    for digit in str(count):
                        chars[write] = digit
                        write += 1

                left = right  # Move to start of next group

        return write

"""
Time Complexity - O(N)

Lots of edge cases :
All 9s → e.g., 999 → 1001
Mirroring creates a smaller number → e.g., 12932 → mirror → 12921 < 12932, so you must increment and mirror again
Odd vs Even Length
Middle Carry Propagation when incrementing e.g., 1991 → mirror = 1991 < 1991, so increment → 20 → 2002
"""
def next_palindrome(num: str) -> str:
    n = len(num)
    half = (n) // 2
    is_odd = (n % 2 != 0)

    # Split into left, middle (if odd), right
    left = num[:half]
    middle = num[half] if is_odd else ''
    right = num[half+1:] if is_odd else num[half:]

    # Mirror left + middle to create a palindrome
    if is_odd:
        candidate = left + middle + left[::-1]
    else:
        candidate = left + left[::-1]

    if candidate > num:
        return candidate

    # If not, we need to increment (left + middle)
    if is_odd:
        incremented = str(int(left + middle) + 1)
        new_left = incremented[:-1]
        new_middle = incremented[-1]
        return new_left + new_middle + new_left[::-1]
    else:
        incremented = str(int(left) + 1)
        return incremented + incremented[::-1]

"""
We want to decide a split point in the string such that:
All characters to the left are 0
All characters to the right are 1
We try every split point i (between characters):
Count number of 1s before i (that need to be flipped to 0)
Count number of 0s after i (that need to be flipped to 1)
The total flips = ones_before + zeros_after

Time Complexity: O(n)
Space Complexity: O(n) (due to the prefix array)
"""
"""
|00110 → 0 flips left, flip 3 zeros to 1 → 3
0|0110 → 0 1s left, 2 zeros right → 2
00|110 → 0 1s left, 1 zero right → 1
001|10 → 1 1s left, 1 zero right → 2
0011|0 → 1 1s left, 1 zero right → 2
00110| → 2 1s left, 0 zero right → 2
"""
def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)

        # Compute prefix sum of 1s
        ones_prefix = [0] * (n + 1)
        for i in range(n):
            ones_prefix[i + 1] = ones_prefix[i] + (1 if s[i] == '1' else 0)

        min_flips = float('inf')

        for i in range(n + 1):
            # Left: 0..i-1 → should be 0 → flip all 1s in that region
            ones_left = ones_prefix[i]

            # Right: i..n-1 → should be 1 → flip all 0s in that region
            zeros_right = (n - i) - (ones_prefix[n] - ones_prefix[i])

            min_flips = min(min_flips, ones_left + zeros_right)

        return min_flips

"""
O(N) Time 
"""
def length_of_linked_list(head: Optional[ListNode]):
"""
Although nodes is just a Python list, each element in nodes is still a reference to a node in the original linked list.
"""
    nodes = []
    current = head
    while current is not None:
        nodes.append(current)
        current = current.next
    return len(nodes)

    # if we want to remove from back in bruteforce way
    removeIndex = len(nodes) - n
        if removeIndex == 0:
            return head.next
    # directly operate on nodes array as its reference to LL
    nodes[removeIndex - 1].next = nodes[removeIndex].next
    return head

"""
Time - O(n) and Space - O(1)
"""
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head

        dummy = ListNode(0, head)
        prev, head = dummy, dummy.next
         
        # Move `prev` to node before `left`
        for _ in range(left - 1):
            prev = prev.next

        # `start` is the first node to reverse
        start = prev.next
        then = start.next

        # Reverse the sublist using head-insertion
        for _ in range(right - left):
            start.next = then.next
            then.next = prev.next
            prev.next = then
            then = start.next

        return dummy.next

def detect_and_remove_cycle(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    # Step 1: Detect loop
    slow = fast = head
    has_cycle = False

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return head  # No loop detected

    # Step 2: Find the start of the loop
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    # slow (or fast) is now at the start of the loop

    # Step 3: Find the last node in the cycle and break it
    ptr = slow
    while ptr.next != slow:
        ptr = ptr.next

    ptr.next = None  # Break the loop

    return head

def next_greater_element(nums):
    n = len(nums)
    res = [-1] * n  # Initialize result with -1 (no greater element)
    stack = []      # Will store indices in decreasing order of nums values

    for i in range(n):
        # Pop from stack while current element is greater than element at stack top
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]  # Found next greater element for idx
        stack.append(i)
    
    return res

def next_smaller_element(nums):
    n = len(nums)
    res = [-1] * n  # Initialize with -1 (no smaller element)
    stack = []      # Will store indices in increasing order of nums values

    for i in range(n):
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]  # Found next smaller element
        stack.append(i)
    
    return res

def previous_greater_element(nums):
    """
    For each element, find the nearest element to the LEFT that is GREATER.
    Returns a list where res[i] is the previous greater element of nums[i],
    or -1 if no such element exists.
    """
    n = len(nums)
    res = [-1] * n    # Initialize result array with -1 (means no previous greater)
    stack = []        # Stack to keep indices of elements, maintaining strictly decreasing order

    for i in range(n):
        # Pop elements from the stack while current element is >= element at stack top
        # because they cannot be previous greater for future elements
        while stack and nums[i] >= nums[stack[-1]]:
            stack.pop()
        
        # If stack is not empty, the top is the index of previous greater element
        res[i] = nums[stack[-1]] if stack else -1
        
        # Push current index to stack to possibly be previous greater for future elements
        stack.append(i)

    return res

def previous_smaller_element(nums):
    """
    For each element, find the nearest element to the LEFT that is SMALLER.
    Returns a list where res[i] is the previous smaller element of nums[i],
    or -1 if no such element exists.
    """
    n = len(nums)
    res = [-1] * n       # Initialize result array with -1 (means no previous smaller)
    stack = []           # Stack to keep indices of elements, maintaining strictly increasing order

    for i in range(n):
        # Pop elements from stack while current element is <= element at top of stack
        # because they cannot be previous smaller for future elements
        while stack and nums[i] <= nums[stack[-1]]:
            stack.pop()
        
        # If stack not empty, top of stack is index of previous smaller element
        res[i] = nums[stack[-1]] if stack else -1
        
        # Push current index for future elements to compare
        stack.append(i)

    return res

def is_valid_parentheses(s: str) -> bool:
    open_count = 0  # Tracks the net number of unmatched '('

    for char in s:
        if char == '(':
            open_count += 1
        elif char == ')':
            open_count -= 1
            # If at any point open_count is negative, a ')' is unmatched
            if open_count < 0:
                return False

    # At the end, all '(' must be matched by ')'
    return open_count == 0

def evaluate(expression: str) -> int:
    def calculate(tokens):
        stack = []
        num = 0
        sign = '+'  # Default sign is '+'

        while tokens:
            token = tokens.pop(0)  # Read one character at a time

            if token.isdigit():  # Build multi-digit number
                num = num * 10 + int(token)

            if token in "+-*/" or not tokens:  # End of number OR end of expression
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop() * num)
                elif sign == '/':
                    stack.append(int(stack.pop() / num))  # Python's `/` is float, so use `int()`

                sign = token  # Update the operator
                num = 0  # Reset the number

            elif token == '(':  # Solve sub-expression inside parentheses
                num = calculate(tokens)

            elif token == ')':  # Return computed result if closing parenthesis is found
                break

        return sum(stack)  # Sum all elements left in the stack

    return calculate(list(expression.replace(" ", "")))  # Convert expression to list (char by char)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # Avoids overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found

def lower_bound(array, target):
    """
    Returns the smallest index l such that array[l] >= target and array[right] < target
    If all elements are < target, returns len(array).
    """
    left, right = 0, len(array) # allows the solution to return len(arr) when the target is greater than all elements in the array (i.e., the insertion point is at the end) and 0 if less than all elements in array
    while left < right:
        mid = (left + right) // 2
        # If mid element is less than target, move left up
        if array[mid] < target:
            left = mid + 1
        else:
            # mid is a candidate, but keep searching left
            right = mid
    # Now, left == right is the first index where array[index] >= target
    # If all elements in the array are less than or equal to target, the search will finish with left == len(array).
    return left

def upper_bound(array, target):
    """
    Returns the smallest index r such that array[r] > target and array[left] <= target.
    If all elements are <= target, returns len(array).
    To get the index of the last element <= target, return upper_bound(array, target) - 1
    """
    left, right = 0, len(array)
    while left < right:
        mid = (left + right) // 2
        if array[mid] <= target:
            # mid is too small or just right, move left up
            left = mid + 1
        else:
            # mid is a candidate, move right down
            right = mid
    # left == right is the first index where array[index] > target
    # If all elements in the array are less than or equal to target, the search will finish with left == len(array).
    return left

def binary_search_answer(space):
    left, right = 0, len(space)
    while left < right:
        mid = (left + right) // 2
        if check(space[mid]):
            right = mid  # mid might be the first True, so keep it
        else:
            left = mid + 1  # mid is False, need larger
    return left  # index of first True (if any)

"""
Approach	Time Complexity	Space Complexity	Suitable For
Brute Force (Vertical Scanning)	O(N * M)	O(1)	Small Inputs
Binary Search	O(N log M)	O(1)	Medium Inputs
Divide & Conquer	O(N * M)	O(log N)	Recursion-friendly cases
Trie (Prefix Tree)	O(N * M)	O(N * M)	Large Inputs
"""
def is_common_prefix(strs, length):
    prefix = strs[0][:length]
    return all(s.startswith(prefix) for s in strs)

def longest_common_prefix(strs):
    if not strs:
        return ""

    left, right = 0, min(map(len, strs))
    while left < right:
        mid = (left + right + 1) // 2
        if is_common_prefix(strs, mid):
            left = mid  # Move right (increase prefix size)
        else:
            right = mid - 1  # Move left (decrease prefix size)

    return strs[0][:left]

def searchInRotatedArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1

        while left < right: # if they are equal, we will be stuck in a loop
            mid = (left + right) // 2
            # as both parts are sorted individually, the minimum value will occur when arr[left] > arr[right]
            if arr[mid] < arr[right]:
                # we are in the increasing part → move right
                left = mid + 1
            else: # when mid value is smaller than right
                # we are in the decreasing part → move left
                right = mid

        return right  # or left; both point to the peak, left is maximum and right is minimum

"""
Prefix + Binary Search is O(nlogn). This is best we can do incase of +ve, -ve, 0 in array. Prefix sums allow you to compute the sum of any subarray efficiently. Convert the problem of minimal subarray length with sum ≥ target into finding the smallest j such that prefixSum[j] - prefixSum[i] >= target for each i.
"""
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        prefix_sums = [0] * (n + 1)

        # Compute prefix sums
        for i in range(n):
            prefix_sums[i + 1] = prefix_sums[i] + nums[i]

        min_length = n + 1 # this length cannot be the answer, so min() with it from any subarray will be fine
        
        for start in range(n):
            left, right = start, n
            # Binary search to find smallest end index where subarray sum >= target (lower bound)
            while left < right:
                mid = (left + right) // 2
                current_sum = prefix_sums[mid + 1] - prefix_sums[start]
                if current_sum >= target:
                    right = mid
                else:
                    left = mid + 1
            if left != n:
                min_length = min(min_length, left - start + 1)

        # If no valid subarray found, return 0
        return 0 if min_length == n + 1 else min_length
"""
Sliding Window is exploiting the fact that we have positive integers only in the array. The sliding window technique relies on the property that adding more elements to the window does not decrease the sum (because all are positive). So, if the subarray sum >= k is found, the right pointer can be increase till end of array. But we need minimum, so no need for that! Instead we move the left pointer to find another subarray. We want to shrink the window as soon as we see a valid subarray.
"""
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left, sum = 0, 0
        count = float("inf")
"""
Just because we are using 2 loops dosent make it O(n^2).
The outer for right in range(len(nums)) loop runs n times. The inner while sum >= target: loop moves the left pointer forward. Critically, left pointer only moves forward throughout the entire algorithm (never back). Both left and right pointers together move at most 2n steps (right goes from 0 to n-1; left only moves forward). Each element is visited at most twice: once when right includes it and once when left excludes it.
"""
        for right in range(len(nums)):
            sum += nums[right]
            while sum >= target:
                count = min(right - left + 1, count)
                sum -= nums[left]
                left += 1

        return 0 if count == float("inf") else count

def minEatingSpeed(self, piles: list[int], h: int) -> int:
        """
        Finds the minimum eating speed (k) such that Koko can eat all bananas
        within h hours.

        Args:
            piles: A list of integers representing the number of bananas in each pile.
            h: The maximum number of hours Koko has to eat all bananas.

        Returns:
            The minimum integer k (eating speed).
        """

        # The search space for 'k'
        # The minimum possible speed is 1 (Koko must eat at least 1 banana per hour).
        # The maximum possible speed is the largest pile size. If Koko eats at this speed,
        # she'll finish each pile in 1 hour, which is the fastest possible.
        low = 1
        high = max(piles)
        
        # This will store the minimum valid 'k' found so far.
        # Initialize with 'high' because we know 'high' is always a valid speed,
        # but we want to find the minimum.
        min_k = high 

        # Binary search for the minimum k
        while low <= high:
            mid = (low + high) // 2  # Calculate the middle speed

            # Calculate the total time taken to eat all bananas at 'mid' speed
            total_time = 0
            for pile in piles:
                # For each pile, the time taken is ceil(pile / mid).
                # math.ceil(a / b) calculates the smallest integer greater than or equal to a/b.
                # This correctly accounts for cases where pile < mid (eats all in 1 hour)
                # or pile is a multiple of mid (exact division) or not (needs an extra hour).
                total_time += math.ceil(pile / mid)
            
            # Check if Koko can eat all bananas within 'h' hours at 'mid' speed
            if total_time <= h:
                # If she can, 'mid' is a possible answer.
                # We try to find an even smaller 'k' by searching in the lower half.
                min_k = mid
                high = mid - 1
            else:
                # If she cannot, 'mid' is too slow.
                # We need a faster speed, so search in the upper half.
                low = mid + 1
        
        return min_k

"""
Binary Search + Prefix Sum for range queries
"""
def maximumBeauty(self, items, queries):
        # Step 1: Sort items by price
        items.sort()
        
        # Step 2: Build prefix max array for beauty
        prices = []
        prefix_max_beauty = []
        max_beauty = 0
        
        for price, beauty in items:
            # Only keep the best beauty seen so far for each price
            max_beauty = max(max_beauty, beauty)
            if prices and prices[-1] == price:
                # skip duplicate prices, keep max
                prefix_max_beauty[-1] = max_beauty
            else:
                prices.append(price)
                prefix_max_beauty.append(max_beauty)

        # Step 3: Binary search for each query
        res = []
        for q in queries:
            # Find the rightmost item with price <= q
            idx = bisect_right(prices, q) - 1
            if idx >= 0:
                res.append(prefix_max_beauty[idx])
            else:
                res.append(0)
        return res

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
        n = mountainArr.length()

        # Step 1: Find peak index of the mountain array using binary search
        left, right = 1, n - 2  # peak cannot be first or last element
        while left <= right:
            mid = (left + right) // 2
            val_left = mountainArr.get(mid - 1)
            val_mid = mountainArr.get(mid)
            val_right = mountainArr.get(mid + 1)

            # If slope is ascending: move right to find peak
            if val_left < val_mid < val_right:
                left = mid + 1
            # If slope is descending: move left to find peak
            elif val_left > val_mid > val_right:
                right = mid - 1
            else:
                # Found peak point where array changes from increasing to decreasing
                break
        peak_index = mid

        # Step 2: Binary search on ascending part from start to peak
        left, right = 0, peak_index
        while left <= right:
            mid = (left + right) // 2
            val = mountainArr.get(mid)
            if val == target:
                return mid
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1

        # Step 3: Binary search on descending part from peak+1 to end
        left, right = peak_index + 1, n - 1
        while left <= right:
            mid = (left + right) // 2
            val = mountainArr.get(mid)
            if val == target:
                return mid
            elif val > target:
                left = mid + 1
            else:
                right = mid - 1

        # If target is not found in either part
        return -1

def lexicalOrder(n: int) -> List[int]:
    result = []

    def dfs(curr):
        if curr > n:
            return
        result.append(curr)
        for i in range(10):
            next_num = curr * 10 + i
            if next_num > n:
                break  # Prune this branch
            dfs(next_num)

    for i in range(1, 10):
        dfs(i)

    return result

def partition(s):
    """
    Returns all possible palindrome partitionings of string s.
    Each partition is a list of substrings, all of which are 
palindromes.
    At each recursion, you are not deciding for each character whether to include it or not. Instead, you are choosing every possible end index for a substring starting at the current position, and only recursing on those substrings that are palindromes. This is a multi-way branching at each step, not binary.
    Time and Space Complexity - O(n×2^n) as each partitioning operation is O(n), and there are 2^n−1 partitions
    """
    from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        substring = []
        self.backtrack(result, 0, substring, s)
        return result  # Return all palindrome partitions collected
    
    def backtrack(self, result: List[List[str]], start: int, substring: List[str], s: str) -> None:
        # If we reached the end, add a copy of current partition to the result
        if start == len(s):
            result.append(substring[:]) # add copy of substring
            return
        
        # Try all possible partitions starting at 'start'
        for end in range(start, len(s)):
            if self.isPalindrome(s, start, end):
                # Append current palindrome substring
                substring.append(s[start:end+1])
                # Recurse for the remaining substring
                self.backtrack(result, end + 1, substring, s)
                # Backtrack: remove last substring and try next
                substring.pop()
    
    def isPalindrome(self, s: str, left: int, right: int) -> bool:
        # Check palindrome between indices left and right inclusive
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

def exist(board, word):
    def dfs(i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
            return False
        
        temp = board[i][j]
        board[i][j] = '#'  # Mark as visited
        
        # Explore neighbors
        if (dfs(i + 1, j, k + 1) or (dfs(i - 1, j, k + 1)) or (dfs(i, j + 1, k + 1)) or (dfs(i, j - 1, k + 1)):
            return True
        
        board[i][j] = temp  # Backtrack
        return False
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(i, j, 0):
                return True
    return False

"""
Approach	Time	Space	Notes
Backtracking (DFS)	O(4^N)	O(N)	Efficient, recursive
Iterative (BFS with Queue)	O(4^N)	O(4^N)	Uses queue for level-wise expansion
"""
from typing import List

def letterCombinations(digits: str) -> List[str]:
    if not digits:
        return []

    phone_map = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }

    res = []

    def backtrack(index, path):
        if index == len(digits):
            res.append("".join(path))
            return

        for char in phone_map[digits[index]]:
            path.append(char)
            backtrack(index + 1, path)
            path.pop()  # Backtrack to previous state

    backtrack(0, [])
    return res

"""
We can generate all subsets such that, each element falls into one of k buckets - each has k options, such that their sum is same = sum(nums)/k. Such decision tree would be of height n, so O(k^n) - pretty bad!

Now we dont really need to put the elements in summation buckets, we can just recurse each element and if along the recursion the sum matches, store it until we have k such subsets stored. That would be O(k*2^n) as we will have k such decision trees! Also, we have to track what numbers we used to not use it again.

Interestingly, with right pruning, its 30ms solution!

Memoization is also possible, if we pass subsets as tuple.
"""
from typing import List

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total_sum = sum(nums)
        
        # If total sum is not divisible by k, partitioning into k equal subsets is impossible
        if total_sum % k != 0:
            return False
        
        target_sum = total_sum // k
        
        # This list keeps track of the current sum of each subset (not the elements themselves). Tracking sum only is sufficient here because we only need to know if subsets can achieve the target sum, not the exact elements in them.
        subsets_sums = [0] * k
        
        # Sorting in descending order helps pruning:
        # We try to place bigger numbers first, so if a big number doesn't fit early, 
        # we can backtrack faster.
        nums.sort(reverse=True)
        return backtrack(0)
        
        def backtrack(start: int) -> bool:
            # If all numbers have been placed successfully
            if start == len(nums):
                return True

            current_num = nums[start]

            # Try to put current_num into each of the k subsets
            for end in range(k):
                # If adding current_num doesn't exceed the target sum for this subset
                if subsets_sums[end] + current_num <= target_sum:
                    subsets_sums[end] += current_num  # Choose to add
                    
                    # Recursive call to place next number
                    if backtrack(start + 1):
                        return True  # Found a valid partition, no need to explore further
                    
                    subsets_sums[end] -= current_num  # Backtrack (undo the choice)
                    
                    # Optimization :
                    # If this subset was empty (sum zero) and adding current_num didn't lead to solution,
                    # then trying other empty subsets at this level will also fail.
                    if subsets_sums[end] == 0:
                        break

            # If no subset could accommodate current_num without violating target sum, fail
            return False

"""
In palindrome partitioning, we divide continuously in a linear manner. However, in this question, we can divide from any point, pick any element, and partition discontinuously.

As the bags chosen is not necessarily contiguous subarray of cookies, we can't use Greedy or Sliding window of size k.

Greedy algorithms make locally optimal choices at each step, hoping to reach a globally optimal solution. In distribution problems, a locally "fair" choice might lead to a globally unfair outcome later. Imagine cookies [10, 1, 1, 10] and 2 children. If we had to give continuous subarrays, a greedy approach might try to give the first child [10] (largest first). Then the second child gets [1, 1, 10] (unfairness 12). However, the optimal solution might be to give the first child [10, 1] (unfairness 11) and the second child [1, 10] (unfairness 11). The initial greedy choice prevented this better outcome.
"""
def distributeCookies(self, cookies: List[int], k: int) -> int:
        n = len(cookies)

        # Minimum possible unfairness is the largest single bag.
        # Maximum possible unfairness is the sum of all cookies.
        left = max(cookies)
        right = sum(cookies)
        ans = right

        def can_distribute(max_unfairness: int) -> bool:
            children_cookies = [0] * k

            def backtrack(cookie_index: int):
                if cookie_index == n:
                    return True

                for i in range(k):
                    if children_cookies[i] + cookies[cookie_index] <= max_unfairness:
                        children_cookies[i] += cookies[cookie_index]
                        if backtrack(cookie_index + 1):
                            children_cookies[i] -= cookies[cookie_index]  # Backtrack
                            return True
                        children_cookies[i] -= cookies[cookie_index]  # Backtrack
                return False

            return backtrack(0)

        while left <= right:
            mid = (left + right) // 2
            if can_distribute(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans

"""
Minimize the number of intervals thats needs to be removed to avoid overlaps or select the maximum number of non-overlapping intervals.
At every step, always pick the interval that finishes earliest among the available ones. By always picking the interval that ends earliest, you leave the most room for the remaining intervals, maximizing your chances of fitting more without overlap
"""
def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0

    # Sort intervals by end time
    intervals.sort(key=lambda x: x[1])
    count = 0
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start < prev_end: # If the current interval starts before the previous interval ends, they overlap.
            count += 1
        else: 
            # No overlap, update prev_end
            prev_end = end

    return count

import heapq
from collections import defaultdict, Counter

class HuffmanNode:
    def __init__(self, freq, char=None, left=None, right=None):
        self.freq = freq          # Frequency of the character(s)
        self.char = char          # Character stored (None for internal nodes)
        self.left = left          # Left child
        self.right = right        # Right child

    # For heapq to sort nodes by frequency
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(char_freq):
    """
    Build Huffman tree from character frequencies.
    Returns the root of the Huffman tree.
    """
    min_heap = []

    # Initialize the heap with leaf nodes for each character
    for char, freq in char_freq.items():
        heapq.heappush(min_heap, HuffmanNode(freq, char))
    
    # Combine nodes until single tree remains
    while len(min_heap) > 1:
        # Pop two nodes with smallest freq
        left = heapq.heappop(min_heap)
        right = heapq.heappop(min_heap)

        # Merge these nodes into a new internal node
        merged = HuffmanNode(left.freq + right.freq, None, left, right)
        heapq.heappush(min_heap, merged)
    
    # The remaining node is the root of the Huffman tree
    return min_heap[0] if min_heap else None

def build_huffman_codes(root):
    """
    Traverse the Huffman tree to build a dictionary of character->code mappings.
    """
    huffman_codes = {}

    def dfs(node, code):
        if node is None:
            return
        # If leaf node
        if node.char is not None:
            huffman_codes[node.char] = code if code else "0"  # handle single char edge case
            return
        # Traverse left adds "0", right adds "1"
        dfs(node.left, code + "0")
        dfs(node.right, code + "1")

    dfs(root, "")
    return huffman_codes

def huffman_encode(text):
    """
    Encode the input text using Huffman coding.
    Returns the encoded string and the Huffman tree root for decoding.
    """
    # Count frequency of each character
    char_freq = Counter(text)

    # Build Huffman tree
    root = build_huffman_tree(char_freq)

    # Build codes by traversing the tree
    codes = build_huffman_codes(root)

    # Encode the text using code map
    encoded_text = "".join(codes[ch] for ch in text)

    return encoded_text, root

def huffman_decode(encoded_text, root):
    """
    Decode the encoded text using the Huffman tree.
    Returns the original text string.
    """
    decoded_chars = []
    current = root
    for bit in encoded_text:
        # Traverse tree per bit
        if bit == "0":
            current = current.left
        else:
            current = current.right
        
        # On reaching leaf node, append character and restart from root
        if current.char is not None:
            decoded_chars.append(current.char)
            current = root
    
    return "".join(decoded_chars)

def fractional_knapsack(weights, values, capacity):
    """
    Args:
        weights: List of item weights.
        values: List of item values.
        capacity: Maximum capacity of the knapsack.
    
    Returns:
        max_value: Maximum value that can be carried in the knapsack.
    Time Complexity - O(nlogn)
    """

    # Step 1: Calculate value-to-weight ratio for each item
    n = len(weights)
    items = []
    for i in range(n):
        ratio = values[i] / weights[i]
        items.append((ratio, weights[i], values[i]))  # (ratio, weight, value)

    # Step 2: Sort items by ratio in descending order
    items.sort(reverse=True)

    # Step 3: Accumulate items in the knapsack
    max_value = 0.0
    for ratio, weight, value in items:
        if capacity >= weight:
            # If the whole item can be taken, take it all
            max_value += value
            capacity -= weight
        else:
            # Take the fraction that fits
            fraction = capacity / weight
            max_value += value * fraction
            break  # Knapsack is full

    return max_value

def level_order_traversal(root):
        """BFS for tree"""
        if not root:
            return []
        
        result = []
        # We enqueue child nodes at the back.
        # We dequeue nodes from the front to process them level by level.
        queue = deque([root]) # queue = [1]
        level_sum = 0 # when its never reset, it gives sum of all nodes in binary tree
        
        # each iteration of while loop is one level
        while queue:
            level = []
            level_sum = 0 # reset sum at each level, so last level sum is of deepest layer
            level_size = len(queue)
            
            # each iteration of for loop is for nodes at each level
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                level_sum += node.val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level)
        return result
    
    # Iteration 1 (Level 0):
    # - level_size = 1
    # - Process node 1:
    #     * Add 1 to current level
    #     * Add children (2,3) to queue
    # - After iteration: 
    #     * queue = [2,3]
    #     * result = [[1]]
    
    # Iteration 2 (Level 1):
    # - level_size = 2
    # - Process node 2:
    #     * Add 2 to current level
    #     * Add children (4,5) to queue
    # - Process node 3:
    #     * Add 3 to current level
    #     * Add child (6) to queue
    # - After iteration:
    #     * queue = [4,5,6]
    #     * result = [[1], [2,3]]
    
    # Iteration 3 (Level 2):
    # - level_size = 3
    # - Process nodes 4,5,6:
    #     * Add 4,5,6 to current level
    #     * No children to add
    # - After iteration:
    #     * queue = []
    #     * result = [[1], [2,3], [4,5,6]]
    
    # Final result: [[1], [2,3], [4,5,6]]
    
    # Time: O(n) - visit each node once
    # Space: O(w) - where w is max width of tree

# Left -> Root -> Right (Sorted for BST)
def inorder(node: TreeNode) -> List[int]:
            if not node:
                return []
            return inorder(node.left) + [node.val] + inorder(node.right)
        return inorder(root)

# Root -> Left -> Right
def preorder(node: TreeNode) -> List[int]:
            if not node:
                return []
            return [node.val] + preorder(node.left) + preorder(node.right)
        return preorder(root)

# 
def postorder(node: TreeNode) -> List[int]:
            if not node:
                return []
            return postorder(node.left) + postorder(node.right) + [node.val]
        return postorder(root)

class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        # If you use result = 0 (a local variable inside the method), each recursive call gets its own copy of result, and their changes are not reflected back to the caller or accumulated. With self.result, all recursive calls share the same variable attached to the Solution object. Any modification in any nested call is preserved and visible globally.

        self.result = 0 
        self.dfs(root)
        return self.result
        
    def dfs(self, node: TreeNode):
        if not node:
            return (0, 0)  # sum = 0, count = 0

        left_sum, left_count = self.dfs(node.left)
        right_sum, right_count = self.dfs(node.right)

        total_sum = node.val + left_sum + right_sum
        total_count = 1 + left_count + right_count

        average = total_sum // total_count
        if node.val == average:
            self.result += 1

        return (total_sum, total_count)

"""
O(n) Time and O(h) space
"""
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if not root:
            return None

        # First recurse into children
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)

        # Then check if current node is now a leaf
        if not root.left and not root.right and root.val == target:
            # in case of leaf node, it gets cut from the parent as removeLeafNodes will return None making root.left/right None. When the node has no reference, python's garbage collector will handle it
            return None 

        return root

def right_view(root: TreeNode) -> List[int]:
        """Right view of binary tree using level order"""
        if not root:
            return []
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            
            for i in range(level_size):
                node = queue.popleft()
                
                if i == level_size - 1:  # rightmost node of current level
                    result.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return result

def boundary_traversal(root: TreeNode) -> List[int]:
        """
        Boundary Traversal of Binary Tree
        
        Intuition:
        - Traverse tree boundary in anti-clockwise direction
        - Three parts: left boundary, leaves, right boundary
        - Need to avoid duplicate nodes
        
        Algorithm steps:
        1. Add root
        2. Add left boundary (excluding leaves)
        3. Add leaves from left to right
        4. Add right boundary (excluding leaves) in reverse
        
        Helper functions:
        - add_left_boundary: Adds nodes on leftmost path
        - add_leaves: Adds all leaf nodes
        - add_right_boundary: Adds nodes on rightmost path (bottom-up)
        
        Use cases:
        1. Printing tree perimeter
        2. Finding external nodes
        3. Tree visualization
        
        Time: O(n), Space: O(h) where h is height of tree
        """
        def add_left_boundary(node: TreeNode, result: List[int]):
            if not node or (not node.left and not node.right):
                return
            result.append(node.val)
            if node.left:
                add_left_boundary(node.left, result)
            elif node.right:
                add_left_boundary(node.right, result)
        
        def add_leaves(node: TreeNode, result: List[int]):
            if not node:
                return
            if not node.left and not node.right:
                result.append(node.val)
                return
            add_leaves(node.left, result)
            add_leaves(node.right, result)
        
        def add_right_boundary(node: TreeNode, result: List[int]):
            if not node or (not node.left and not node.right):
                return
            if node.right:
                add_right_boundary(node.right, result)
            elif node.left:
                add_right_boundary(node.left, result)
            result.append(node.val)
        
        if not root:
            return []
        
        result = [root.val]
        if not root.left and not root.right:
            return result
        
        if root.left:
            add_left_boundary(root.left, result)
        add_leaves(root.left, result)
        add_leaves(root.right, result)
        if root.right:
            add_right_boundary(root.right, result)
        
        return result

def rob(self, root: TreeNode) -> int:
        def dfs(root):
            if not root:
                return [0, 0]

            leftPair = dfs(root.left)
            rightPair = dfs(root.right)

            withRoot = root.val + leftPair[1] + rightPair[1]
            withoutRoot = max(leftPair) + max(rightPair)

            return [withRoot, withoutRoot]

        return max(dfs(root))