0

I was running tests for this coding challenge: https://app.codesignal.com/interview-practice/task/Hm98RnqK9Be575yoj/description?solutionId=G73ah4gr33g966arv

I came up with this solution:

boolean sumOfTwo(int[] a, int[] b, int v) {

        boolean answer = false;
       outloop: for(int c : a) {


            for(int d: b) {
                if(c + d == v) {
                    answer = true;
                }
                if(answer) {
                    break outloop;
                }
            }
        }

        return answer;

    }

This does work, but performs much more slowly than the most voted solution -

boolean sumOfTwo(int[] a, int[] b, int v) {
    HashMap<Integer, Boolean> hash = new HashMap<>();
    for (int e : a) hash.put(v - e, true);
    for (int e : b) if (hash.containsKey(e)) {
        
        return false;
        
    }
    return false;

}

My question is - why? I thought arrays performed better than maps?

Nespony
  • 1,253
  • 4
  • 24
  • 42
  • 1
    In your code, you are doing an O(n^2) traversal, every b for every a. In the hash map implementation, you are iterating each array only once, meaning O(n) runtime. Hence, yours is slower. – sbsatter Jul 06 '20 at 10:33
  • Also to clarify: HashMap/HashSet is O(1) for `#contains` – Rogue Jul 06 '20 at 15:35

0 Answers0