search

ljeng / cheat-sheet

Data structures & algorithms cheat sheet
696 stars 107 forks source link

Add "nice to knows" for LCS and quickselect #1

Open jfceja opened 5 years ago

jfceja commented 5 years ago

It's nice to know that the LCS problem can be solved in O(n) space using the algorithm made by Hirschberg.

It's nice to know that quick-select can be done in O(n) worst-case (deterministic).

These "more efficient" implementations likely aren't as easy to understand/modify so I get that someone may intentionally choose the ones that you have here

leetcoder123 commented 3 years ago

My team just had to swap out the normal quick-select algorithm with the deterministic variant, so I will have to disagree with the general/unqualified claim "is actually not used in practice".