Timeline for How can you find all unbalanced parens in a string in linear time with constant memory?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 4, 2019 at 12:32 | comment | added | Gilles 'SO- stop being evil' | @Édouard You have to put the output somewhere. If you define the output as memory locations, then you shouldn't count those locations as part of the memory usage of the program. (Remember that these are locations that the program isn't allowed to read from.) If you define the output as a special instruction, then it doesn't occupy any memory. | |
| Feb 4, 2019 at 11:51 | comment | added | Édouard | @Gilles Wouldn't that require 0(n) memory? | |
| Feb 1, 2019 at 13:01 | comment | added | Gilles 'SO- stop being evil' | @Édouard You could write the output to certain designated memory cells (e.g. use the even-numbered memory cells for computation and the odd-numbered ones as output, optionally with the constraint of not reading from output cells), or use a separate output instruction. Either way outputting one index takes one unit of time. | |
| Feb 1, 2019 at 12:39 | comment | added | Édouard | @Gilles I don't know much about the RAM model, and that's probably the source of my confusion. What do you mean by "outputing" an index? Writing in a particular place in memory? Do you the index as a single integer to write it in memopry (in which case, how and how how costly is it)? Or does the RAM model include an "output" instruction and we leave it at that? | |
| Jan 31, 2019 at 7:45 | comment | added | Gilles 'SO- stop being evil' | @Édouard In the RAM model, it takes $O(1)$ memory to store the current index and $O(1)$ time to increment after processing one character of the input. The problem statement doesn't constrain the output format, so the order in which the indices are reported is whatever is convenient. | |
| Jan 30, 2019 at 23:23 | comment | added | Édouard | While I really like this answer, something keeps bothering me about it. That something is "I somehow need to remember the position And I think the issue I have with it is : how do you "output the current index" without consuming memory (or a quite specific context where your outputs are consumed in such a way that the order w-of your outputs doesn’t matter). | |
| Jan 19, 2019 at 2:52 | comment | added | orlp |
@MooingDuck That doesn't work. E.g. (().
|
|
| Jan 19, 2019 at 1:18 | comment | added | Mooing Duck | For the last step, you don't have to run it in reverse, you can simply mark the last N "(" as mismatches. | |
| Jan 19, 2019 at 1:15 | comment | added | Mooing Duck | "If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis." Not quite. Linear time doesn't mean single pass. You can do a second pass to find any brackets in the mismatched side and mark them. | |
| Jan 18, 2019 at 19:22 | vote | accept | temporary_user_name | ||
| Jan 18, 2019 at 17:19 | comment | added | temporary_user_name | Oh very good Gilles, very well explained. I understand perfectly now. It has been quite a few years since I got an answer from you on one of my questions. | |
| Jan 18, 2019 at 8:43 | history | answered | Gilles 'SO- stop being evil' | CC BY-SA 4.0 |