/*
   Leet 239. Sliding Window Maximum

   You are given an array of integers nums, there is a sliding window
   of size k which is moving from the very left of the array to the
   very right. You can only see the k numbers in the window. Each time
   the sliding window moves right by one position. Return the max
   sliding window.

   Example 1:

   Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
   Output: [3,3,5,5,6,7]
   Explanation: 
   Window position                Max
   ---------------               -----
   [1  3  -1] -3  5  3  6  7       3
    1 [3  -1  -3] 5  3  6  7       3
    1  3 [-1  -3  5] 3  6  7       5
    1  3  -1 [-3  5  3] 6  7       5
    1  3  -1  -3 [5  3  6] 7       6
    1  3  -1  -3  5 [3  6  7]      7

   Example 2:

   Input: nums = [1], k = 1
   Output: [1]
 

   Constraints:

   1 <= nums.length <= 105
   -104 <= nums[i] <= 104
   1 <= k <= nums.length
------------------------------

  LeetCode 239: Sliding Window Maximum is a very common Bloomberg-style interview question (hard
  difficulty, frequently asked).
  
  Problem recap (you should be able to state this clearly in 30 seconds):  

  Given array nums of length n and integer k, return an array of size n−k+1 where each position i
      contains the maximum in the sliding window nums[i..i+k-1].

→ Time goal: O(n) (or at worst O(n log k))
→ Space: preferably O(k)      

1. Brute Force – O(n⋅k) – Too Slow

   vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      int n = nums.size();
      vector<int> ans;
      for (int i = 0; i <= n - k; ++i) {
         int mx = *max_element(nums.begin() + i, nums.begin() + i + k);
         ans.push_back(mx);
      }
    return ans;
    }

    -> TLE on n = 10^5, k = 5 * 10^4

2. Best Solution: Monotonic Deque (Decreasing) – O(n)

  We maintain a deque of indices (not values!) in strictly decreasing order of nums values.
  Front of deque = index of current maximum in window
  → nums[deque.front()] is always the largest in current window
  Three cleaning rules (done for every new index i):
    1. Remove elements out of current window
         while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
    2. Remove useless (smaller) elements from back — they can never be max while new element is in window
         while (!dq.empty() && nums[dq.back()] <= nums[i])  dq.pop_back();

         (Use ≤ to keep deque smaller and handle duplicates cleanly)
  
    3. Add current index
       dq.push_back(i);

    4. After i ≥ k-1, answer for window ending at i is nums[dq.front()]

*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindowDeque(vector<int>& nums, int k) {
        // maintain a deque of indices (not values!) in strictly decreasing order of nums values.

        // Front of deque = index of current maximum in window

        // Remove elements out of current window
        // while (!dq.empty() && dq.front() <= i - k) dq.pop_front();

        // Remove useless (smaller) elements from back — they can
        // never be max while new element is in window
        //  while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        //(Use ≤ to keep deque smaller and handle duplicates cleanly)

        // Add current index
        // dq.push_back(i);
        // After i ≥ k-1, answer for window ending at i is nums[dq.front()]

        // Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

        int n = nums.size();
        vector<int> ans;
        deque<int> dq; // stores indices, nums[dq.front()] is max

        for (int i = 0; i < n; ++i) {

            string window;
            if (i < k-1)  window = "<>";
            if (i >= k-1) { for (int j = i-k+1; j <= i; j++) window += to_string(nums[j]) + ","; window = window.substr(0, window.size()-1); }
            cout << "<<< index: " << i << " val: " << nums[i] <<" window: [\033[32m" << window << "\033[0m] >>>" << endl;
            
            // 1. Remove indices outside current window [i-k+1, i]
            if (!dq.empty() && dq.front() == i - k) {
                cout << "  remove index outside window: pop_front: (" << dq.front() << "," << nums[dq.front()]
                     << "), front index equals i - k = " << i-k << endl;
                dq.pop_front();
            }

            // 2. Remove smaller (or equal) elements than current element from back
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                cout << "  remove smaller or equal elems from back: nums[i]=" << nums[i] << " pop_back: ("
                     << dq.back() << "," << nums[dq.back()] << ")" << endl;
                dq.pop_back();
            }

            // 3. Add current
            dq.push_back(i);
            cout << "  dq.push_back (index,value): ";
            for (size_t i = 0; i < dq.size(); i++) cout << "(" << dq[i] << "," << nums[dq[i]] << ") ";
            cout << endl;

            // 4. After first k elements → start collecting answers
            if (i >= k - 1) {
                cout << "   append result: (" << dq.front() << "," << nums[dq.front()] << ")" << endl;
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }

    // Time complexity: O(n log k) worst case
    //  * Each insertion: O(log k)
    //  * Each element can cause multiple pops in worst case (but amortized still O(log k) per element)
    //→ Total: O(n log k)
    vector<int> maxSlidingWindowMaxHeap(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        
        // max-heap: {value, index}
        priority_queue<pair<int,int>> pq;
        
        for (int i = 0; i < n; ++i) {
            pq.emplace(nums[i], i);
            
            // Remove invalid (out of window) elements
            while (!pq.empty() && pq.top().second <= i - k) {
                pq.pop();
            }
            
            if (i >= k - 1) {
                ans.push_back(pq.top().first);
            }
        }
        return ans;
    }
};


int main(void)
{
    vector<tuple<vector<int>, int, vector<int>>> testCases {
        // input               k  output
        { {1,3,-1,-3,5,3,6,7}, 3, {3,3,5,5,6,7} },
        { {1},                 1, {1}           },
        { {1,2,3,4,5,6,7},     3, {3,4,5,6,7} },
        { {5,4,3,2,1},         2, {5,4,3,2} },
    };

    Solution s;

    auto toStr = [](const vector<int>& v)
    {
        string s("[");
        for (auto& i: v) s += to_string(i) + ",";
        s += "]";
        return s;        
    };
    
    for (const auto& testCase: testCases)
    {
        vector<int> input = get<0>(testCase);
        int k = get<1>(testCase);
        vector<int> expected = get<2>(testCase);
        
        // cout << "input: "    << setw(22) << left << toStr(input)
        //      << "k: "        << setw(3)  << left << k
        //      << "expected: " << setw(22) << left << toStr(expected)
        //      << endl;

        cout << format("input: {:<22}", toStr(input))
             << format("k: {:<3}", k)
             << format("expected: {:<22}",toStr(expected))
             << endl;

        vector<int> result = s.maxSlidingWindowDeque(input, k);
        cout << "result: ";
        for (auto& i: result) cout << i << " ";
        cout << endl;        
        EXPECT_EQ(result, expected);
        cout << format("{:-<25}", '-') << endl;
    }

    return 0;
}