Session Notes: The "Aggregate Deque" (Queue & Deque with Stacks)

1. The Basics: What is a "Container"?

Think of a Container as a box to store your data. We choose the container based on how we need to access the memory.

• Vector: A single continuous block of memory. Fast access, hard to resize.
• List: Data scattered in memory. Easy to delete, slow to find.

The "Bucket" Concept: Splitting data into smaller buckets (Stacks) allows us to manage "Min/Max" history efficiently.

2. The Problem: Sliding Window Aggregates

We often need to find the Max, Min, GCD, or Bitwise OR of a group of numbers that keeps changing (a "Sliding Window").

The Two Types of Operations

• Invertible (Easy): +, -, XOR. If a number leaves, you simply "subtract" it.
• Idempotent (Hard): Max, Min, GCD, OR.

Issue: If the Max is 100 and the number 100 leaves, you can't subtract it to find the new Max. You usually have to rescan (\(O(K)\)).

Solution: The Aggregate Deque allows us to remove elements and query the aggregate in \(O(1)\).

3. The Core Logic: Stacks as Queues

A Queue is FIFO. A Stack is LIFO. To make a Queue from Stacks, we use Two Stacks: Input (Push) and Output (Pop).

Why is this efficient? (The Banker's Proof)

It might look slow because sometimes we move all elements from Input to Output. However, using the Accounting Method, we prove it is Amortized \(O(1)\).

The Coin Analogy:

Imagine every Push operation costs 3 coins:

1. 1 coin pays for the Push itself.
2. 2 coins are saved (banked) with the element.

The Lifecycle of an Element:

• Push: Cost 1. (Bank 2).
• Move (Rebalance): When Output is empty, we move the element.
  • Pop from Input (Cost 1).
  • Push to Output (Cost 1).
  • Total Cost: 2. We pay this using the 2 banked coins.
• Pop: Cost 1.

Result: Every step is paid for in advance. Total work per element is constant.

4. Homework Task 1: Output-Restricted Aggregate Deque

• Requirement: Push Back, Push Front, Pop Front.
• Use Case: A sliding window that mostly moves right, but occasionally needs to extend left.

2 Stacks vs. 3 Stacks?

You do NOT need 3 stacks. We can implement this efficiently with just 2 Vectors:

• F (Front): Handles push_front and pop_front.
• B (Back): Handles push_back.

Logic:

• Pushing to Front or Back is trivial (\(O(1)\)).
• Popping Front: If F is empty, we move ALL elements from B to F. This reverses them, placing the oldest element of B at the top of F, ready to be popped.

C++ Implementation (Concise)

View Simplified C++ Solution

struct Node { int val, agg; };

// Example: GCD Operation
int get_gcd(int a, int b) { return gcd(a, b); }

class OutputRestrictedDeque {
    vector<Node> F, B; // Front, Back

    void push(vector<Node>& st, int val) {
        int agg = st.empty() ? val : get_gcd(st.back().agg, val);
        st.push_back({val, agg});
    }

public:
    void push_front(int val) { push(F, val); }
    void push_back(int val)  { push(B, val); }

    void pop_front() {
        if (F.empty()) {
            // Lazy Move: Move ALL from Back to Front
            while (!B.empty()) {
                push(F, B.back().val); // Calculates agg automatically
                B.pop_back();
            }
        }
        if (!F.empty()) F.pop_back();
    }

    int query() {
        if (F.empty() && B.empty()) return -1;
        if (F.empty()) return B.back().agg;
        if (B.empty()) return F.back().agg;
        return get_gcd(F.back().agg, B.back().agg);
    }
};

Walkthrough: The Lazy Flip

Scenario: F is empty, B has [10, 20]. We call pop_front().

1. Initial State:
   • F: [] (Empty)
   • B: [10, 20] (Top is 20)
2. Action: pop_front() triggers rebalance because F is empty.
3. Refill F:
   • Pop 20 from B -> Push to F. F: [20]
   • Pop 10 from B -> Push to F. F: [20, 10]
4. Final State:
   • F: [20, 10] (Top is 10, which matches the oldest element!)
   • B: []
5. Pop: Remove 10 from F. Return.

5. Homework Task 2: Full Aggregate Deque

• Requirement: Push and Pop from BOTH ends.

The Problem with "Move All"

If we use the logic from Task 1 (moving everything when a stack is empty), we encounter the Ping-Pong Failure:

• L is empty. Pop Front -> Move ALL R to L.
• R is now empty. Pop Back -> Move ALL L to R.
• Result: Every operation becomes \(O(N)\).

The Solution: "Move Half"

When a stack is empty, we only move half the elements from the other stack.

Mathematical Proof (Refill Interval):

If we move \(N/2\) elements to L:

• Cost: \(N\) operations (to move elements).
• Benefit: L now has \(N/2\) elements.
• Result: The user must perform at least \(N/2\) cheap \(O(1)\) pops before L becomes empty again.

Amortized Cost: \(\frac{\text{Cost}}{\text{Ops}} = \frac{N}{N/2} = 2\). The average cost is constant (\(O(1)\)).

Edge Case Fix (N=1)

If R has 1 element and L is empty, \(N/2=0\). We would move nothing and crash.

• Fix: mid = (n + 1) / 2.
• If \(N=1\), mid=1. We move the 1 element.
• If \(N=4\), mid=2. We move 2 elements.

C++ Implementation (Concise)

View Simplified C++ Solution

struct Node { int val, agg; };

class AggregateDeque {
    vector<Node> L, R; // Left (Front), Right (Back)

    void push(vector<Node>& st, int val) {
        int agg = st.empty() ? val : max(st.back().agg, val);
        st.push_back({val, agg});
    }

    // The O(1) Amortized Magic: Move Half
    void rebalance(vector<Node>& src, vector<Node>& dest) {
        if (src.empty()) return;

        vector<int> tmp; 
        for(auto& n : src) tmp.push_back(n.val);
        src.clear();

        int n = tmp.size();
        int mid = (n + 1) / 2; // (n+1)/2 ensures we move 1 item if n=1

        // Move bottom half (Oldest) to dest
        for (int i = mid - 1; i >= 0; --i) push(dest, tmp[i]);

        // Keep top half (Newest) in src
        for (int i = mid; i < n; ++i) push(src, tmp[i]);
    }

public:
    void push_front(int v) { push(L, v); }
    void push_back(int v)  { push(R, v); }

    void pop_front() {
        if (L.empty()) rebalance(R, L);
        if (!L.empty()) L.pop_back();
    }

    void pop_back() {
        if (R.empty()) rebalance(L, R);
        if (!R.empty()) R.pop_back();
    }

    int query() {
        if (L.empty() && R.empty()) return -1;
        if (L.empty()) return R.back().agg;
        if (R.empty()) return L.back().agg;
        return max(L.back().agg, R.back().agg);
    }
};

Walkthrough: The Move Half Strategy

Scenario: L is empty, R has [1, 2, 3, 4]. We call pop_front().

1. Identify State: N=4. We need to move Mid = (4+1)/2 = 2 elements.
2. Split:
   • Bottom Half (Oldest): [1, 2] -> Should go to L.
   • Top Half (Newest): [3, 4] -> Should stay in R.
3. Move to L (Reverse Order):
   • Move 2. L: [2]
   • Move 1. L: [2, 1]
4. Reconstruct R:
   • Keep 3, 4. R: [3, 4]
5. Final State:
   • L: [2, 1] (Top is 1, ready to pop!)
   • R: [3, 4] (Ready for future pop_back)

6. Monotonic Queue vs. Aggregate Queue

When should you use which?

Feature	Monotonic Queue	Aggregate Queue
Primary Use	Finding Max/Min in a sliding window.	Finding GCD, LCM, Max/Min,Bitwise Ops (Any Associative Op).
Mechanism	Maintains a deque of indices with strictly increasing/decreasing values.	Uses Two Stacks to maintain aggregate history.
Logic	Removes "useless" elements (e.g., smaller elements ahead of a larger one).	Keeps all elements but efficiently manages their aggregates.
Pros	Simpler to specific range-min/max problems.	Universal. Works for operations that are NOT comparable (like Matrix Multiplication).
Complexity	Amortized \(O(1)\).	Amortized \(O(1)\).
Example	"Sliding Window Maximum" (LeetCode 239).	"Shortest Subarray with Sum at least K" (if K is negative) or "Subarray GCD".

Rule of Thumb:

• If you need Max/Min, use a Monotonic Queue.
• If you need GCD/XOR/Product, use an Aggregate Queue.

7. Practice Problems

Here are some standard problems to practice the Aggregate Queue and Monotonic Queue concepts:

• CSES 3221: Sliding Window Minimum
  • Type: Monotonic Queue (since "Min" is comparable).
  • Challenge: Find the minimum of every window of size \(K\).

View Code (Monotonic Queue)

vector<int> min_sliding_window(const vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        // 1. Remove elements out of window
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();

        // 2. Main Monotonic Logic: Remove useless elements
        // If current element is smaller than last, last is useless.
        while (!dq.empty() && nums[dq.back()] >= nums[i]) dq.pop_back();

        dq.push_back(i);
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

• CSES 3405: Sliding Window Bitwise OR
  • Type: Aggregate Queue (since OR is not invertible).
  • Challenge: Find the Bitwise OR of every window of size \(K\).

View Code (Aggregate Queue)

// Uses the 'Two Stacks' logic defined in Task 1/2.
// Replace 'gcd' with '|' (OR operator).
struct Node { int val, agg; };
// ... Implement Push/Pop with OR logic ...

Alternative Solution: Bit Counting for OR

If we don't want to use Two Stacks, we can exploit the property of bits.
Since bits are independent, we can maintain a frequency array of set bits for each position (0 to 30).

• Add(x): Iterate bits of x. If j-th bit is set, count[j]++.
• Remove(x): Iterate bits of x. If j-th bit is set, count[j]--.
• Query(): Reconstruct answer. If count[j] > 0, then the j-th bit is set in the window OR.

Complexity: \(O(30 \cdot N)\) ≈ \(O(N)\).

View Code (Bit Counting)

void solve(vector<int>& nums, int k) {
    int counts[32] = {0};
    auto add = [&](int x) {
        for(int i=0; i<30; ++i) if((x >> i) & 1) counts[i]++;
    };
    auto remove = [&](int x) {
        for(int i=0; i<30; ++i) if((x >> i) & 1) counts[i]--;
    };
    auto query = [&]() {
        int ans = 0;
        for(int i=0; i<30; ++i) if(counts[i] > 0) ans |= (1<<i);
        return ans;
    };

    for(int i=0; i<nums.size(); ++i) {
        add(nums[i]);
        if(i >= k) remove(nums[i-k]);
        if(i >= k-1) cout << query() << " ";
    }
}

• LeetCode 239: Sliding Window Maximum
  • Type: Monotonic Queue.

View Code (Monotonic Queue)

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // Store INDICES
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();

        // For Max: Pop if current is LARGER (strictly decreasing queue)
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();

        dq.push_back(i);
        if (i >= k - 1) res.push_back(nums[dq.front()]); // Front is Max
    }
    return res;
}

• LeetCode 862: Shortest Subarray with Sum at Least K
  • Type: Monotonic Deque (on Prefix Sums).

View Code (Mono Deque)

int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> P(n + 1, 0);
    for (int i = 0; i < n; ++i) P[i + 1] = P[i] + nums[i];

    deque<int> dq;
    int ans = n + 1;

    for (int y = 0; y <= n; ++y) {
        // 1. Contract window: if P[y] - P[first] >= k, we found a valid subarray
        while (!dq.empty() && P[y] - P[dq.front()] >= k) {
            ans = min(ans, y - dq.front());
            dq.pop_front();
        }
        // 2. Maintain Monotonicity (Increasing P[x])
        while (!dq.empty() && P[y] <= P[dq.back()]) dq.pop_back();

        dq.push_back(y);
    }
    return ans <= n ? ans : -1;
}

• LeetCode 1499: Max Value of Equation
  • Type: Monotonic Queue + Math.
  • Goal: Maximize \(y_i + y_j + |x_i - x_j| = (y_i - x_i) + (y_j + x_j)\).
  • Strategy: Maximize \((y_i - x_i)\) in the sliding window.

View Code (optimized)

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    deque<pair<int, int>> dq; // stores {y - x, x}
    int max_val = -2e9; // INT_MIN approx

    for (const auto& p : points) {
        int x = p[0], y = p[1];

        // Remove points out of range (x - x_old > k)
        while (!dq.empty() && x - dq.front().second > k) dq.pop_front();

        if (!dq.empty()) max_val = max(max_val, dq.front().first + x + y);

        // Maintain decreasing y - x
        while (!dq.empty() && dq.back().first <= y - x) dq.pop_back();
        dq.push_back({y - x, x});
    }
    return max_val;
}

• Standard Aggregate Queue Tasks (No direct link):
  • "Find the GCD of every subarray of size K." (Perfect for Aggregate Queue).
  • "Find the Bitwise AND of every subarray of size K."