new_connection

[mrenemy999-os]

Discussion Type

Product Feedback

Discussion Content

Given an array and window size k, return max in each window.

[github-actions[bot]]

💬 Your Product Feedback Has Been Submitted 🎉

Thank you for taking the time to share your insights with us! Your feedback is invaluable as we build a better GitHub experience for all our users.

Here's what you can expect moving forward ⏩

• Your input will be carefully reviewed and cataloged by members of our product teams. 
  • Due to the high volume of submissions, we may not always be able to provide individual responses.
  • Rest assured, your feedback will help chart our course for product improvements.
• Other users may engage with your post, sharing their own perspectives or experiences. 
• GitHub staff may reach out for further clarification or insight. 
  • We may 'Answer' your discussion if there is a current solution, workaround, or roadmap/changelog post related to the feedback.

Where to look to see what's shipping 👀

• Read the Changelog for real-time updates on the latest GitHub features, enhancements, and calls for feedback.
• Explore our Product Roadmap, which details upcoming major releases and initiatives.

What you can do in the meantime 💻

• Upvote and comment on other user feedback Discussions that resonate with you.
• Add more information at any point! Useful details include: use cases, relevant labels, desired outcomes, and any accompanying screenshots.

As a member of the GitHub community, your participation is essential. While we can't promise that every suggestion will be implemented, we want to emphasize that your feedback is instrumental in guiding our decisions and priorities.

Thank you once again for your contribution to making GitHub even better! We're grateful for your ongoing support and collaboration in shaping the future of our platform. ⭐

[vivek02122003-dot]

🧠 Idea:

Maintain max of each window of size k.

❌ Brute Force
Check max for every window
Time: O(n * k) → slow
🚀 Optimal (Deque)
💡 Why deque works?
Stores indices in decreasing order
Front = maximum of current window
Remove:
Out-of-window elements (from front)
Smaller elements (from back)

👉 Each element added & removed once

⚡ Complexity
Time: O(n) (amortized)
Space: O(k)
🔁 Heap (Alternative)
Use max heap
Time: O(n log k)
Slower due to log factor
Also need lazy deletion
🧠 Key Insight

👉 Deque is optimal because it avoids re-processing elements
👉 Maintains only useful candidates for max

🧪 Example
nums = [1,3,-1,-3,5,3,6,7], k=3
output = [3,3,5,5,6,7]

[asaddevx]

Hi @mrenemy999-os, this is the Sliding Window Maximum problem. Here are a few approaches:

Solution 1: Deque (Optimal - O(n))

from collections import deque

def max_sliding_window(nums, k):
    if not nums:
        return []
    
    result = []
    dq = deque()  # stores indices
    
    for i, num in enumerate(nums):
        # Remove indices outside current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements from back
        while dq and nums[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        # Add to result when window is fully formed
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Solution 2: Brute Force (O(n*k) — Not efficient for large arrays)

def max_sliding_window_bruteforce(nums, k):
    if not nums:
        return []
    
    result = []
    for i in range(len(nums) - k + 1):
        result.append(max(nums[i:i+k]))
    
    return result

Example

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

print(max_sliding_window(nums, k))
# Output: [3, 3, 5, 5, 6, 7]

Complexity

Approach	Time	Space
Deque	O(n)	O(k)
Brute Force	O(n*k)	O(1) extra

Explanation

The deque approach maintains elements in decreasing order. At each step:

1. Remove elements outside the window
2. Remove smaller elements (they'll never be maximum)
3. Add current element
4. The front of deque is always the maximum for current window

---