Sliding Window Maximum

Problem Statement: Given an array nums and a sliding window of size k, find the maximum value in each window position as it moves from left to right.

Approach Analysis

The brute-force approach iterates through each window position and finds the maximum by comparing all k elements, resulting in O(n×k) time complexity.

A max-heap seems promising initially since it can quickly retrieve the maximum value. However, the sliding window moves by removing the leftmost element and adding a new element on the right. A standard max-heap cannot efficiently remove arbitrary elements—it can only pop the maximum, which creates a problem when the element being removed is not the current maximum.

Monotonic Queue Solution

The optimal solution uses a monotonic queue—a data structure that maintains elements in descending order. The key insight is that we only need to track elements that could potentially become the maximum. Elements that are smaller than a more recent element will never be the maximum for any future window position.

The monotonic queue must support these operations:

1. pop(value): Remove value from the front if it equals the current maximum
2. push(value): Add while removing all smaller elements from the back
3. front(): Return the current maximum

The deque (double-ended queue) is the ideal underlying container since it supports O(1) operations at both ends.

Implementation

#include <deque>
#include <vector>
#include <iostream>

class MonotonicQueue {
private:
    std::deque<int> data;

public:
    void enqueue(int value) {
        // Remove all elements smaller than the new value from the back
        while (!data.empty() && value > data.back()) {
            data.pop_back();
        }
        data.push_back(value);
    }

    void dequeue(int value) {
        // Only remove if it's the front element being pushed out
        if (!data.empty() && value == data.front()) {
            data.pop_front();
        }
    }

    int currentMax() {
        return data.front();
    }

    bool empty() {
        return data.empty();
    }
};

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    MonotonicQueue mq;
    std::vector<int> results;

    // Initialize the first window
    for (int i = 0; i < k; ++i) {
        mq.enqueue(nums[i]);
    }
    results.push_back(mq.currentMax());

    // Slide the window across the array
    for (int i = k; i < nums.size(); ++i) {
        mq.dequeue(nums[i - k]);  // Remove element leaving window
        mq.enqueue(nums[i]);     // Add new element to window
        results.push_back(mq.currentMax());
    }

    return results;
}

Top K Frequent Elements

Problem Statement: Given a non-empty integer array, return the k most frequent elements.

Example:

• Input: nums = [1,1,1,2,2,3], k = 2
• Output: [1,2]

Approach Analysis

This problem requires three distinct operations:

1. Counting element frequencies using a hash map
2. Sorting by frequency to find the top k elements
3. Returning the k most frequent elements

Priority Queue Solution

A priority queue (implemented as a heap) provides the perfect balance of functionality and efficiency. While it appears as a queue externally, internally it maintains a heap structure that allows O(1) access to the extremal element.

Understanding Heaps: A heap is a complete binary tree where parent nodes are always greater than or equal to (max-heap) or less than or equal to (min-heap) their children. The heap property allows efficient insertion and removal while maintaining sorted order.

For finding the top k frequent elements, we need a min-heap because:

• When the heap size exceeds k, we remove the smallest element
• After processing all elements, the min-heap contains the k largest elements

Implementation

#include <unordered_map>
#include <priority_queue>
#include <vector>
#include <utility>

class Solution {
private:
    // Custom comparator for min-heap based on frequency
    struct FrequencyComparator {
        bool operator()(const std::pair<int, int>& a, 
                        const std::pair<int, int>& b) const {
            return a.second > b.second;  // Min-heap: smaller frequency at top
        }
    };

public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        // Step 1: Count frequencies using hash map
        std::unordered_map<int, int> frequencyMap;
        for (int num : nums) {
            frequencyMap[num]++;
        }

        // Step 2: Use min-heap to keep top k frequent elements
        std::priority_queue<std::pair<int, int>, 
                           std::vector<std::pair<int, int>>, 
                           FrequencyComparator> minHeap;

        for (const auto& entry : frequencyMap) {
            minHeap.push(entry);
            if (minHeap.size() > k) {
                minHeap.pop();  // Remove smallest frequency
            }
        }

        // Step 3: Extract results (reverse order for correct output)
        std::vector<int> result(k);
        for (int i = k - 1; i >= 0; --i) {
            result[i] = minHeap.top().first;
            minHeap.pop();
        }

        return result;
    }
};

Time complexity: O(n log k) where n is the array size

Summary: Stack and Queue Patterns

Common Stack Applications

Recursion Implementation: The call stack stores local variables, parameters, and return addresses for each recursive call. Understanding stack behavior helps debug recursion issues.

Bracket Matching: Classic problem solved by pushing opening brackets and popping to match closing brackets. Key edge cases include:

• Unmatched opening brackets
• Incorrect bracket types
• Unmatched closing brackets

String Deduplication: Using a stack to remove adjacent duplicates—when a character equals the top, pop it; otherwise, push the new character.

Reverse Polish Notation: Each subexpression produces a result used in subsequent operations—similar to adjacent character elimination.

Common Queue Applications

Monotonic Queue Pattern: Maintain a queue where elements are strictly ordered (increasing or decreasing). Only keep elements that could potentially be needed:

• The front always contains the current extremum
• New elements remove all worse elements from the back
• Outgoing window elements are removed from the front if present

Priority Queue Pattern: Use heaps for partial ordering:

• Min-heap for getting k largest elements
• Max-heap for getting k smallest elements
• Avoid sorting entire dataset when only top k are needed

Container Choice Considerations

deque (double-ended queue):

• Supports O(1) insertion/removal at both ends
• Better than vector for frequent front operations
• Elements not stored contiguously
• Default underlying container for stack and queue

When to use each: