HackerRank (Stacks) - Maximum element solution gets a timeout

Question

Apparently my solution is really slow. Can someone help me with why my solution passes a little over half the test cases for this question?

Here is my solution:

function processData(input) {
 //Enter your code here
 let inputArr = input.split("\n");
 let newArr = inputArr.map(x => x.split(" ").map(p => parseInt(p, 10)));
 let stack = [];
 let len = newArr.length;
 for (let i = 0; i < len; i++){
 if (newArr[i][0] === 1){
 stack.push(newArr[i][1]);
 } else if (newArr[i][0] === 2){
 stack.pop();
 } else if (newArr[i][0] === 3){
 console.log(stack.reduce(maxNum));
 }
 }
}
let maxNum = (acc, curr) => Math.max(acc, curr);

• Raimund Krämer: Creating a new function that just delegates to Math.max slow things down. Is there a reason not to use Math.max as parameter of reduce?
• Raimund Krämer: Also it might be a good idea not to have to reduce it at all at the end, and instead keep the current maximum value in a variable.
• Conor Mancone: @D.Everhard You can't pass Math.max directly to reduce because it has a different calling sequence. See the examples here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
• Marc Rohloff: Your solution needs to take into account that the first line is the number of 'commands'

Answer 1

Performance review

These code challenges have tight constraints (a very good thing in my view) so you you must be aware of the actual load on the CPU for every line you write.

Also these code challenges run on V8, and sometimes that version is not up to date. It helps to have some knowledge of some of V8's oddities, past and present.

Looking at your code.

The first problem is the parsing of the input. Using Array.map is convenient but slow.

Rather than parse the input before you process it, combine the processing with the parsing. This will save a significant amount of time.

Don't slice arrays if you don't need to, there are better ways to access data in arrays if speed is important.

Same with Array.reduced, there is no need for it in this example.

Use Number("42") to convert to number rather than parseInt as it is quicker. There really is only one use for parseInt and that is to convert numbers from bases other than 10.

The commands (first value per line after first line) are not used as numbers, you don't need to convert them.

RegExps are very quick compared to loops, iterators, and many of the array functions. Its well worth learning RegExps to get the most out of your code.

You can use a RegExp to split the input. input.split(/[^0-9]/g); will split on each non digit and a zillion times faster than using String.split and array.map

Function calls add overhead that is not related to the algorithm. Avoid needless function calls if you can. That does not mean flatten out your code that means dont create indirect function calls if there is no need.

// completely redundant and only adds overhead.
let maxNum = (acc, curr) => Math.max(acc, curr);

V8 specific

Watch out when using let. Some of these code challenge sites are still running on older versions of V8 and let used to add a big overhead especially inside loops.

Careful with indexing indexing. Some JS engines are not as efficient as others when it comes to array indexing and property referencing.

For example V8 will be slower when you reference an array elements using multiple indexes

var c = 0;
for(var i = 0; i < 10; i ++){
 for(var j = 0; j < 100; j ++){
 c += myArray[i][j];
 }
}

You can improve the performance by staying as close to the required index as possible.

var c = 0;
for(var i = 0; i < 10; i ++){
 const innerArray = myArray[i]; // only need to calculate i index 10 times
 // rather than 1000 times.
 
 for(var j = 0; j < 100; j ++){
 c += innerArray[j];
 }
}

Note V8 has made some amazing improvements over the past months. It always pays to test performance when in doubt.

Rewrite

The following will be about the fastest possible. the only performance increase you could get is using a typed array and implementing your own stack (which is worth the effort for larger array sizes)

/* Commands first item is command count
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. */
function processData(data) {
 const stack = [];
 const input = data.split(/[^0-9]/g); // RegExp to split the data
 var max, i, inPos = 0; // inPos is data read pos
 var count = Number(input[inPos++]); // You could get away without Number 
 // but using a number type is faster 
 while (count--) { //simplify the loop
 const command = input[inPos++]; // The command is not used as number
 if (command === "1") { // compare to the string not number as its quicker
 // in this situation
 // Older V8 the following is the fastest way to push to an array 
 stack[stack.length] = Number(input[inPos++]);
 } else if(command === "2") {
 stack.pop();
 } else {
 // for and while loops are faster than array methods.
 i = stack.length; 
 // you dont know if length could be zero
 // but it says nothing about what to do for no value so I am
 // assuming it safe to get max from the top.
 max = stack[--i];
 while (i--) {
 // there may be a slight advantage to using the next line
 // but cant remember how much to, indexing stack twice may 
 // swing the balance
 // max = max < stack[i] ? stack[i] : max;
 // over calling Math.max 
 max = Math.max(max, stack[i]);
 }
 console.log(max);
 }
 }
}

I find expanded and commented code hard to read so below is a neater version in my prefered style.

function processData(data) {
 const stack = [];
 const input = data.split(/[^0-9]/g);
 var count, max, i, inPos = 0;
 count = Number(input[inPos++]); 
 while (count--) { 
 const command = input[inPos++];
 if (command === "1") { stack[stack.length] = Number(input[inPos++]) }
 else if (command === "2") { stack.pop() }
 else {
 i = stack.length; 
 max = stack[--i];
 while (i--) { max = Math.max(max, stack[i]) }
 console.log(max);
 }
 }
}

• Kruga: maxNum is not redundant. If it's called with more than 2 arguments, the rest gets ignored. The callback in Array.reduce gets passed 4 arguments, so you need to get rid of the last 2 to use Math.max. Pretty confusing way of doing it though. By the way, is there any drawback of just using Math.max(...stack) instead?
• Blindman67: @Kruga spread operator not available on all versions of node.js. Don't know about OP's test site but LeetCode still running non ES6 node.js. Alternative Math.max.apply(null,array) not as fast as while loop. though I had no way to test is max = v < max ? v : max would have been quicker than max = Math.max(max,v); in this example.
• Dream_Cap: The else statement is still a bit confusing to me. I hope this kind of optimization stuff will come to me as I practice more hackerrank problems. I'm confused about the nested while loop loop. I see that is calculates the max value and that the while loop eventually counts to 0 for the false condition, but I don't know what the max var is doing and how it is utilized against stack[i].
• Blindman67: @Dream_Cap This code is written for best performance (well close to best) so the loops are used because they are faster than the array methods. The inner loop ( else { defaults command "3" ) checks all items on the stack to find the max value. I holds the stack size and max is set to the first entry then the loop checks each item in turn and sets max to the items value if it is geater. After the loop the result is printed.. In ES6 you can do the same with a single line console.log(Math.max(...stack)) But I don't know what version the server is running so I gave the safe fast option.

Answer 2

Notes

Declaring some of your variables as const can protect you against erroneous reassignment or rebinding, as any assignment to const variables will throw a TypeError at runtime instead of silently continuing execution.

Instead of parseInt(str) I recommend using the unary plus operator +str which is "the fastest and preferred way of converting something into a number" according to MDN.

Parsing

I like your separation of input parsing and the actual program logic. However, you create a lot of temporary copies by first splitting and then mapping the array. If you like, you can use iterators or generator functions to parse input with only constant additional required space:

function* operations(input) { ... yield [operator, value] ... }
for (const [operator, value] of operations(input)) { ... }

In this case however, as you are striving for optimal performance, even generator functions are slow compared to directly processing the raw input.

Robustness

Your code is not very robust. Your handling of invalid queries is inconsistent. For invalid queries 2, 2, 1 5, 3 you return 5. For invalid queries 2, 1 5, 2, 3 you throw a TypeError: Reduce of empty array with no initial value. I recommend to simply ignore the request of deleting the top element of an empty stack. This would be consistent with [].pop(). I also recommend to define the maximum of an empty stack as -Infinity. This would be consistent with Math.max().

Correctness

Your code is not correct. For example, for queries 3, 1 10, 1 20, 3 you throw a TypeError: Reduce of empty array with no initial value. This is because you process the first line as any other line and ignore the fact that it contains the number of operations.

Runtime Complexity

The worst-case runtime complexity of your code is quadratic. Let's assume you are only given push and print queries in alternating order. You loop over all N queries. For each of the N/2 print queries, you inspect all stack elements to find the maximum. Since the number of stack elements corresponds to the number of push queries N/2, the average number of elements in the stack is N/4. Unfortunately, the resulting N/2 ×ばつ N/4 = N2/8 is quadratic. A linear worst-case runtime complexity is possible. Instead of pushing the incoming element onto the stack, you simply push the current maximum on the stack. So you can reply to a print query by simply inspecting the top of the stack.

Applying the aforementioned changes to your code, we get the following implementation with linear runtime complexity:

function processData(input) {
 const lines = input.split('\n');
 const stack = [];
 let max = -Infinity;
 for (let i = 1; i < lines.length; ++i) {
 const operator = lines[i][0];
 switch (operator) {
 case '1':
 stack.push(max);
 const value = +lines[i].substring(2);
 if (value > max) max = value;
 break;
 case '2':
 if (stack.length > 0) max = stack.pop();
 break;
 case '3':
 console.log(max);
 break;
 }
 }
}

Optimizations

Blindman67 has already pointed out that regular expressions speed up parsing by a huge margin. But we would still copy the input which results in a linear additional space requirement. By stepping through the raw input via input.indexOf and input.substring and using the fact that two of the three queries are of fixed length, we can reduce the additionally needed memory to a minimum and thereby speed up parsing even more. We also reduce the overall number of push and pop operations on the stack by a simple run length encoding - i.e. by keeping track of the last maximum in one stack and its repetitions in another stack:

function processData(input) {
 const maxima = [];
 const counts = [];
 let max = -Infinity;
 let count = 0;
 let pos = input.indexOf('\n') + 1;
 while (pos < input.length) {
 switch (input[pos]) {
 case '1':
 let next = input.indexOf('\n', pos + 3);
 if (next < 0) next = input.length;
 const value = +input.substring(pos + 2, next);
 if (value > max) {
 maxima.push(max);
 counts.push(count)
 max = value;
 count = 1;
 } else {
 count++;
 }
 pos = next + 1;
 break;
 case '2':
 if (--count === 0) {
 count = counts.pop();
 max = maxima.pop();
 }
 pos += 2;
 break;
 case '3':
 console.log(max);
 pos += 2;
 break;
 }
 }
}

Performance Test on V8 6.2

Below are average runtimes (in ms) measured after warmup (1000 preliminary calls).

Best case - input queries 1 10, 3, 2 repeated

 | 100 1000 10000 100000
-----------|-----------------------------
Dream_Cap | 0.0487 0.393 3.76 81.87
Blindman67 | 0.0085 0.067 0.73 15.62
le_m | 0.0072 0.040 0.43 3.95

Since the best-case runtime complexity did not change, we only see minor performance improvements. The runtime is dominated by parsing speed.

Worst case - input queries 1 10, 1 20, 3, 2 repeated

 | 100 1000 10000 100000
-----------|-----------------------------
Dream_Cap | 0.0685 1.349 91.97 8622.32
Blindman67 | 0.0131 0.130 4.66 386.04
le_m | 0.0096 0.051 0.43 5.89

Since the worst-case runtime complexity improved from quadratic to linear, we see major performance improvements. The runtime is dominated by read query maximum retrieval speed.

• Dream_Cap: Is there a performance tool you recommend for measuring solution performance? Also, any algorithm courses you recommend? I am really bad at coding challenges, and would like to get better(I want to get a front end dev position once I get back to the US)
• le_m: @Dream_Cap Performance: have a look at benchmarkjs.com - Algorithms: read some chapters of the standard reference mitpress.mit.edu/books/introduction-algorithms - JavaScript niceties: Check out 2ality.com

Answer 3

Here is a small change that may help. Constantly pushing and popping with an array can be resource intensive, depending upon the underlying implementation. So what I have done is made a stack that only grows. It uses a "pointer" to keep track of where in the list the top of the stack is. It grows the stack as needed, but when an element is "popped" it just moves the pointer backwards. When it comes time to calculate the max, it simply takes the max of the list up to the pointer.

This should give you much better performance when there are more pushes and pops than outputs. If there are lots of outputs though, it may not help. If this doesn't do it the next step would be to track the max so that you don't have to iterate over the array with a reduce to get the max. However, I suspect that the code to do that will be quite complicated. The issue is that you have to track not just the max, but the position of the max, and of all past max's, to account for some difficult examples. For instance, imagine your state is:

[1, 2, 3, 4, 5, 6, 7]

And then your instructions say to pop 3 and output the max. You have to keep track of not just the current max, but track the max in such a way that you can figure out what the new max is after an arbitrary number of pops. Tricky. So I vote for starting with one simplification, and seeing how far that gets you. Note, this is untested. I've just modified your stuff:

function processData(input) {
 //Enter your code here
 let inputArr = input.split("\n");
 let newArr = inputArr.map(x => x.split(" ").map(p => parseInt(p, 10)));
 let stack = [];
 let len = newArr.length;
 let index = 0;
 let maxValue = -1;
 let lastMax = -1;
 for (let i = 0; i < len; i++){
 if (newArr[i][0] === 1){
 index += 1;
 stack[index] = newArr[i][1];
 } else if (newArr[i][0] === 2){
 index -= 1;
 } else if (newArr[i][0] === 3){
 console.log(stack.slice(0,index+1).reduce(maxNum));
 }
 }
}
let maxNum = (acc, curr) => Math.max(acc, curr);

Edit to add

You may even want to initialize your array to some largish size. This will hurt performance on early tests with just a few instructions, but you will still pass those. However, it may help the tests on larger array sizes, which are the ones where you are at risk of timing out (I think: it does depend on some details of how javascript implements arrays).

let stack = new Array(1000);