Evaluate Reverse Polish Notation

Reverse Polish Notation (RPN) expressions are evaluated using a stack data structure. When iterating through the expression tokens, operands are pushed onto the stack. Upon encountering an operator, the top two operands are popped, the operation is executed, and the result is pushed back.

A common pitfall involves hanlding negative integers. String parsing methods like .isdigit() fail to recognize negative signs, requiring explicit handling or an operator-based conditional check. Another critical detail is division. In Python, standard division / yields a float, and floor division // rounds towards negative infinity. To comply with the problem's requirement of truncating towards zero, casting the float result of / to an integer is the most robust approach.

class Solution:
    def evalRPN(self, expressions: List[str]) -> int:
        calc_stack = []
        operations = {"+", "-", "*", "/"}
        
        for expr in expressions:
            if expr not in operations:
                calc_stack.append(int(expr))
            else:
                right_operand = calc_stack.pop()
                left_operand = calc_stack.pop()
                
                if expr == "+":
                    calc_stack.append(left_operand + right_operand)
                elif expr == "-":
                    calc_stack.append(left_operand - right_operand)
                elif expr == "*":
                    calc_stack.append(left_operand * right_operand)
                else:
                    # Truncate towards zero for division
                    calc_stack.append(int(left_operand / right_operand))
                    
        return calc_stack.pop()

Sliding Window Maximum

Finding the maximum in every sliding window of an array efficiently requires a Monotonic Deque. A standard queue or frequent max calculations result in O(nk) time complexity, whereas a monotonic deque achieves O(n).

The deque strictly maintains elements in decreasing order from front to back. When a new element enters the window, all smaller elements at the back of the deque are removed, ensuring the front always holds the current window's maximum. When the window slides, the outgoing element is removed from the front only if it matches the deque's front element. Using collections.deque is mandatory since standard list pop(0) operations are O(n).

from collections import deque

class MonotonicDeque:
    def __init__(self):
        self.data = deque()
        
    def remove_outgoing(self, outgoing_val):
        if self.data and self.data[0] == outgoing_val:
            self.data.popleft()
            
    def add_incoming(self, incoming_val):
        while self.data and incoming_val > self.data[-1]:
            self.data.pop()
        self.data.append(incoming_val)
        
    def fetch_max(self):
        return self.data[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], window_size: int) -> List[int]:
        mono_deque = MonotonicDeque()
        max_results = []
        
        for idx in range(window_size):
            mono_deque.add_incoming(nums[idx])
        max_results.append(mono_deque.fetch_max())
        
        for idx in range(window_size, len(nums)):
            mono_deque.remove_outgoing(nums[idx - window_size])
            mono_deque.add_incoming(nums[idx])
            max_results.append(mono_deque.fetch_max())
            
        return max_results

Top K Frequent Elements

Identifying the most frequent elements involves two main steps: counting frequencies and extracting the top k counts. A hash map efficiently stores the frequency of each element.

To filter the top k elements without sorting the entire map, a Min-Heap (Priority Queue) is utilized. By maintaining a heap size of exactly k, the least frequent elements are continuously evicted when the heap exceeds its capacity limit. After processing all elements, the remaining items in the min-heap represent the k most frequent elements, which can then be extracted.

import heapq

class Solution:
    def topKFrequent(self, nums: List[int], limit: int) -> List[int]:
        freq_map = {}
        for num in nums:
            freq_map[num] = freq_map.get(num, 0) + 1
            
        min_heap = []
        for val, count in freq_map.items():
            heapq.heappush(min_heap, (count, val))
            if len(min_heap) > limit:
                heapq.heappop(min_heap)
                
        top_k = []
        while min_heap:
            top_k.append(heapq.heappop(min_heap)[1])
            
        return top_k