Deque-STL

Sort by

recency

|

456 Discussions

|

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

    }