Блог пользователя Destopia

Автор Destopia, история, 23 месяца назад, По-английски

I've solved a lot of two pointers problems, I found that every problem I solved with two pointers is also solvable with binary search, is that true?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
23 месяца назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

Two pointers is a very generic technique, and I am sure there are problems you can solve using two pointers but not binary search. For example, Mo's algorithm is in some sense an application of two pointers, but I don't see how someone could use binary search in it.

»
23 месяца назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

It isn't true, but the answer to that question isnt really thst important. Sets for example can solve everything a priority queue can, but people still use priority queues for a lot of problems.

Sometimes using binary search goes over the time limit, sometimes you would need an extra structure to use binary search, sometimes two pointers is more convinient to code.

Learn both and use them when necessary (even though i would say that binary search is more important)

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's your binary search alternative to Manacher's Algorithm for finding the longest palindromic substring?

  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Forward and backward string hashes and binary search for longest length which they are equal at every position. Easier than Manacher's and also easily linear time if you just don't binary search and rather do a sliding window that you expand when possible at the cost of having some probability of failure

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Most of them, because binary search is also application of two pointers, i also used two pointers, l and r