Popular posts

@mrclan Sorry, but I am not from an IT background and not sure what O(n) exactly means or how to verify it. I thought it meant that there are no unnecessary lines executed after the result is found (time optimization). You are right if you mean the .reduce (but .every has "quick exit"). The CB is really called 4 times. If this is too much, you can replace it with a for ... of-loop and break it if you found the solution. But this isn't tail optimized and requires a bit more RAM. I used a shortcut return in the .reduce to solve this.

@rahulbisht This isn't TypeScript but plain JavaScript (in version ES2015). The ... is called spread operator. This line of code splits (a copy of) the oasis array at index and put them together as a new array. You could also write: const path = oasis.slice(index).concat(oasis.slice(0, index))

@lichtjaeger Neither am I. But the way I see O(n) terminology is like this: In very-very simple/brief form, an O(n) solution would be the one where, even for the worst case scenario, the maximum number of iterations of a loop would be equal to the number of inputs(n). For eg. a loop inside a loop, would be a O(n^2) solution. Same logic applies for both time-complexities and memory complexities. So, if for 1 input, the program produces the output in 4s(assume) and consuming 4KB(assume) of memory, then if 10 inputs are fed, if the program has O(n) complexity, it would produce the output in a maximum of 40s and would consume 40KB of memory at most. Hope that gives you an idea and clarifies a bit.

I have run some test and it looks like my first attempt is better than O(n) and the solution with for ... of is even better and faster.

@lichtjaeger thanks for the clarification.