CODEWITHSUNDEEP
algorithmloopsbig-o
Uzair Ahmed
Uzair Ahmed

Reputation: 96

Compare elements of two arrays in less than O(n^2) time?

I have two integer arrays. I need to find out two numbers, one from each array, whose sum is equal to 2. This is very simple in O(n^2) but is there a way to do it faster?

Upvotes: 2

Views: 1494

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726569

You can do it in O(N+M) time and O(N) space like this:

  • Put elements of array a into a hash set
  • Walk through array b, and check if hash table contains 2-b[i]

Constructing a hash set of N elements takes O(N) time and O(N) space. Checking each of M elements against the hash set takes O(1), for a total of O(N+M) time.

Upvotes: 5

Related Questions