This problem can be solved in o(n) using "queue".