Comparison performing contains() for ArrayList and HashSet

 

 

contains() in HashSet and ArrayList

 

Big-O notation for contains() in HashSet is O(1) which takes constant time and doesn't preserve the order. But, in ArrayList, It takes O(n) which is linear time and ensure the order of the entry. 

 

 

 

Example Code

    static int sockMerchant(int n, int[] ar) {
        Set<Integer> color = new HashSet<>();
        int pairs = 0;
 
        for(int i = 0; i < n; i++){
            if(!color.contains(ar[i])){//기존 element에 없으면 
                 color.add(ar[i]); //set에 추가
            }else{
                pairs ++; 
                color.remove(ar[i]); //단 하나의 pair만 존재하게 하기 위해 기존 index삭제
            }       
        }
        return pairs;
    }

 

contains() returns true if it is present in Set.

 

 

 

 

Reference 

https://www.baeldung.com/java-hashset-arraylist-contains-performance

https://www.hackerrank.com/challenges/sock-merchant/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup