Skip to main content
Code Review

Return to Answer

Added missing parenthesis after one top call
Source Link
miscco
miscco
  • 4.4k
  • 12
  • 17

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

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

The trick here is, that a stack has a well defined order in which the elements are retrieved.

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

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.

#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;
        }
    }
}
Add a better solution regarding memory consumption
Source Link
miscco
miscco
  • 4.4k
  • 12
  • 17

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

##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;
        }
    }
}
Source Link
miscco
miscco
  • 4.4k
  • 12
  • 17

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