The two pointer approach results in a new array being created of size n. Would this not mean that the space complexity is O(n) and not O(1)?
Thank you for any help!
Hello @Jacotcher
In space complexity analysis, we typically focus on the additional space used for data structures or variables that are created during the execution of a function and not on the space required to store the function’s return value. Therefore, the space complexity of the SortedSquares function is primarily determined by the space used for the result vector and the few extra variables used for intermediate calculations. The space complexity can be summarized as follows:
- O(n) for the result vector, which stores the squared values.
- O(1) for individual integer variables (left, right, i, square) used for tracking and calculations.
So, in this context, we’re not counting the space used to store the function’s return value in the space complexity analysis.
I hope this will help.
Happy learning
1 Like
This was very useful, I did not understand this before. Thank you!
Course: Coderust: Hacking the Coding Interview - Learn Interactively
Lesson: https://www.educative.io/courses/coderust-hacking-the-coding-interview/shuffle-an-array
1 Like
For anyone else reading this, I saw this summarised in another course too which helped my understanding as to why we don’t count the space to store the return value:
When reporting the space complexity of a solution, we do not count the space taken in memory by the input data or the output data. When comparing two correct solutions to a problem, the space taken up by the input and the output data will be precisely the same. Thus, counting this space does not serve the purpose of determining which solution is more space efficient.
Course: Coderust: Hacking the Coding Interview - Learn Interactively
Lesson: https://www.educative.io/courses/coderust-hacking-the-coding-interview/shuffle-an-array
Hello @Jacotcher
That’s an excellent summary! It indeed encapsulates an essential aspect of space complexity analysis. The focus on space complexity is primarily on the additional space used by the algorithm itself—such as extra variables, data structures, or any temporary space that scales with the problem size—rather than considering the space taken by the input or output data. Comparing solutions based on their additional space utilization helps understand which algorithm is more space-efficient for a given problem.
Thank you for sharing this.
Happy learning