# Queries with Fixed Length

# Queries with Fixed Length

- T
thebick + 4 comments Pardon my bluntness, but what the !@#$! kind of an explanation is this for a problem?

Does it not occur to people who create these problems (and this isn't the first that I've seen with this annoyance) to provide bettern explanations of the problem and better examples?

Suppose the example is

10 5 80 100 95 105 75 1000 30 101 102 99 2 3 5 7 9

then what would the output be and why?

Further, if in the statement

min (max(a[j]) 0 <=i< n i <=j< i+d

what if i and d are both n-1? j could be > n!

Problem creators, get a hint!

lfofanov + 1 comment It's a problem of a moving window. You've got an array of n elements. You pick first d of them and calculate their max value. Then you move the window by 1 element to the right and calc max again. Out of all maxes you return a minimal value.

- PS
psoma74 + 2 comments you're showing all your incapability to understand a 2D loop and yet so rude on the creators!!! if you don't understand the problem ask nicely..

- T
thebick + 1 comment At the time of this writing, at least 7 people (by up-votes) have shared my frustration -- and that is exactly what it is. So would the creator(s) PLEASE do the HackerRank community a favor and improve the explanation of the problem? And would the HackerRank moderators PLEASE require better explanations from the creators? This is not the International Obfuscated C Code Competition.

- PS
psoma74 + 0 comments I understood the problem by just looking at the equation with out reading single line of explanation.. read the explanation only to know about input/output formats and data range.. So I thought, you don't need to use "what the !@#$! kind of an explanation" kind of expression.. instead of asking for more explanation nicely. and what kind of question is this? And what happens when the window hits the right margin? Does i stop at n-d? valid range is already specified clealry i<= j< i+d. and its obvious that i and j shall always be < n, otherwise program crash!!! so you would just use generic (j

trick/fun here is how to reuse the previous window calculation to avoid time out failures.

take care and have fun.

- AW
awalsh128 + 0 comments He is showing that he doesn't understand the problem statement and is being rude. Although the problem is stated poorly; the explaination is very terse and only one toy example is given. I don't blame his frustration, there is no need to insult his capability.

- EJ
eric3141 + 0 comments I agree this wrong specification and poor example should be fixed. If it was a human interviewer we could ask for clarification on the boundary cases. Based on the title of the problem we might

**ASSUME**it should be a fixed-length window over the entire set, and the equation is wrong. Others are very kind to answer the question but we can only hope those suggestions are from reverse-engineering the correct problem statement by submitting a passing solution. Here is my understanding, after submitting a passing solution:min ( max(a[j] ) 0 <= i <= n-d i <=j < i+d

- CB
chetanbaghel321 + 0 comments 100 100 105 1000 1000

ahmetb + 1 comment Is it just me trying to understand the problem definition?

The explanation is just one sentence and is not very helpful.

- AL
lebron_alex + 0 comments I feel the same way. They could atleast give explanation of the example.

- ML
levashovm + 3 comments Wasn't sure how to apply queues to this problem.

Solved using Sparse tables, which are nlogn in building and space requirements, but allow o(n) time per each query length. They can be used, because the array is immutable in this problem and seem much better than segment trees. Worst case result is 0.02s in C++.

In contrast, the Code from Editorial (Problem Setter's) is giving 0.17s worst case.

SergeyT + 0 comments Theoretically, you can use queue of length d. Add the next number, remove oldest one and calculate the minimum value of queue. It can be not the fastest algorithm, but with queue

lfofanov + 0 comments I used a queue (in C#) and a variable to store last max. I recalculated window's max at first time and only when the max value was dequeued.

- SV
004forever + 0 comments I got it with a stack that was holding the largest previous values with their index in descending order. When I checked a new a, I could calculate how far to the left I can go before I hit a larger value, or the end of the array, by popping the values smaller than the current value off the stack. As I popped values off the stack, I can calculate the right distance for the popped value by subtracting the current index from the popped index. Once I did those calculations, I push the current value to the stack and move to the next value.

yangxiaoyong + 1 comment for those who don't how to start.

this problem is similar to Sliding Window Max, which can be found this link: https://knaidu.gitbooks.io/problem-solving/content/stacks_and_queues/sliding_window_max.html

bsgreenb + 0 comments Sliding window implemented in Ruby:

def getMiniMax(arr, d) startWindow = 0 endWindow = d - 1 window = nil max = nil miniMax = nil until endWindow == arr.length if window.nil? window = arr[startWindow..endWindow] max = window.max miniMax = max else shifted = window.shift pushed = arr[endWindow] window.push(pushed) if pushed >= max max = pushed elsif shifted == max max = window.max if max < miniMax miniMax = max end end end startWindow +=1 endWindow += 1 end return miniMax end

madHEYsia + 0 comments Testcases are too long to check for mistakes.

fsimonazzi + 2 comments Shouldn't the spec be

`min[0<=i<N-d](max[i<=j<i+d](a[j]))`

? If i = N-1 is a valid value, as per the spec, then j can range up to N-1+d, which is out of bounds.madHEYsia + 0 comments I was searching this comment only. Nobody pointed it.

- JE
jorepstein1 + 0 comments I was trying to debug my code for a long @$$ time thinking it was some sort of circular array where you looped around the end.

The intro is indeed wrong if I understand it correctly

love1024 + 1 comment It becomes very easy using deque. You just have to

use one deque to store incoming list

another one to store maximum element at one end(Just need to take into consideration few points like how many element to pop from deque of max storage) Each query will taking O(n) time

hardeepr1 + 0 comments lolz

patelvismay92 + 1 comment Dear Friends, I have seen that for this problem, many people are focusing on 'moving window'. But as you know it can be worst if there is a new max element in each window and if there are lot of queries to process like Q > 1000,

**In this situation, the best choice would be 'Priority Queue using heap',**for this I have used two priority queues(max heap) to manage the flow and the worst case complexity in any situation falls down to*O(log n)*insertion and*O(log n)*poping out will make the things faster and easier.*O(nlogn)*#include <iostream> #include <queue> using namespace std; int main() { ios::sync_with_stdio(false); priority_queue<int> * mainheap, * secheap; int N, Q, d, globMin, start, end; cin >> N >> Q; int A[N]; for(int i = 0; i < N; i++) cin >> A[i]; while(Q-- > 0) { mainheap = new priority_queue<int>(); secheap = new priority_queue<int>(); cin >> d; for(int i = 0; i < d - 1; i++) mainheap->push(A[i]); globMin = 1000001; start = 0; end = start + d - 1; for(;end < N; start++, end++) { mainheap->push(A[end]); int m = mainheap->top(); if(m < globMin) globMin = m; secheap->push(A[start]); while(!secheap->empty() && secheap->top() == mainheap->top()) { secheap->pop(); mainheap->pop(); } } cout << globMin << endl; delete mainheap; delete secheap; } return 0; }

- G
gschoen + 0 comments For a sufficiently random array the sliding window should be more than adequate (it was for me). You would only expect to compute a new MAX once every d shifts on average.

The worst case would be if the array was sorted in descending order. You would have to recompute the new MAX after every shift which would run in O(d*n) time. The average running time would be between O(n) and O(d*n).

spas_kalaydzhiy1 + 1 comment That is my solution that passed all test cases. I am still a student and trying to improve my problem solving skill. It took me around an hour to catch all the end cases, do you think there is a better solution and do you think that is too much time for a problem like this one ?

Thanks in advance, I love the discussions in HackerRank.

private static long solve(List<Integer> numbers, int d, int N) { Queue<Integer> window = new LinkedList<>(); int min = Integer.MAX_VALUE; int max = -1; for (int i = 0; i < d; i++) { int current = numbers.get(i); window.add(current); if (current > max) max = current; } if (max < min) min = max; for (int i = 1; i <= N - d; i++) { int numToAdd = numbers.get(i + d - 1); window.add(numToAdd); if (numToAdd >= max) max = numToAdd; if (window.remove() == max) { max = Collections.max(window); } if (max < min) min = max; } return min; }

prateekkk + 0 comments Awesome logic...

- AL
lebron_alex + 0 comments Can anyone explain this problem to me? I don't really understand it.

Sort 64 Discussions, By:

Please Login in order to post a comment