C++ implementation of Hackerrank's “Maximum Element in a Stack”

Question

I just attempted the Maximum Element Challenge on Hackerrank. This question has been posted before in swift Swift Hackerrank Maximum Element in a Stack but it has attracted low views/no answers. Moving forward, based on the requirements of finding the maximum element, I used a vector<int> as my underlying data structure as opposed to using Stack as I can't iterate through a stack. This exercise is meant to be a simple one but the time limit gets exceeded for larger input.

How do I improve the performance? Please feel free to criticise my approach as I'm new to C++ with 5 days of experience.

You have an empty sequence, and you will be given \$N\$ queries. Each query is one of these three types:

• 1 x -Push the element x into the stack
• 2 -Delete the element present at the top of the stack
• 3 -Print the maximum element in the stack

Input Format

The first line of input contains an integer, \$N\$ . The next \$N\$ lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

Constraints

• \$1 \leq N \leq 10^5 \$
• \$1 \leq x \leq 10^9 \$
• \$1 \leq \text{type} \leq 3 \$

Output Format

For each type \$3\$ query, print the maximum element in the stack on a new line.

Sample Input

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

Sample Output

26
91

#include <vector>
#include <iostream>
#include <algorithm>


//using namespace std;
bool compareValues(int i, int j) { return i<j; }

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int N;
    int queryType;
    int element;
     std::vector<int> stackOfNumbers;

    std::cin >> N;    
    for(int i =0; i < N ; i++){
        std::cin >> queryType;

        switch(queryType) {
      case 1 :
            std::cin >> element;              
            stackOfNumbers.push_back(element);
         break;
      case 2 :
            stackOfNumbers.erase(stackOfNumbers.end()-1);
            break;
      case 3 :
           std::cout<< *std::max_element(std::begin(stackOfNumbers), std::end(stackOfNumbers),compareValues ) << std::endl;
         break;
      default :
        std::cout << "Invalid queryType" << std::endl;
   }


    }
    return 0;
}

Answer 1

This is one of the questions, that is directly related to the underlying data structure. So you can actually be quite sure, that this problem is best solved with a stack.

The trick here is, that a stack hahttp://codereview.stackexchange.com/questions/146882/c-implementation-of-hackerranks-maximum-element-in-a-stacks a well defined order in which the elements are retrieved.

In that particular problem, lets say you know the current maximum of the stack. If the new element is smaller than that, you can push the maximum value instead of the actual one, as you are only interested in the maximum value of the whole stack. This is only true, as a stack guaranties, that the new element is removed before the previous maximum element. Only if it is greater you push the new element.

This has the distinct disadvantage, that you do not preserve the original data. So there are two solutions, one for tracking the maximum element and one for also preserving the data.

#include <iostream>
#include <stack>

int main () {
    size_t numQuerries;
    std::cin >> numQuerries;
    std::stack<int> maxStack;

    int inputType;
    for (size_t querry = 0; querry < numQuerries; ++querry) {
        int input;
        std::cin >> inputType;
        switch(inputType) {
        case 1:
            std::cin >> input;
            if (maxStack.empty()) {
                maxStack.push(input);
            } else {
                maxStack.push(input > maxStack.top() ? input : maxStack.top());
            }
            break;
        case 2:
            if (!maxStack.empty()) {
                maxStack.pop();
            }
            break;
        case 3:
            std::cout << maxStack.top() << "\n";
            break;
        default:
            break;
        }
    }
}

So now if you want to keep the original data you simply need two stacks

#include <iostream>
#include <stack>

int main () {
    size_t numQuerries;
    std::cin >> numQuerries;
    std::stack<int> maxStack;
    std::stack<int> dataStack;

    int inputType;
    for (size_t querry = 0; querry < numQuerries; ++querry) {
        int input;
        std::cin >> inputType;
        switch(inputType) {
        case 1:
            std::cin >> input;
            if (maxStack.empty()) {
                maxStack.push(input);
            } else {
                maxStack.push(input > maxStack.top() ? input : maxStack.top());
            }
            dataStack.push(input);
            break;
        case 2:
            if (!maxStack.empty()) {
                maxStack.pop();
                dataStack.pop();
            }
            break;
        case 3:
            std::cout << maxStack.top() << "\n";
            break;
        default:
            break;
        }
    }
}

Better Solution

So these were the intuitive solutions. However, is there some room for further improvement?. Obviously yes. The point is, that you do not need to store the same element every time because you know what the maximum is. You can circumvent this by using two stacks. One with the current maximum and one with the number of its occurences.

#include <iostream>
#include <stack>

int main () {
    size_t numQuerries;
    std::cin >> numQuerries;
    std::stack<int> maxStack;
    std::stack<size_t> occurenceStack;

    int inputType;
    for (size_t querry = 0; querry < numQuerries; ++querry) {
        int input;
        std::cin >> inputType;
        switch(inputType) {
        case 1:
            std::cin >> input;
            if (maxStack.empty()) {
                maxStack.push(input);
                occurenceStack.push(1);
            } else {
                if (input > maxStack.top()) {
                    maxStack.push(input);
                    occurenceStack.push(1);
                } else {
                    occurenceStack.top()++;
                }
            }
            break;
        case 2:
            if (!maxStack.empty()) {
                if (occurenceStack.top() > 1) {
                    occurenceStack.top()--;
                } else {
                    maxStack.pop();
                    occurenceStack.pop();
                }
            }
            break;
        case 3:
            std::cout << maxStack.top() << "\n";
            break;
        default:
            break;
        }
    }
}

Answer 2

I believe to finish this within the time limit, you need to complete each of the three operations with \$O(1)\$ time complexity.

There are a number of variations in how you do that, but nearly all of them involve keeping track of the maximum value on the stack as you build the stack, rather than searching through all the existing stack items each time you receive a query. Given that this is an online challenge, I hesitate to go into a lot more detail on this point than that.

As far as the code style goes, the most obvious point would be that your compareValues isn't really necessary--std::less<T> will be used by default, and your comparison adds nothing it doesn't already do perfectly well. In fact, std::less<T> may be superior in one respect: it's defined as a function object--a class that overloads operator() to do the comparison. You'r defining an actual function, and passing a pointer to a function. Passing a function object tends to make it easier for a compiler to generate inline code, so letting std::less<T> do the job may well improve speed at least slightly.

One more (somewhat less obvious) point is that in the process of improving efficiency to the point that you can finish within the time limit, I'm (reasonably) confident that you'll eliminate the need to traverse the stack, so you should be able to use std::stack<int>.

Answer 3

It is possible to query for the maximum element, pushing and popping in constant time. The idea is that you maintain a partial linked list whithin the stack:

max_stack.h

#pragma once
#ifndef MAX_STACK_H
#define MAX_STACK_H

#include <stdexcept>

template<typename T>
class MaxStack {
public:

    MaxStack()
    :
    top_node{nullptr},
    maximum{nullptr}
    {}

    void push(T datum)
    {
        MaxStackNode* new_node = new MaxStackNode(datum, top_node);

        if (top_node == nullptr)
        {
            maximum = new_node;
        }
        else if (maximum->datum < datum)
        {
            new_node->previousMaximum = maximum;
            maximum = new_node;
        }

        top_node = new_node;
    }

    void pop()
    {
        check_not_empty();
        MaxStackNode* ret = top_node;

        if (maximum == ret)
        {
            maximum = ret->previousMaximum;
        }

        top_node = top_node->previous;
        delete ret;
    }

    T top()
    {
        check_not_empty();
        return top_node->datum;
    }

    T max()
    {
        check_not_empty();
        return maximum->datum;
    }

private:

    struct MaxStackNode {
        T datum;
        MaxStackNode* previous;
        MaxStackNode* previousMaximum;

        MaxStackNode(T datum, MaxStackNode* previous)
        :
        datum{datum},
        previous{previous},
        previousMaximum{nullptr}
        {}
    };

    MaxStackNode* top_node;
    MaxStackNode* maximum;

    void check_not_empty()
    {
        if (top_node == nullptr)
        {
            throw std::runtime_error{"The stack is empty."};
        }
    }
};

#endif // MAX_STACK_H

What comes to your coding style, you are not quite consistent:

for(int i =0; i < N ; i++){

Please, put a single space character before (, after ) and after =. Also, remove the space character after N; like this:

for (int i = 0; i < N; i++) {

You might want to fix the indentation as well.

main.cpp

#include "max_stack.h"
#include <iostream>

using std::cout;
using std::endl;

int main() {
    int N;
    int queryType;
    int element;
    MaxStack<int> stack;

    std::cin >> N;

    for(int i = 0; i < N ; i++) {
        std::cin >> queryType;

        switch(queryType) {
            case 1 :
                std::cin >> element;
                stack.push(element);
                break;

            case 2 :
                stack.pop();
                break;

            case 3 :
                cout << stack.max() << endl;
                break;
        }
    }

    return 0;
}

Hope that helps.