DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 72: Python Sliding Window Maximum - Deque O(n) Solution for Efficient Max Tracking (LeetCode #239 Guide)

#challenge #python #algorithms #datastructures

Welcome to Day 72 of the #80DaysOfChallenges journey! This intermediate challenge solves the sliding window maximum problem (LeetCode #239), finding the max in every k-sized window of an array using a deque to maintain decreasing indices in O(n) time, a brilliant optimization over naive O(nk). It combines deque for monotonic queue, index tracking to remove out-of-window, and cleanup of smaller values, essential for streaming data, stock analysis, or real-time max queries. If you're advancing from basic arrays to deque-based algos or prepping for interviews with window problems, this "Python sliding window max" script demonstrates a function that's optimal, handles all cases, and easy to adapt for min or other stats.

💡 Key Takeaways from Day 72: Sliding Window Max Function

This task features a function that uses a deque to store indices of potential maxes in decreasing order, popping out-of-window or smaller values. It's a monotonic queue pattern: maintain candidates for max. We'll detail: function with deque and result list, loop for cleanup and append, and main with input parse.

1. Function Design: Deque for Indices Init

The sliding_window_max function takes nums and k, returns max list:

def sliding_window_max(nums: list[int], k: int) -> list[int]: """Return list of maximums for each sliding window.""" dq = deque() # store indices of useful elements  result = []
Enter fullscreen mode Exit fullscreen mode

Deque holds indices (not values) for window checks and value access.

2. Loop Processing: Cleanup Outdated/Smaller, Add Current

Core enumeration scans:

 for i, val in enumerate(nums): # remove indices that are out of the current window  if dq and dq[0] <= i - k: dq.popleft() # remove smaller values from the back  while dq and nums[dq[-1]] <= val: dq.pop() dq.append(i) # add current index  # window becomes valid when i >= k - 1  if i >= k - 1: result.append(nums[dq[0]]) # front holds max  return result
Enter fullscreen mode Exit fullscreen mode

Popleft if front out-of-window. Pop back if smaller than val (no future max). Append i. When window full, front dq[0] is max index, append its value. O(n) time, each index pushed/popped once.

3. Main Interactive: Space-Separated Input

Script reads nums and k, calls, prints:

raw = input("Enter numbers (space-separated): ").strip() nums = list(map(int, raw.split())) k = int(input("Enter window size k: ").strip()) output = sliding_window_max(nums, k) print(f"Sliding window maximums: {output}")
Enter fullscreen mode Exit fullscreen mode

Parses ints, prompts k, shows maxes. Simple, assumes valid.

🎯 Summary and Reflections

This sliding max uses deque for monotonic candidates, O(n) genius. It reinforced:

  • Index storage: Enables window/outdated checks.
  • Monotonic decreasing: Back pops ensure front always max.
  • Amortized O(1): Each element processed constant times.

Reflections: Core to stock spans, rain water. For min, reverse comparisons.

Advanced Alternatives: List for deque (slower pops). Segment tree O(log n) per query. Your window max? Share!

🚀 Next Steps and Resources

Day 72 mastered window maxes. In #80DaysOfChallenges? Min version? Post!

Top comments (0)