Monotonic Stack/Queue Patterns

from typing import List

def next_greater_element(nums: List[int]) -> List[int]:
    """
    Find the next greater element for each element in the array
    
    Args:
        nums: List of integers to process
        
    Returns:
        List where result[i] is the next greater element for nums[i], or -1 if none exists
        
    Raises:
        ValueError: If input list is None
        
    Time Complexity: O(n) - each element is pushed and popped at most once
    Space Complexity: O(n) - for the result list and stack
    
    Example: next_greater_element([2, 1, 2, 4, 3, 1]) → [4, 2, 4, -1, -1, -1]
    """
    # Input validation
    if nums is None:
        raise ValueError("Input list cannot be None")
    
    if len(nums) == 0:
        return []
    
    # Handle single element case
    if len(nums) == 1:
        return [-1]
    
    result = [-1] * len(nums)
    stack = []  # Store indices
    
    for i, num in enumerate(nums):
        # Pop elements smaller than current element
        while stack and nums[stack[-1]] < num:
            index = stack.pop()
            result[index] = num
        stack.append(i)
    
    return result

def daily_temperatures(temperatures: List[int]) -> List[int]:
    """
    Calculate how many days until a warmer temperature for each day
    
    Args:
        temperatures: List of daily temperatures
        
    Returns:
        List where result[i] is days until warmer temperature, or 0 if never
        
    Raises:
        ValueError: If input list is None or contains invalid temperatures
        
    Time Complexity: O(n) - each element processed once
    Space Complexity: O(n) - for stack and result list
    
    Example: daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) → [1,1,4,2,1,1,0,0]
    """
    # Input validation
    if temperatures is None:
        raise ValueError("Temperatures list cannot be None")
    
    if len(temperatures) == 0:
        return []
    
    # Validate temperature values
    for i, temp in enumerate(temperatures):
        if not isinstance(temp, (int, float)) or temp != temp:  # Check for NaN
            raise ValueError(f"Invalid temperature at index {i}: {temp}")
    
    result = [0] * len(temperatures)
    stack = []
    
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index  # Days difference
        stack.append(i)
    
    return result

def next_greater_elements_circular(nums: List[int]) -> List[int]:
    """
    Find next greater element in circular array (array wraps around)
    
    Args:
        nums: List of integers treated as circular
        
    Returns:
        List where result[i] is next greater element (may wrap around), or -1 if none
        
    Raises:
        ValueError: If input list is None
        
    Time Complexity: O(n) - each element processed at most twice
    Space Complexity: O(n) - for stack and result list
    
    Example: next_greater_elements_circular([1,2,1]) → [2,-1,2]
    """
    # Input validation
    if nums is None:
        raise ValueError("Input list cannot be None")
    
    if len(nums) == 0:
        return []
    
    if len(nums) == 1:
        return [-1]
    
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # Process array twice to handle circular nature
    for i in range(2 * n):
        current_index = i % n
        
        while stack and nums[stack[-1]] < nums[current_index]:
            index = stack.pop()
            result[index] = nums[current_index]
        
        # Only push in first iteration
        if i < n:
            stack.append(current_index)
    
    return result

def stock_span(prices: List[float]) -> List[int]:
    """
    Calculate stock span for each day (consecutive days with price <= current day)
    
    Args:
        prices: List of stock prices for consecutive days
        
    Returns:
        List where span[i] is number of consecutive days (including current) with price <= prices[i]
        
    Raises:
        ValueError: If input list is None or contains invalid prices
        
    Time Complexity: O(n) - each element pushed/popped once
    Space Complexity: O(n) - for stack and result list
    
    Example: stock_span([100, 80, 60, 70, 60, 75, 85]) → [1,1,1,2,1,4,6]
    """
    # Input validation
    if prices is None:
        raise ValueError("Prices list cannot be None")
    
    if len(prices) == 0:
        return []
    
    # Validate price values
    for i, price in enumerate(prices):
        if not isinstance(price, (int, float)) or price != price or price < 0:
            raise ValueError(f"Invalid price at index {i}: {price}")
    
    span = [0] * len(prices)
    stack = []  # Store indices
    
    for i, price in enumerate(prices):
        # Pop indices of prices smaller than or equal to current price
        while stack and prices[stack[-1]] <= price:
            stack.pop()
        
        # Span is distance to previous greater element
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    
    return span

def remove_k_digits(num: str, k: int) -> str:
    """
    Remove k digits from number to form the smallest possible number
    
    Args:
        num: String representation of a number
        k: Number of digits to remove
        
    Returns:
        Smallest possible number after removing k digits
        
    Raises:
        ValueError: If inputs are invalid
        
    Time Complexity: O(n) - each digit processed once
    Space Complexity: O(n) - for stack storage
    
    Example: remove_k_digits("1432219", 3) → "1219"
    """
    # Input validation
    if not isinstance(num, str) or num is None:
        raise ValueError("Number must be a valid string")
    
    if not num.isdigit():
        raise ValueError("Number string must contain only digits")
    
    if not isinstance(k, int) or k < 0:
        raise ValueError("k must be a non-negative integer")
    
    if k >= len(num):
        return "0"
    
    if k == 0:
        return num
    
    stack = []
    to_remove = k
    
    for digit in num:
        # Remove larger digits from stack if possible
        while stack and stack[-1] > digit and to_remove > 0:
            stack.pop()
            to_remove -= 1
        stack.append(digit)
    
    # Remove remaining digits from end if needed
    while to_remove > 0 and stack:
        stack.pop()
        to_remove -= 1
    
    # Build result and handle leading zeros
    result = ''.join(stack).lstrip('0')
    return result or '0'

# Advanced: Next Greater Element with frequency
def next_greater_frequency(arr):
    """Find next element with greater frequency"""
    from collections import Counter
    
    freq = Counter(arr)
    result = [-1] * len(arr)
    stack = []
    
    for i, num in enumerate(arr):
        while stack and freq[arr[stack[-1]]] < freq[num]:
            index = stack.pop()
            result[index] = num
        stack.append(i)
    
    return result

# Monotonic Queue for Sliding Window Maximum
from collections import deque

def sliding_window_maximum(nums, k):
    """Find maximum in each sliding window of size k"""
    if not nums or k == 0:
        return []
    
    dq = deque()  # Store indices in decreasing order of values
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside current window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Remove indices of smaller elements
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Add to result if window is of size k
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

# Example usage
def demonstrate_monotonic_patterns():
    print("Next Greater Element:")
    print(next_greater_element([2, 1, 2, 4, 3, 1]))  # [4, 2, 4, -1, -1, -1]
    
    print("\nDaily Temperatures:")
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))  # [1,1,4,2,1,1,0,0]
    
    print("\nStock Span:")
    print(stock_span([100, 80, 60, 70, 60, 75, 85]))  # [1,1,1,2,1,4,6]
    
    print("\nSliding Window Maximum:")
    print(sliding_window_maximum([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]