Problem Solving Framework

1. Define input and output specifications
2. Analyze time and space complexity
3. Decompose complex problems: Break down into smaller, solvable subproblems (stack and queue operations, variations of stack/queue applications) – (Focus on patttern recognition)
4. Select appropriate algorithms: Based on decomposed subproblems, choose suitable approaches (monotonic queues, priority queues)
5. Handle edge cases: Consider boundary condiitons and special scenarios
6. Return final result

Reverse Polish Notation Evaluation (Stack Application) Reverse Polish Notation (RPN) is a mathematical notation where operators follow their operands. This can be efficiently evaluated using a stack.

class RPNCalculator {
    private static final Set<Character> OPERATORS = Set.of('+', '-', '*', '/');
    
    public static int evaluateRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (String token : tokens) {
            if (token.length() == 1 && OPERATORS.contains(token.charAt(0))) {
                if (stack.size() < 2) {
                    throw new IllegalArgumentException("Insufficient operands for operation");
                }
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(performOperation(operand1, operand2, token.charAt(0)));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        
        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid expression");
        }
        
        return stack.pop();
    }
    
    private static int performOperation(int a, int b, char operator) {
        return switch (operator) {
            case '+' -> a + b;
            case '-' -> a - b;
            case '*' -> a * b;
            case '/' -> a / b;
            default -> throw new IllegalArgumentException("Unknown operator: " + operator);
        };
    }
}

Sliding Window Maximum (Monotonic Queue) Finding the maximum value in each sliding window of size k in an array can be optimized using a monotonic decreasing queue.

class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[n - k + 1];
        
        for (int i = 0; i < n; i++) {
            // Remove elements from the back that are smaller than current element
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // Remove elements that are out of the current window
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            
            // Record the maximum for the current window
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

Top K Frequent Elements (Priority Queue) Finding the k most frequent elements in an array can be efficiently solved using a priority queue (min-heap).

class TopKFrequentElements {
    public static int[] topKFrequent(int[] nums, int k) {
        // Count frequency of each number
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        // Use a min-heap to keep track of top k elements
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue)
        );
        
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        // Extract the results
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll().getKey();
        }
        
        return result;
    }
}