Maximum Element is a coding challenge with easy difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time and O(n) space complexity.
Problem Statement
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.
Read full details and access the challenge on Maximum Element | HackerRank
Solution
function getMax(operations) {
let stack = [];
let maxs = [];
operations.forEach((op) => {
if (op == '2') {
stack.pop(); // Delete the element present at the top of the stack.
} else if (op == '3') {
var max = Math.max(...stack);
maxs.push(max); // Print the maximum element in the stack.
} else {
stack.push(Number(op.slice(2))); // Push the element x into the stack.
}
})
return maxs;
}
Time Complexity : O(n)
Space Complexity : O(n)
The problem in itself is simple, you just have to follow the instructions, but there are 2 tricky parts for me that I will address later. I will first explain the code.
First, we define a stack (in this case, we use an array since they’re almost the same, it’ll be too long if we completely implement a stack) and also define maxs to store all the max values that we have to print for type 3.
We then loop through the operations and treat them according to their types. Do notice that we start the if from op == ‘2’ instead of ‘1’. I do this since type 1 is a string and still has to be split, so it’ll be cleaner to just put it in else.
Finally, we return the maxs array.
We’re iterating through the array once and we used Math.max() which most likely also iterates through a whole array. That means we have a nested loop, but since they’re different arrays, we have O(n*m) time complexity to be precise. In the more generic term, we have O(n) time complexity.
Since we used arrays, we have O(n) space complexity.
Note
Here’s the tricky parts if you solve it in JavaScript :
- If the type is 3, we have to print the max number in the stack. Of course we’d think it means console.log(); but it turns out that we still has to return something or it’d be runtime error. So, we store the max number into an array and return that instead.
- Prior to this solution, I kept getting time limit exceeded error, but I can’t reduce the time complexity anymore. It turns out that a minor tweak solved the issue. My mistake was that in the else clause, I used stack.push(op.slice(2)); I didn’t convert it to number at first. Turns out this makes the time limit exceeds. I assume that accessing an array of mixed types take more time since it has to convert the types, so we have to store only one type in an array for efficiency.
Overall, it’s the efficiency and details that we have to pay more attention to.
Conclusion
That’s how you can solve the Maximum Element Challenge in HackerRank.
It’s overall an easy but you have to give attention to the details and efficiency tweaks which serves as a really good practice.
If you have an approach different from mine, please do comment below!
Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions using JavaScript in this blog!
See you next post!