--- Difficulty: Hard Source: 160 Days of Problem Solving Tags: - Stack - sliding-window --- # πŸš€ _Day 6. Maximum of minimum for every window size_ 🧠 The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/stack-gfg-160/problem/maximum-of-minimum-for-every-window-size3453) ## πŸ’‘ **Problem Description:** Given an array of integers **arr[]**, find the **maximum of the minimum element** for every window size **w** from **1 to N**. ## πŸ” **Example Walkthrough:** ### **Example 1** ### **Input:** ``` arr[] = {10, 20, 30, 50, 10, 70, 30} ``` ### **Output:** ``` 70 30 20 10 10 10 10 ``` ### **Explanation:** | **Window Size (k)** | **Subarrays of size k** | **Minimum in each subarray** | **Maximum among these minimums** | | ------------------- | ---------------------------------------------------------------------- | ---------------------------- | -------------------------------- | | 1 | {10}, {20}, {30}, {50}, {10}, {70}, {30} | 10, 20, 30, 50, 10, 70, 30 | 70 | | 2 | {10, 20}, {20, 30}, {30, 50}, {50, 10}, {10, 70}, {70, 30} | 10, 20, 30, 10, 10, 30 | 30 | | 3 | {10, 20, 30}, {20, 30, 50}, {30, 50, 10}, {50, 10, 70}, {10, 70, 30} | 10, 20, 10, 10, 10 | 20 | | 4 | {10, 20, 30, 50}, {20, 30, 50, 10}, {30, 50, 10, 70}, {50, 10, 70, 30} | 10, 10, 10, 10 | 10 | | 5 | {10, 20, 30, 50, 10}, {20, 30, 50, 10, 70}, {30, 50, 10, 70, 30} | 10, 10, 10 | 10 | | 6 | {10, 20, 30, 50, 10, 70}, {20, 30, 50, 10, 70, 30} | 10, 10 | 10 | | 7 | {10, 20, 30, 50, 10, 70, 30} | 10 | 10 | ## **Example 2** ### **Input:** ``` arr[] = {1, 3, 2, 4, 5} ``` ### **Output:** ``` 5 3 2 1 1 ``` ### **Explanation:** | **Window Size (k)** | **Subarrays of size k** | **Minimum in each subarray** | **Maximum among these minimums** | | ------------------- | ------------------------------- | ---------------------------- | -------------------------------- | | 1 | {1}, {3}, {2}, {4}, {5} | 1, 3, 2, 4, 5 | 5 | | 2 | {1, 3}, {3, 2}, {2, 4}, {4, 5} | 1, 2, 2, 4 | 3 | | 3 | {1, 3, 2}, {3, 2, 4}, {2, 4, 5} | 1, 2, 2 | 2 | | 4 | {1, 3, 2, 4}, {3, 2, 4, 5} | 1, 2 | 1 | | 5 | {1, 3, 2, 4, 5} | 1 | 1 | ## **Constraints:** - $\( 1 \leq N \leq 10^5 \)$ - $\( 1 \leq arr[i] \leq 10^6 \)$ ## 🎯 **My Approach:** ### **Optimized Stack-Based Approach (O(N) Time, O(N) Space)** To efficiently find the **maximum of the minimum for every window size**, we use a **monotonic stack** to determine the **window size for which each element is the minimum**. ### **Algorithm Steps:** 1. **Find the nearest smaller elements on both left and right sides** - Store the **left boundary** (`prevSmaller[i]`) where `arr[i]` is the minimum. - Store the **right boundary** (`nextSmaller[i]`) where `arr[i]` is the minimum. - Use **stacks** to efficiently compute these values. 2. **Calculate the window size where each element is the minimum** - The window size for `arr[i]` is `nextSmaller[i] - prevSmaller[i] - 1`. 3. **Store maximum values for each window size** - Use an array `res[]` to store the maximum of the minimums for each window size. 4. **Propagate the maximum values** - Ensure `res[i]` contains the maximum for all larger windows using **backward propagation**. ## πŸ•’ **Time and Auxiliary Space Complexity** - **Expected Time Complexity:** O(N), since each element is processed once. - **Expected Auxiliary Space Complexity:** O(N), for storing index boundaries and stack operations. ## πŸ“ **Solution Code** ## **Code (C++)** ```cpp class Solution { public: vector maxOfMins(vector& arr) { int n = arr.size(); vector res(n), len(n); stack s; for (int i = 0; i <= n; i++) { while (!s.empty() && (i == n || arr[s.top()] >= arr[i])) { int j = s.top(); s.pop(); len[j] = s.empty() ? i : i - s.top() - 1; } if (i < n) s.push(i); } for (int i = 0; i < n; i++) res[len[i] - 1] = max(res[len[i] - 1], arr[i]); for (int i = n - 2; i >= 0; i--) res[i] = max(res[i], res[i + 1]); return res; } }; ```

⚑ Alternative Approaches (C++)

 ## **2️⃣ Stack-Based Approach (Left-Right Boundaries)** - Uses **two passes** to determine window lengths. - More explicit calculation of **left and right limits**. ```cpp class Solution { public: vector maxOfMins(vector& arr) { int n = arr.size(); vector res(n), len(n, n); stack s; for (int i = 0; i < n; i++) { while (!s.empty() && arr[s.top()] >= arr[i]) s.pop(); len[i] = s.empty() ? i + 1 : i - s.top(); s.push(i); } s = stack(); for (int i = n - 1; i >= 0; i--) { while (!s.empty() && arr[s.top()] > arr[i]) s.pop(); len[i] += s.empty() ? n - i - 1 : s.top() - i - 1; s.push(i); } for (int i = 0; i < n; i++) res[len[i] - 1] = max(res[len[i] - 1], arr[i]); for (int i = n - 2; i >= 0; i--) res[i] = max(res[i], res[i + 1]); return res; } }; ``` ## **3️⃣ Deque-Based Approach (Sliding Window)** - **Maintains a deque** to track minimums efficiently. - Faster in practice for **large datasets**. ```cpp class Solution { public: vector maxOfMins(vector& arr) { int n = arr.size(); vector res(n, INT_MIN); vector left(n), right(n); deque dq; for (int i = 0; i < n; i++) { while (!dq.empty() && arr[dq.back()] >= arr[i]) dq.pop_back(); left[i] = dq.empty() ? i + 1 : i - dq.back(); dq.push_back(i); } dq.clear(); for (int i = n - 1; i >= 0; i--) { while (!dq.empty() && arr[dq.back()] > arr[i]) dq.pop_back(); right[i] = dq.empty() ? n - i : dq.back() - i; dq.push_back(i); } for (int i = 0; i < n; i++) { int len = left[i] + right[i] - 1; res[len - 1] = max(res[len - 1], arr[i]); } for (int i = n - 2; i >= 0; i--) res[i] = max(res[i], res[i + 1]); return res; } }; ``` ## **πŸ“Š Comparison of Approaches** | **Approach** | ⏱️ **Time Complexity** | πŸ—‚οΈ **Space Complexity** | ⚑ **Method** | βœ… **Pros** | ⚠️ **Cons** | | ------------------------------ | ---------------------- | ----------------------- | ------------- | ------------------------------- | --------------------------- | | **Optimized Stack** | 🟒 `O(N)` | 🟒 `O(N)` | Stack-based | Best runtime & space efficiency | None | | **Left-Right Stack** | 🟑 `O(N)` | 🟑 `O(N)` | Stack-based | Explicit left-right boundaries | Slightly more code | | **Deque-Based Sliding Window** | 🟑 `O(N)` | 🟑 `O(N)` | Deque-based | Useful for sliding windows | More complex implementation | ## **πŸ’‘ Best Choice?** - βœ… **For best efficiency:** **Stack-based (`O(N)`, `O(N)`)**. - βœ… **For explicit left-right tracking:** **Left-Right Stack (`O(N)`, `O(N)`)**. - βœ… **For sliding window problems:** **Deque-based (`O(N)`, `O(N)`)**.
## **Code (Java)** ```java class Solution { public ArrayList maxOfMins(int[] arr) { int n = arr.length; int[] res = new int[n], len = new int[n]; Stack s = new Stack<>(); for (int i = 0; i <= n; i++) { while (!s.isEmpty() && (i == n || arr[s.peek()] >= arr[i])) { int j = s.pop(); len[j] = s.isEmpty() ? i : i - s.peek() - 1; } if (i < n) s.push(i); } for (int i = 0; i < n; i++) res[len[i] - 1] = Math.max(res[len[i] - 1], arr[i]); for (int i = n - 2; i >= 0; i--) res[i] = Math.max(res[i], res[i + 1]); ArrayList ans = new ArrayList<>(); for (int r : res) ans.add(r); return ans; } } ``` ## **Code (Python)** ```python class Solution: def maxOfMins(self, arr): n = len(arr) res, length, s = [0] * n, [0] * n, [] for i in range(n + 1): while s and (i == n or arr[s[-1]] >= arr[i]): j = s.pop() length[j] = i if not s else i - s[-1] - 1 if i < n: s.append(i) for i in range(n): res[length[i] - 1] = max(res[length[i] - 1], arr[i]) for i in range(n - 2, -1, -1): res[i] = max(res[i], res[i + 1]) return res ``` ## 🎯 **Contribution and Support:** For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative! ⭐ If you find this helpful, please give this repository a star! ⭐ ---

πŸ“Visitor Count