(Java) Does boolean array use constant O(1) space?


  • -1
    H

    Since it's a hard question and my solution is so simple, does boolean[n] use O(n) space or O(1) space?

    public int findDuplicate(int[] nums){
        boolean[] arr = new boolean[nums.length+1];
        for(int i=0;i<nums.length;i++){
            if(arr[nums[i]]){
                return nums[i];
            }else{
                arr[nums[i]]=true;
            }
        }
        return 0;
    }

  • 0
    S

    I would say a boolean array is O(n) because as the size of the input array grows so does the size of your boolean array


  • 1
    B

    No, the boolean array is not constant, unfortunately. As SimplyAhmazing stated, it is O(n). Essentially any time that you find yourself doing something like new boolean[nums.length] where the array or data structure you are creating depends on the size of the input, it will not be constant space. This is independent of the amount of space the item in the array takes up. Since you are coupling the creation with the size of the input, it cannot be O(1).

    Hope that helps!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.