Deque-STL

Sort by

recency

|

455 Discussions

|

  • + 0 comments

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

  • + 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;
    }
    
  • + 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).

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

    }

  • + 0 comments

    include

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