Space complexity in two sums

Question

I wrote a piece of code of two sums:

public static int[] twoSums0(int[] nums, int target){

    for(int i=0;i<nums.length;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i] == target-nums[j]){
                return new int[]{i,j};
            }
        }
    }
    throw new IllegalArgumentException("No solution");
}

I just want to know, why the space complexity is O(1)? And why when we use a hashmap, it becomes O(n)?

The time complexity is very easy to understand but I don't get the space complexity.

Answer 1

To calculate space complexity, you have to analyze the asymptotic size of all the objects and primitives created by your method. You don't include the size of the input.

This method creates at most a single array of 2 elements (in additional to the 2 primitives used for the indices of the loops). Therefore it requires constant space (i.e. O(1) space complexity).

If you would use a HashMap to improve the time complexity of this method, I'm assuming you'll add all the elements of the input array to that HashMap, which will require O(n) space.