Search code examples
arraysalgorithmdata-structures

how to find nth minimum/maximum of all subarrays of size k (Sliding window problem)

There are so many reference to find minimum/maximum of all subarrays of size k but how to find nth maximum/minimum in best possible way. If we have to find just min/max of subarrays, then we can use deque solution with linear time complexity. But for nth min/max, I am not able to find the solution.

Note: n<=k

Example: arr = {7,1,4,20,11,17,15} n=2, k=4

output: 4,4,11,15

Solution

  • I believe the data structure you need is a little modified Binary Search Tree (BST), where each node also stores the size of it's subtree.

    Adding, removing elements or finding nth element in a BST all then becomes log(K)*. So while sliding the window over your array, you have 3 log(K) operations, assuming total N elements in given array, the overall time complexity is therefore N*log(K).

    • You need a balanced BST (Red Black Tree for example) to maintain this time complexity. If you are coming from any online judges like Codeforce or Hackerrank, remember they more often than not provide inputs that will generate degenerate BSTs.