Timeline for Arrays. Find row with most 1's, in O(n)
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 19 at 16:14 | comment | added | Benjamin Kuykendall | Love how concrete this pseudocode is, but I needed a verbal description. The algorithm will "walk down" the matrix like a staircase (perhaps with uneven steps). Start at the top left. For each row, if the current location contains a 1, walk forward until you hit the first 0. Then walk down and repeat from where you left off. At the end of the process, the last row where you saw a 1 is going to be the answer. This description also helps with the runtime analysis: in total you take at most n steps forward and n steps down. To argue correctness, it might help to draw a picture. | |
| Jun 19 at 0:19 | history | edited | EnEm | CC BY-SA 4.0 |
Change variable name to avoid confusion
|
| Jun 18 at 6:19 | vote | accept | GeekGuy | ||
| Jun 18 at 4:27 | history | answered | EnEm | CC BY-SA 4.0 |