educative.io

Educative

Linear solution for Find Two Numbers that Add up to "n"

I don’t know why it is not in the solution review, but the problem is solvable in O(n)

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

    for (int i = 0; i < arr.length; i++) {
      Integer difference = n - arr[i];

      if (dic.containsKey(difference)) {
        result[0] = arr[i];
        result[1] = difference;
        break;
      }
      dic.put(arr[i], i);
    }
    // write your code here
    return result;   // return the elements in the array whose sum is equal to the value passed as parameter 
  }

Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

1 Like

Hi @Evgeny_Mironenko, Thanks for reaching out to us.
The given solution is just for the implementation purpose that’s why it can be done using any approach.Yes this problem can be done in O(n).In the lesson, it has been already highlighted you can scroll down to this link here a note is there which tells us the optimal solution which refers to Challenge 10. And the solution of the problem is given in O(n).

Hope the answer to your query, Happy Learning :blush:

1 Like