locate a pair with targetSum==55 : pre-sorted #O(N) 1-pass

I came up with this idea within 5 sec — carefully adjust le and ri pointers from both ends towards center.

  • if arr[le] + arr[ri] too big, then move le
  • else move ri
  • repeat until success or le+1==ri

My friend Ashish was asked a related question — unsorted array .. must return original indices of the pair. It’s relatively easy to adjust my algo to meet this requirement.

  • before sorting, save the original indices in a multimap or map<val, set<index>>
  • after we found a pair, look up to get the indices.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s