Evaluating Reverse Polish Notation (LeetCode 150)

Reverse Polish Notation (RPN), also known as postfix expression, places operators after thier operands. For example, the infix expression (1 + 2) * (3 + 4) becomes 1 2 + 3 4 + * in RPN. This notation eliminates ambiguity and parenthetical grouping, making it ideal for stack-based evaluation.

The algorithm processes tokens sequentially: push numbers onto the stack, and when encountering an operator, pop two operands, compute the result, and push it back. Postfix notation corresponds to postorder traversal (left-right-root) of an expression tree, while infix notation corresponds to inorder traversal.

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> s;
        for (const string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                long long operandA = s.top(); s.pop();
                long long operandB = s.top(); s.pop();
                
                if (token == "+") s.push(operandB + operandA);
                else if (token == "-") s.push(operandB - operandA);
                else if (token == "*") s.push(operandB * operandA);
                else s.push(operandB / operandA);
            } else {
                s.push(stoll(token));
            }
        }
        return static_cast<int>(s.top());
    }
};

Key Points

1. long long: A 64-bit signed integer type in C++, capable of representing values from -2^63 to 2^63 - 1.

2. stoll: Converts a string to a long long integer.

Common Pitfall

When popping two numbers for computation, the second-popped operand (operandB) must be positioned before the operator. Reversing this order produces incorrect results for subtraction and division operations.

Sliding Window Maximum (LeetCode 239)

This problem requires finding the maximum element in each sliding window of size k. A deque (double-ended queue) can maintain a monotonically decreasing sequence, where the front always contains the maximum of the current window.

The core idea involves a custom monotonic queue that handles two operations:

• push: If the incoming value exceeds elements at the back, remove those smaller elements first. This ensures the deque stays in descending order.
• pop: Only remove from the front if the value being popped matches the front element; otherwise, do nothing since smaller elements were already discarded during push.

class Solution {
public:
    class MonotonicQueue {
    public:
        deque<int> data;
        
        void enqueue(int val) {
            while (!data.empty() && val > data.back()) {
                data.pop_back();
            }
            data.push_back(val);
        }
        
        void dequeue(int val) {
            if (!data.empty() && val == data.front()) {
                data.pop_front();
            }
        }
        
        int currentMax() {
            return data.front();
        }
    };
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MonotonicQueue mq;
        vector<int> result;
        
        for (int i = 0; i < k; ++i) {
            mq.enqueue(nums[i]);
        }
        result.push_back(mq.currentMax());
        
        for (int i = k; i < nums.size(); ++i) {
            mq.dequeue(nums[i - k]);
            mq.enqueue(nums[i]);
            result.push_back(mq.currentMax());
        }
        return result;
    }
};

The algorithm first populates the initial window of size k, then slides the window one position at a time, recording the maximum after each movement.

Top K Frequent Elements (LeetCode 347)

Heap Fundamentals

Heaps are complete binary trees with specific ordering properties:

• Max Heap: Parent nodes contain values greater than or equal to their children
• Min Heap: Parent nodes contain values less than or equal to their children

Priority queues in C++ STL implement heaps by default as max heaps. To create a min heap, use greater as the comparator.

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

Custom Comparator Implementation

The comparator must implement operator() rather than comparison operators because:

1. It acccepts flexible parameter types and quantities
2. It allows easier modification of comparison logic when requirements change

class Solution {
public:
    struct FrequencyCompare {
        bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
            return a.second > b.second;
        }
    };
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> frequency;
        for (const int& num : nums) {
            ++frequency[num];
        }
        
        priority_queue<pair<int,int>, vector<pair<int,int>>, FrequencyCompare> pq;
        
        for (const auto& entry : frequency) {
            pq.push(entry);
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
        vector<int> answer(k);
        for (int i = k - 1; i >= 0; --i) {
            answer[i] = pq.top().first;
            pq.pop();
        }
        return answer;
    }
};

Key Points

1. With greater as the comparator, smaller elements receive higher priority and bubble to the top of a min heap.

2. Elements are extracted in ascending order, requiring reverse insertion into the result array.

Common Pitfall

The comparator class must declare its operator() as public. Private access triggers compilation errors during priority queue operations.