educative.io

Space complexity of Counting Bits

Courses
,
#1

The lesson says the provided solution has a space complexity of O(n). Since we exclude the output space from the space complexity, is the space comp due to initializing an array of length n at the start, which is considered auxiliary until the final results are input? If so, then could we reduce the space comp to O(1) by initializing an empty list and appending each addition?

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-python/solution-counting-bits

1 Like
#2

Hi @Isaac_Haseley,

You’re correct in saying that we don’t count the auxiliary space occupied by the output data structures. Regardless of whether we initialize an empty list and append or initialize a list with length n + 1, the space complexity will be O(1). Both methods use constant space irrespective of input size.

We have fixed the space complexity and hope you continue to enjoy your learning experience with us at Educative!

Happy learning!

1 Like