We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I think to force deque use there should be a test for the worst case (decreasing array). Using quick-bench.com you can see that although with a random array the int algorithm is between roughly 1.3x and 6x faster than the deque implementation, when the values in the array are always decreasing, the complexity quickly becomes closer to 0(n* k) in the int implementation. Meaning that the bigger the k the slower the code relative to the deque implementation and in my test up to 270x slower for a decreasing array from 4999 to 0 and a k of 2000. If you want to play around here's the benchmark I used https://github.com/cegranger/statquest-cpp/blob/main/benchmarks/bench_moving_max.cpp
I didn't know if using deque was mandatory, so I went oldschool with some optimizations to avoid a full n² complexity:
voidprintKMax(intarr[],intn,intk){//Write your code here.intmax=0;intpos=0;for(inti=0;i<k;i++){if(arr[i]>max){pos=i;max=arr[pos];}}cout<<max;for(intj=k;j<n;j++){if(j-k<pos){if(arr[j]>max){max=arr[j];pos=j;}}else{max=0;for(inti=1;i<=k;i++){if(arr[j-k+i]>max){pos=j-k+i;max=arr[pos];}}}cout<<" "<<max;}cout<<endl;}
I don't understand why my code is not getting a correct answer
As far as I'm aware, even with some custom inputs based on the test cases:
I'm getting the corect answer. However, for some reason I am not getting correct test cases.
Hi everyone!
I wanted to share my well-commented solution for the Sliding Window Maximum problem. I explain the deque logic and how to achieve O(n) complexity.
Check it out on GitHub: https://github.com/habibma/SlidingWindowMaximum
I think to force deque use there should be a test for the worst case (decreasing array). Using quick-bench.com you can see that although with a random array the int algorithm is between roughly 1.3x and 6x faster than the deque implementation, when the values in the array are always decreasing, the complexity quickly becomes closer to 0(n* k) in the int implementation. Meaning that the bigger the k the slower the code relative to the deque implementation and in my test up to 270x slower for a decreasing array from 4999 to 0 and a k of 2000. If you want to play around here's the benchmark I used https://github.com/cegranger/statquest-cpp/blob/main/benchmarks/bench_moving_max.cpp
I didn't know if using deque was mandatory, so I went oldschool with some optimizations to avoid a full n² complexity:
Here is Deque-STL problem solution in C++ - https://programmingoneonone.com/hackerrank-deque-stl-solution-in-cpp.html
I don't understand why my code is not getting a correct answer
As far as I'm aware, even with some custom inputs based on the test cases: I'm getting the corect answer. However, for some reason I am not getting correct test cases.