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 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.
The time limit forced me to take into consideration when the max value left the sliding window and only look for the new max whenever it was popped AND whenever the incoming value was not >= to that max (otherwise the new value would just replace the popped old max).
void printKMax(int arr[], int n, int k) {
std::deque subArr;
int shift = 0;
for(int a=0;a < k; ++a)
subArr.push_back(arr[a]);
// Get actual max value (iterator)
auto maxval = std::max_element(subArr.begin(), subArr.end(), [](int a, int b){return a < b;});
// Get max value position
int pos = maxval - subArr.begin();
cout << *maxval << ' ';
while(shift + k < n){
subArr.pop_front(); // Remove old value
subArr.push_back(arr[shift + k]); // Add new value
pos--; // Move max value position back
// If new value is greater than actual max
if(subArr.back() > *maxval){
pos = subArr.size() - 1;
maxval = subArr.begin() + pos;
}
else if(pos < 0){ // If not and old value ran out of scope find new max value
maxval = std::max_element(subArr.begin(), subArr.end(), [](int a, int b){return a < b;});
pos = maxval - subArr.begin();
}
// Print new max value
cout << *maxval << ' ';
shift++;
}
cout << '\n';
using namespace std;
void print(vector &arr, int k) {
deque dq;
int n = arr.size();
for (int i = 0; i < n; ++i) {
if (!dq.empty() && dq.front() == i - k)
dq.pop_front();
while (!dq.empty() && arr[dq.back()] < arr[i])
dq.pop_back();
dq.push_back(i);
if (i >= k - 1)
cout << arr[dq.front()] << " ";
}
cout << '\n';
}
int main()
{
// freopen("input.inp", "r", stdin);
// freopen("output.out", "w", stdout);
int t; cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector arr(n);
for (int i = 0; i < n; ++i)
cin >> arr[i];
print(arr, k);
}
return 0;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
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.
The time limit forced me to take into consideration when the max value left the sliding window and only look for the new max whenever it was popped AND whenever the incoming value was not >= to that max (otherwise the new value would just replace the popped old max).
A bit straightforward which passes all tests:
void printKMax(int arr[], int n, int k) { std::deque subArr; int shift = 0; for(int a=0;a < k; ++a) subArr.push_back(arr[a]); // Get actual max value (iterator) auto maxval = std::max_element(subArr.begin(), subArr.end(), [](int a, int b){return a < b;}); // Get max value position int pos = maxval - subArr.begin(); cout << *maxval << ' ';
}
include
using namespace std; void print(vector &arr, int k) { deque dq; int n = arr.size();
}
int main() { // freopen("input.inp", "r", stdin); // freopen("output.out", "w", stdout); int t; cin >> t; while (t--) { int n, k; cin >> n >> k; vector arr(n); for (int i = 0; i < n; ++i) cin >> arr[i]; print(arr, k); } return 0; }