Thursday, November 4, 2010

Find two numbers in an unsorted array

Given an unsorted array A find two numbers a, b in A such that a - b = x. In linear time!

1 comment:

  1. Stream the numbers. Push v[i] into a hash table. Lookup into a hash table for the value x-v[i] to exist.. if it does, output v[i] and x-v[i].

    Tougher problem: do this with a fixed amount of memory (ruling out a hash table for all the numbers) Though I suppose you could do it with a fixed size hash table and just use multiple passes to cover the range.

    ReplyDelete