Sliding Window Median
Updated
Problem statement
You are given an integer array nums and an integer k.
A window is a block of k neighboring elements of nums. The first window starts at index 0, and each next window moves one step to the right, until the last window ends at the last index. So there are nums.length - k + 1 windows.
The median of a window is found by sorting its k numbers:
- If
kis odd, the median is the middle number. - If
kis even, the median is the smaller of the two middle numbers.
Return an array with the median of every window, from the leftmost window to the rightmost.
Function
medianSlidingWindow(nums: int[], k: int) → int[]Examples
Example 1
nums = [5,1,4,2,8,3]k = 3return = [4,2,4,3]There are 6 - 3 + 1 = 4 windows. Sorted, they are:
[5,1,4]becomes[1,4,5], median4.[1,4,2]becomes[1,2,4], median2.[4,2,8]becomes[2,4,8], median4.[2,8,3]becomes[2,3,8], median3.
Example 2
nums = [2,7,4,4,1]k = 2return = [2,4,4,1]k = 2 is even, so each median is the smaller of the two numbers in the window.
The windows are [2,7], [7,4], [4,4] and [4,1], so the medians are 2, 4, 4 and 1.
Example 3
nums = [6,-2,9,0]k = 4return = [0]The only window is the whole array. Sorted, it is [-2,0,6,9]. The two middle numbers are 0 and 6, and the smaller one is 0.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^91 <= k <= nums.length
More AuxoAI Online Assessment questions
Similar questions at other companies
- Minimum Operations to Make an Array ContinuousAmazon · ONSITE INTERVIEW
- Minimum Cost to Make Array EqualWalmart · OAWalmart interview questions
- Find Array Uniqueness Median 🐈Microsoft · OAMicrosoft interview questions
- Choose One from Each Set to Minimize the RangeInMobi · OAInMobi interview questions
- Count Servers With No Requests in a Time WindowIBM · OAIBM interview questions
- Linear InterpolatorTwo Sigma · OATwo Sigma interview questions
- Maximum Requests in WindowSalesforce · OASalesforce interview questions
- Minimum Parking Roof LengthAmerican Express · OAAmerican Express interview questions
- Choose ContainersIMC Trading · OAIMC Trading interview questions
- Minimize Maximum Group DifferenceDRW · OADRW interview questions