Back to course home
0% completed
Vote For New Content
For the python solution, at the end of each level we run "result.append(list(cur...
Richard Yuan
Aug 22, 2022
For the python solution, at the end of each level we run "result.append(list(currentLevel))" to convert the deque into a list. Wouldn't this effectively make the time complexity O(n^2) in the worst case since we have to copy the elements of the deque into a list?
Similar to the DFS problem "All Paths for a Sum" where the time complexity came out to O(n^2) or O(nlogn) unless I am missing something.
0
0
Comments
Comments
Design Gurus3 years ago
Not exactly. Every element is pushed to the queue only once, and we convert the queue to a list for each level once.
Overall, each element becomes part of the queue and the list only once for ALL the iterations of while/for loops.
O(n^2) is possible only when, in the ...
On this page