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.
  1. Prepare
  2. C++
  3. STL
  4. Deque-STL
  5. Discussions

Deque-STL

Sort by

recency

|

456 Discussions

|

  • ludovic_tirtiaux
     + 0 comments

    I didn't know if using deque was mandatory, so I went oldschool with some optimizations to avoid a full n² complexity:

    void printKMax(int arr[], int n, int k){
	//Write your code here.
    int max = 0;
    int pos = 0;
    
    for (int i = 0; i < k; i++) {
        if (arr[i] > max) {
            pos = i;
            max = arr[pos];
        }
    }
    
    cout << max;
                
    for (int j = k; j < n; j++) {
        if (j - k < pos) {
            if (arr[j] > max) {
                max = arr[j];
                pos = j;
            }
        } else {
            max = 0;
            for (int i = 1; i <= k; i++) {
                if (arr[j - k + i] > max) {
                    pos = j - k + i;
                    max = arr[pos];
                }
            }
        }

        cout << " " << max;
    }
    
    cout << endl;
}

  • yashdeora98294
     + 0 comments

    Here is Deque-STL problem solution in C++ - https://programmingoneonone.com/hackerrank-deque-stl-solution-in-cpp.html

  • rojasrijo
     + 0 comments

    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.

    #include <iostream>
#include <deque> 
using namespace std;

void printKMax(int arr[], int n, int k){
    deque<int> indexes;
    --k;
    int j = 0;
    int maxNumInd = 0;
    int prevMaxNumI = 0;
    
    for(; k < n; ++k){
        for(; j <= k; ++j){
            indexes.push_back(j);
            if(prevMaxNumI == -1 || arr[prevMaxNumI] < arr[j]){
                if(arr[maxNumInd] < arr[j]){
                    prevMaxNumI = maxNumInd;
                    maxNumInd = j;
                }
                else {
                    prevMaxNumI = j;
                }
            }
        }
        cout << arr[maxNumInd] << " ";
        
        if(maxNumInd == indexes.front()){
            maxNumInd = prevMaxNumI;
        }
        if(prevMaxNumI == indexes.front()){
            prevMaxNumI = -1;
        }
        indexes.pop_front();
    }
    cout << endl;
}

int main(){
  
	int t;
	cin >> t;
	while(t>0) {
		int n,k;
    	cin >> n >> k;
    	int i;
    	int arr[n];
    	for(i=0;i<n;i++)
      		cin >> arr[i];
    	printKMax(arr, n, k);
    	t--;
  	}
  	return 0;
}

  • allenviljoen
     + 0 comments

    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).

  • kubalak_2k18
     + 0 comments

    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 << ' ';

    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';

    }