DEV Community


Discussion on: Daily Challenge #304 - Consecutive Letters

bugb profile image

It's always nice to avoid a second iteration

We also have space complexity

  • if 2 loops O(2n) and the space is O(1) then it still good to give a try
  • if you have only one loop but the space is O(n) or O(n^2), you should consider to use then ;)
willsmart profile image

You're right, space is part of the equation too. It's all about what tradeoffs you're happy to make.

In this case, we're checking for duplicates in the string so we're either storing a memo hash (O(n) on space) or iterating over the pairs of elements (O(n^2) on time).
This one is O(n) on space and time, but you could defn make a fn that was O(1) on space if you were ok with O(n^2) on time.

(O(n) == O(2n) btw. The notation includes a multiplier to cover differences in the base case. So the top function up there where [...s] implicitly loops through the string before even hitting the every, actually has the same complexity as the lower function that is genuinely just one loop.)