Timo
BAN USER
Comments (3)
Reputation 40
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 vote
I fail to see how daywalker's solution works. Given the high number of votes and praises, however, I must assume that I am mistaking something.
Consider the (zero-based-)array [1,2,3,3] of size 3+1 = 4. On the algorithm's first iteration, a[0] is checked and found positive (it is 1). So the value -1 is stored under a[a[0]] = a[1] which is where the value 2 is located. The updated array looks like this: [1,-1,3,3].
On the second iteration, a[1] is found negative (it is -1) and therefore -1 reported as a duplicate (which it is not).
This seems wrong to me. What am I missing?
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
A better approach would be to store all integers in a hash table additionally and use that table in the final loop over all sums to look up the required complement. That way, the runtime complexity drops to O(n^2).
- Timo February 06, 2013