3 ms·

The "Boyer–Moore majority vote algorithm" is also very neat. It's the optimal solution to https://leetcode.com/problems/majority-element/ https://leetcode.com/

The "Boyer–Moore majority vote algorithm" is also very neat. It's the optimal solution to https://leetcode.com/problems/majority-element/ https://leetcode.com/problems/majority-element/ – as in it's required to solve the problem in linear time and in O(1) space.

lofi_lory 5y ago
Does it have practical applications tho? Last I read about it, I figured it was just neat. (On the other hand it pollutes the namespace as a "BMA" search term collision XD)
- healeycodes 5y ago
  These days? Perhaps some niche area. From the paper's abstract: > the algorithm uses storage in a way that permits an efficient use of magnetic tape
tzs 5y ago
I don't know if this applies to that problem, but something worth noting about Leetcode O(1) space problems: the input is mutable and does not count toward your space usage. I like to use Leetcode hard or medium problems as interesting puzzles to work on in my head when I've got some time to kill, such as waiting in line for some service or lying in bed trying to fall asleep. One of those problems was given an input array of integers, find the smallest positive integer that is not in the array. They wanted this in O(N) time and O(1) space. I spent something like two months trying to solve that. I even spent a fair bit of that time trying to prove that it could not be done, hoping that maybe if I could not prove it impossible I might get some insights from why I could not do so that would help me figure out how to do it. That "try to disprove it to gain insight" approach didn't work, because my attempts to disprove it actually almost convinced me that it was in fact impossible. I say almost, because my argument using Turing machines actually seemed like it wa right, but it has been around 40 years since I last studied or used Turing machines, and so I wasn't quite sure that I wasn't missing something. I finally gave up, and took a quick glance at a published solution, trying to just see enough to get unstuck. The first thing I saw was that they were writing to the input array. As soon as I saw that you can overwrite the input, and so by O(1) space what they really mean is O(1) additional space besides this array of length N that we give you, the solution came quickly.

lofi_lory 5y ago

Does it have practical applications tho? Last I read about it, I figured it was just neat. (On the other hand it pollutes the namespace as a "BMA" search term collision XD)

healeycodes 5y ago
These days? Perhaps some niche area. From the paper's abstract: > the algorithm uses storage in a way that permits an efficient use of magnetic tape

tzs 5y ago

I don't know if this applies to that problem, but something worth noting about Leetcode O(1) space problems: the input is mutable and does not count toward your space usage. I like to use Leetcode hard or medium problems as interesting puzzles to work on in my head when I've got some time to kill, such as waiting in line for some service or lying in bed trying to fall asleep. One of those problems was given an input array of integers, find the smallest positive integer that is not in the array. They wanted this in O(N) time and O(1) space. I spent something like two months trying to solve that. I even spent a fair bit of that time trying to prove that it could not be done, hoping that maybe if I could not prove it impossible I might get some insights from why I could not do so that would help me figure out how to do it. That "try to disprove it to gain insight" approach didn't work, because my attempts to disprove it actually almost convinced me that it was in fact impossible. I say almost, because my argument using Turing machines actually seemed like it wa right, but it has been around 40 years since I last studied or used Turing machines, and so I wasn't quite sure that I wasn't missing something. I finally gave up, and took a quick glance at a published solution, trying to just see enough to get unstuck. The first thing I saw was that they were writing to the input array. As soon as I saw that you can overwrite the input, and so by O(1) space what they really mean is O(1) additional space besides this array of length N that we give you, the solution came quickly.