ArrayList vs HashSet

Question

I was working on this problem https://cses.fi/problemset/task/1660, and here's my code:

import java.util.*;
public class SubarraySumsI {

public static void main(String[] args) {
    Scanner in = new Scanner (System.in);
    int N = in.nextInt();
    int X = in.nextInt();
    
    ArrayList <Long> prefix = new ArrayList <Long> ();
    int count = 0;
    prefix.add(0l);
    long prefixsum = 0;
    for (int a = 0; a < N; a++) {
        prefixsum += in.nextInt();
        prefix.add(prefixsum);
        
        if (prefix.contains(prefixsum - X)) {
            count++;
        }
    }
    
    System.out.println(count);
    in.close();
  }
}

I noticed that on a lot of the test cases, it was really slow. However, if I just change prefix from an ArrayList to a HashSet, it suddenly becomes a lot faster.

I'm not that experienced with using Sets and HashSets yet, so can someone explain what the difference is between ArrayList and HashSet?

score 0 · Answer 1 · answered Feb 13 '22 at 03:58

0

You can read in here the difference between Set and Array

https://www.geeksforgeeks.org/difference-between-list-set-and-map-in-java/

answered Feb 13 '22 at 03:58

roig

1
1

score 0 · Answer 2 · answered Feb 13 '22 at 04:23

The question that you asked

"Can someone explain what the difference is between ArrayList and HashSet?"

is too broad. There are many differences, and you should be able to find many resources that summarize them.

The (probable) specific thing that is causing a performance difference in your program will be this:

 if (list.contains(prefixsum - X)) {
        count++;
 }

versus (presumably)

 if (set.contains(prefixsum - X)) {
        count++;
 }

In the ArrayList case, the contains method has to test each element of the list until it either find a match or reaches the end. The time taken to do that will typically be proportional to the number of elements in the list.

In the HashSet case, a hash table data structure is used which (typically) reduces the number of elements that need to be tested to a small number.

The net result is that contain is fast for a HashSet and slow for ArrayList.

Explaining in detail how hash tables work in general and specifically in the HashSet case is beyond the scope of this Q&A.

ArrayList vs HashSet

2 Answers2