Evaluating Reverse Polish Notation

Problem:

Given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation, evaluate the expression and return the resulting integer value.

Constraints:

• Valid operators are '+', '-', '*', and '/'.
• Each operand can be an integer or another expression.
• Division between two integers always truncates toward zero.
• The expression contains no division by zero.
• The input is a valid expression in Reverse Polish Notation.
• The result and all intermediate calculations fit within a 32-bit integer.

Approach:

Reverse Polish Notation (RPN) is a postfix notation where operators follow they operands. This format is well-suited for stack-based evaluation:

• When encountering a number, push it onto the stack.
• When encountering an operator, pop the top two numbers from the stack, apply the operation, and push the result back.
• Special attention is needed for subtraction and division to maintain correct operand order.

Solution:

class Solution {
    public int evaluateRPN(String[] tokens) {
        Deque<Integer> evaluationStack = new LinkedList<>();
        
        for (String token : tokens) {
            switch (token) {
                case "+":
                    evaluationStack.push(evaluationStack.pop() + evaluationStack.pop());
                    break;
                case "-":
                    int subtrahend = evaluationStack.pop();
                    int minuend = evaluationStack.pop();
                    evaluationStack.push(minuend - subtrahend);
                    break;
                case "*":
                    evaluationStack.push(evaluationStack.pop() * evaluationStack.pop());
                    break;
                case "/":
                    int divisor = evaluationStack.pop();
                    int dividend = evaluationStack.pop();
                    evaluationStack.push(dividend / divisor);
                    break;
                default:
                    evaluationStack.push(Integer.parseInt(token));
            }
        }
        
        return evaluationStack.pop();
    }
}

Sliding Window Maximum

Problem:

Given an integer array nums and a sliding window of size k that moves from the leftmost to the rightmost of the array, return an array containing the maximum value in each sliding window position.

Approach:

① Brute Force: For each window position, find the maximum value. This approach is inefficient and typically exceeds time limits.

② Monotonic Queue: Implement a custom queue that maintains the following properties:

• The maximum value in the current window is always at the front of the queue.
• When adding a new element, remove all smaller elements from the back to maintain decreasing order.
• When removing an element, only remove it from the front if it's the current maximum.

Solution:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        
        int[] results = new int[nums.length - k + 1];
        int resultIndex = 0;
        MonotonicQueue window = new MonotonicQueue();
        
        // Initialize the first window
        for (int i = 0; i < k; i++) {
            window.add(nums[i]);
        }
        results[resultIndex++] = window.getMax();
        
        // Slide the window across the array
        for (int i = k; i < nums.length; i++) {
            window.remove(nums[i - k]);
            window.add(nums[i]);
            results[resultIndex++] = window.getMax();
        }
        
        return results;
    }
    
    class MonotonicQueue {
        Deque<Integer> queue;
        
        public MonotonicQueue() {
            queue = new LinkedList<>();
        }
        
        void add(int value) {
            while (!queue.isEmpty() && queue.peekLast() < value) {
                queue.pollLast();
            }
            queue.offerLast(value);
        }
        
        void remove(int value) {
            if (!queue.isEmpty() && queue.peekFirst() == value) {
                queue.pollFirst();
            }
        }
        
        int getMax() {
            return queue.peekFirst();
        }
    }
}

Top K Frequent Elements

Problem:

Given an integer array nums and an integer k, return the k most frequent elements. The result can be in any order.

Approach:

1. Use a hash map to count the frequency of each element.
2. Use a priority queue to sort elements by frequency.

Two approaches with priority queues:

• Max-heap: Store all elements and sort by frequency in descending order.
• Min-heap: Maintain only the top k elements, which is more efficient for large datasets.

Solution:

// Max-heap implementation
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = 
            new PriorityQueue<>((entry1, entry2) -> entry2.getValue() - entry1.getValue());
        
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            maxHeap.offer(entry);
        }
        
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll().getKey();
        }
        
        return result;
    }
}

// Min-heap implementation
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = 
            new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else if (entry.getValue() > minHeap.peek().getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }
        
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll().getKey();
        }
        
        return result;
    }
}