Problem: [problem statement with input size limits].
Give 2 approaches: a simple one and an efficient one. For each: idea, pseudocode, time and space complexity, and when it breaks. Then implement the efficient one in [language] with tests for edge cases.