find pair of numbers in array that add to given sum

by

If you have a sorted array you can find such a pair in O(n) by moving two pointers toward the middle

i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

The sorting can be made O(N) if you have a bound on the size of the numbers (or if the the array is already sorted in the first place). Even then, a log n factor is really small and I don’t want to bother to shave it off.

proof:

If there is a solution (i*, j*), suppose, without loss of generality, that i reaches i* before j reaches j*. Since for all j' between j* and j we know that a[j'] > a[j*] we can extrapolate that a[i] + a[j'] > a[i*] + a[j*] = target and, therefore, that all the following steps of the algorithm will cause j to decrease until it reaches j* (or an equal value) without giving i a chance to advance forward and “miss” the solution.

The interpretation in the other direction is similar.

More Related Contents:

  1. maximize the top element of the stack after performing exactly K operations
  2. Algorithm for all subsets of Array
  3. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  4. List of Big-O for PHP functions
  5. Finding three elements in an array whose sum is closest to a given number
  6. MATLAB adding array elements iteratively: time behavior
  7. How to find the kth smallest element in the union of two sorted arrays?
  8. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  9. Can min/max of moving window achieve in O(N)?
  10. Weighted random selection from array
  11. Print two-dimensional array in spiral order
  12. Find the Smallest Integer Not in a List
  13. How to find a duplicate element in an array of shuffled consecutive integers?
  14. Find the majority element in array
  15. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  16. Binary Search algorithm implementations
  17. Algorithm to determine if array contains n…n+m?
  18. Find the 2nd largest element in an array with minimum number of comparisons
  19. Find all subsets of length k in an array
  20. Maximum single-sell profit
  21. A data structure supporting O(1) random access and worst-case O(1) append?
  22. How to find max. and min. in array using minimum comparisons?
  23. Performance difference between looping range vs looping array
  24. Is indexing vectors in MATLAB inefficient?
  25. Interview question: three arrays and O(N*N)
  26. How to find repeating sequence of characters in a given array?
  27. Maximum sum of non consecutive elements
  28. Finding kth smallest number from n sorted arrays
  29. calculating the number of “inversions” in a permutation
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment