Evaluating Reverse Polish Notation

Reverse Polish Notation (RPN) eliminates the need for parentheses by placing operators after their operands. A stack-based approach efficiently processes tokens in a single pass.

class Solution {
public:
    int evalRPN(vector<string>& expr) {
        stack<int> eval_stack;
        for (const auto& token : expr) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int right_operand = eval_stack.top(); eval_stack.pop();
                int left_operand = eval_stack.top(); eval_stack.pop();

                if (token == "+") eval_stack.push(left_operand + right_operand);
                else if (token == "-") eval_stack.push(left_operand - right_operand);
                else if (token == "*") eval_stack.push(left_operand * right_operand);
                else eval_stack.push(left_operand / right_operand);
            } else {
                eval_stack.push(std::stoi(token));
            }
        }
        return eval_stack.top();
    }
};

Implementation Notes

• Operand extraction order is critical. The first popped value is the right operand, and the second is the left operand. This distinction directly impacts subtraction and division results.
• std::stoi safely converts string tokens to integers, replacing legacy C-style atoi and c_str() calls.
• Control flow structures like switch in C++ require integral or enumeration types. String comparisons must use if-else chains or hash maps.

Sliding Window Maximum

Finding the maximum value in a fixed-size sliding window requires maintaining potential candidates efficiently. A monotonic deque stores indices rather than values, ensuring O(1) amortized operations per element.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& input_arr, int window_size) {
        if (input_arr.empty() || window_size <= 0) return {};

        deque<int> idx_deque;
        vector<int> max_values;
        max_values.reserve(input_arr.size() - window_size + 1);

        for (int i = 0; i < input_arr.size(); ++i) {
            while (!idx_deque.empty() && input_arr[idx_deque.back()] <= input_arr[i]) {
                idx_deque.pop_back();
            }
            idx_deque.push_back(i);

            if (idx_deque.front() <= i - window_size) {
                idx_deque.pop_front();
            }

            if (i >= window_size - 1) {
                max_values.push_back(input_arr[idx_deque.front()]);
            }
        }
        return max_values;
    }
};

Implementation Notes

• The deque maintains indices in strictly decreasing order of their corresponding array values. Incoming elements evict smaller or equal trailing elements, as those older values can never be the window maximum again.
• Index tracking simplifies window boundary checks. Removing the front index when it falls outside the current range (i - window_size) keeps the structure valid.
• Pre-allocating result capacity with reserve() prevents repeated memory reallocations during push_back operations.
• Core std::deque operations include push_back, pop_back, pop_front, front, and back, all operating in constant time.

Top K Frequent Elements

Identifying the most frequent items combines frequency counting with heap-based selection. Two primary heap strategies exist: max-heap extraction and min-heap maintenance.

Approach 1: Max-Heap Extraction

class Solution {
public:
    vector<int> topKFrequent(vector<int>& data, int k) {
        unordered_map<int, int> freq_map;
        for (int val : data) freq_map[val]++;

        priority_queue<pair<int, int>> max_heap;
        for (const auto& entry : freq_map) {
            max_heap.emplace(entry.second, entry.first);
        }

        vector<int> result;
        result.reserve(k);
        while (k-- > 0) {
            result.push_back(max_heap.top().second);
            max_heap.pop();
        }
        return result;
    }
};

Implementation Notes

• std::priority_queue defaults to a max-heap. When storing std::pair, comparrison automatically targets the first element (frequency), making it ideal for ranking.
• std::unordered_map provides average O(1) insertion and lookup, outperforming std::map (O(log n)) when key ordering is unnecessary.

Approach 2: Min-Heap with Custom Comparator

struct FreqComparator {
    bool operator()(const pair<int, int>& left, const pair<int, int>& right) const {
        return left.first > right.first;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& data, int k) {
        unordered_map<int, int> counts;
        for (int num : data) counts[num]++;

        priority_queue<pair<int, int>, vector<pair<int, int>>, FreqComparator> min_heap;
        for (const auto& kv : counts) {
            min_heap.emplace(kv.second, kv.first);
            if (min_heap.size() > k) {
                min_heap.pop();
            }
        }

        vector<int> top_k(k);
        for (int i = k - 1; i >= 0; --i) {
            top_k[i] = min_heap.top().second;
            min_heap.pop();
        }
        return top_k;
    }
};

Implementation Notes

• A min-heap capped at size k reduces time complexity to O(N log K). The smallest frequency is continuously evicted, preserving only the top candidates.
• Custom comparators for std::priority_queue require a functor or lambda that overloads operator(). The logic is inverted compared to standard sorting: returning true when left > right establishes min-heap behavior.
• The underlying container must be explicit specified (std::vector) when providing a custom comparator template argument.
• Result extraction iterates backward to arrange elements in descending frequency order without additional sorting steps.