🚀Day 6. Maximum of minimum for every window size 🧠

The problem can be found at the following link: Question Link

💡 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

{10}, {20}, {30}, {50}, {10}, {70}, {30}

10, 20, 30, 50, 10, 70, 30

{10, 20}, {20, 30}, {30, 50}, {50, 10}, {10, 70}, {70, 30}

10, 20, 30, 10, 10, 30

{10, 20, 30}, {20, 30, 50}, {30, 50, 10}, {50, 10, 70}, {10, 70, 30}

10, 20, 10, 10, 10

{10, 20, 30, 50}, {20, 30, 50, 10}, {30, 50, 10, 70}, {50, 10, 70, 30}

10, 10, 10, 10

{10, 20, 30, 50, 10}, {20, 30, 50, 10, 70}, {30, 50, 10, 70, 30}

10, 10, 10

{10, 20, 30, 50, 10, 70}, {20, 30, 50, 10, 70, 30}

10, 10

{10, 20, 30, 50, 10, 70, 30}

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}, {3}, {2}, {4}, {5}

1, 3, 2, 4, 5

{1, 3}, {3, 2}, {2, 4}, {4, 5}

1, 2, 2, 4

{1, 3, 2}, {3, 2, 4}, {2, 4, 5}

1, 2, 2

{1, 3, 2, 4}, {3, 2, 4, 5}

1, 2

{1, 3, 2, 4, 5}

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:

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.
Calculate the window size where each element is the minimum
- The window size for arr[i] is nextSmaller[i] - prevSmaller[i] - 1.
Store maximum values for each window size
- Use an array res[] to store the maximum of the minimums for each window size.
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++)

class Solution {
public:
    vector<int> maxOfMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> res(n), len(n);
        stack<int> 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.

class Solution {
public:
    vector<int> maxOfMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> res(n), len(n, n);
        stack<int> 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<int>();
        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.

class Solution {
public:
    vector<int> maxOfMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> res(n, INT_MIN);
        vector<int> left(n), right(n);
        deque<int> 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)

Stack-based

Best runtime & space efficiency

None

Left-Right Stack

🟡 O(N)

Stack-based

Explicit left-right boundaries

Slightly more code

Deque-Based Sliding Window

🟡 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)

class Solution {
    public ArrayList<Integer> maxOfMins(int[] arr) {
        int n = arr.length;
        int[] res = new int[n], len = new int[n];
        Stack<Integer> 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<Integer> ans = new ArrayList<>();
        for (int r : res) ans.add(r);
        return ans;
    }
}

Code (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. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

PreviousDay 5. Histogram Max Rectangular Area 🧠NextDay 7. Get Min from Stack 🧠

Last updated 6 months ago

hashtag💡 Problem Description:

hashtag🔍 Example Walkthrough:

hashtagExample 1

hashtagInput:

hashtagOutput:

hashtagExplanation:

hashtagExample 2

hashtagInput:

hashtagOutput:

hashtagExplanation:

hashtagConstraints:

hashtag🎯 My Approach:

hashtagOptimized Stack-Based Approach (O(N) Time, O(N) Space)

hashtagAlgorithm Steps:

hashtag🕒 Time and Auxiliary Space Complexity

hashtag📝 Solution Code

hashtagCode (C++)

hashtag2️⃣ Stack-Based Approach (Left-Right Boundaries)

hashtag3️⃣ Deque-Based Approach (Sliding Window)

hashtag📊 Comparison of Approaches

hashtag💡 Best Choice?

hashtagCode (Java)

hashtagCode (Python)

hashtag🎯 Contribution and Support:

hashtag📍Visitor Count

💡 Problem Description:

🔍 Example Walkthrough:

Example 1

Input:

Output:

Explanation:

Example 2

Input:

Output:

Explanation:

Constraints:

🎯 My Approach:

Optimized Stack-Based Approach (O(N) Time, O(N) Space)

Algorithm Steps:

🕒 Time and Auxiliary Space Complexity

📝 Solution Code

Code (C++)

2️⃣ Stack-Based Approach (Left-Right Boundaries)

3️⃣ Deque-Based Approach (Sliding Window)

📊 Comparison of Approaches

💡 Best Choice?

Code (Java)

Code (Python)

🎯 Contribution and Support:

📍Visitor Count