Java Sets (HashSet) running much slower than normal array lookups etc

Following are two implementations to the codechef problem https://www.codechef.com/problems/UNIONSET

The first one uses the HashSet operations of insert (add) and contains which run in O(1) while the second uses simple arrays. Both the approaches are simple bruteforce for the problem. The HashSet implementation runs much much slower than the corresponding array approach (infact leads to TLE on codechef), for which I don't understand the reason.

  1. Can someone please explain me why should these operations in the HashSet cause the program to slow so much.
  2. Does that mean hashSet internally do a lot of operations and hence even though are O(1) for these operations, they are fairly costly?

Thanks.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class unionset {
    public static void main(String[] argv) throws Exception{
        Scanner in  = new Scanner(System.in);
        int t = in.nextInt();

        while(t>0){
            int n,k;
            n = in.nextInt();
            k = in.nextInt();

            List<Set<Integer>> sets = new ArrayList<Set<Integer>>();
            int[] lens = new int[n];
            for(int i=0;i<n;i++){
                int len = in.nextInt();
                lens[i] = len;
                Set<Integer> s = new HashSet<Integer>(len);

                for(int j=1;j<=len;j++){
                    int tmp = in.nextInt();
                    s.add(tmp);
                }
                sets.add(s);
            }

            int num = 0;
            for(int i=0;i<n;i++){

                for(int j=0;j<i;j++){
                    boolean flag=true;
                    if(sets.get(i).size() + sets.get(j).size() >= k){
                        for(int x = 1;x<=k; x++){
                            if(!(sets.get(i).contains(x) || sets.get(j).contains(x))){
                                flag = false;
                                break;
                            }
                        }
                        if(flag){
                            num++;
                        }
                    }
                }
            }

            System.out.println(num);
            t--;
        }           
    }

}

vs

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class unionset {
    public static void main(String[] argv) throws Exception{
        Scanner in  = new Scanner(System.in);
        int t = in.nextInt();

        while(t>0){
            int n,k;
            n = in.nextInt();
            k = in.nextInt();
            int[][] sets =new int[n][k+1];
            int[] lens = new int[n];
            for(int i=0;i<n;i++){
                int len = in.nextInt();
                lens[i] = len;
                for(int j=1;j<=len;j++){
                    int tmp = in.nextInt();
                    sets[i][tmp] = 1;
                }
            }

            int num = 0;
            for(int i=0;i<n;i++){

                for(int j=0;j<i;j++){
                    boolean flag=true;
                    if(lens[i] + lens[j] >= k){
                        for(int x = 1;x<=k; x++){
                            if(!(sets[i][x]==1 || sets[j][x]==1)){
                                flag = false;
                                break;
                            }
                        }
                        if(flag){
                            num++;
                        }
                    }
                }
            }

            System.out.println(num);
            t--;
        }           
    }

}