educative.io

Brute Force solution for Find Two Numbers that Add up to "n"

Courses
,
#1

I had a question about the first (Brute force) solution for the problem on Find Two Numbers that Add up to “n”.

The given explanation says

Traverse the whole array of the given size. For each element in the array, check if any of the two elements add up to the given number n . Use a nested for-loop for this purpose and iterate over the entire array for each element.

Specifically, the last line says we iterate over the entire array once for each element. I don’t think this is true.

Consider this array - [2, 4, 5, 7, 8].

  1. For the first iteration of the outer loop, we set i at the first element 2. Then for the inner loop, we set j at i+1, that is, we start checking from 4 up to 8.
  2. For the next iteration of the outer loop, when i is at 4, we set j at i+1 again, that is, we check from 5 till 8. We don’t again set j at index 0 and traverse the entire array again, because 2 + 4 has already been checked in the first step.

So why does the explanation say “iterate over the entire array for each element”?

#2

Hi @Manish_Giri ,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your question, you are correct. The explanation is not consistent with the code. The algorithm being explained in the description is also a brute force algorithm which is even slower than the one mentioned in the code. The code has a better running time complexity because we do not iterate n times in the nested loop. However, both the algorithms have the same Big Oh complexity, i.e, O(n). I fixed the description in the lesson to represent the code. Thank you for reporting this inconsistency.

Best Regards,

Fatimah Abdullah | Developer Advocate
Educative

1 Like
#3

Hi @FatimahAbdullah

Thank You for looking into this issue, and fixing the description. I just wanted to clarify the time complexity you mentioned -

I think you meant O(n^2)? Because O(n) would indicate iterating through the array only once.

Thanks,
Manish

#4

@Manish_Giri, yes. Apologies for the typo. I indeed meant O(n^2).

#5

This can be done in O(n) time using a hash table, thereby avoiding the need to sort. Here is my solution:

  public static int[] findSum(int[] arr, int n) 
  {
    int[] result = new int[2];
    
    HashMap<Integer, Integer> map = new HashMap<>();

    for(int i = 0; i < arr.length; i++)
    {
      int complement = n - arr[i];
      if(!map.containsValue(arr[i]))
        map.put(i, arr[i]);

      if(map.containsValue(complement))
      {
        result[0] = arr[i];
        result[1] = complement;
      }
    }
    return result;   // return the elements in the array whose sum is equal to the value passed as parameter 
  }

O(n log n) is only better than O(n) so long as the sample size, n, is less than 10. Once it exceeds that size, O(n) becomes much more efficient. It would be prudent to assume that the sample size is almost always greater than 10, and in a real world scenario, we would want to assume the worst/most stressful case for the algorithm. So, shouldn’t the O(n) be the ideal approach here?

#6

Correct but with no extra space its O(n log n) cannot be made better it seems …