Find all pairs of integers within an array which sum to a specified value

by

I don’t see why the hash table approach is inefficient, at least in algorithm analysis terms – in memory locality terms admittedly, it can be quite bad. Anyway, scan the array twice…

First scan – put all the array elements in the hash table – O(n) total. Individual inserts are only amortized O(1), but a neat thing about how amortized analysis works means the O(n) is absolute – not amortized.

Second scan – check for (sum – current) in the hash table – O(n) total.

This beats the O(n log n) sort-and-search methods, at least in theory.

Then, note that you can combine the two scans into one. You can spot a pair as soon as you encounter the second of that pair during the first scan. In pseudocode…

for i in array.range
  hashset.insert (array [i])

  diff = sum - array [i]
  if hashset.includes (diff)
    output diff, array [i]

If you need positions of the items, use a hashmap and store item positions in it. If you need to cope with duplicates, you might need to store counts in a hashmap. For positions and duplicates, you might need a hashmap of start pointers for linked lists of positions.

This makes assumptions about the hash table implementation, but fairly safe ones given the usual implementations in most current languages and libraries.

BTW – combining the scans shouldn’t be seen as an optimisation. The iteration overhead should be insignificant. Memory locality issues could make a single pass slightly more efficient for very large arrays, but the real memory locality issues will be in the hashtable lookups anyway.

IMO the only real reason to combine the scans is because you only want each pair reported once – handling that in a two-scan approach would be a bit more hassle.

More Related Contents:

  1. Algorithm to beat Strassen’s Algorithm
  2. What does O(log n) mean exactly?
  3. How do I search for a number in a 2d array sorted left to right and top to bottom?
  4. Generate an integer that is not among four billion given ones
  5. Find duplicates in an array, without using any extra space
  6. How to generate Sudoku boards with unique solutions
  7. How to round floats to integers while preserving their sum?
  8. Modulus power of big numbers
  9. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  10. Maximize the rectangular area under Histogram
  11. Compute social distance between two users
  12. Efficient algorithm for ordering different types of objects
  13. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  14. How to find two most distant points?
  15. Smooth spectrum for Mandelbrot Set rendering
  16. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  17. Sorting an array with minimal number of comparisons
  18. Determining if two line segments intersect? [duplicate]
  19. Fastest algorithm for circle shift N sized array for M position
  20. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  21. Lights out game algorithm
  22. Why do we ignore co-efficients in Big O notation?
  23. Previous power of 2
  24. Fast solution to Subset sum
  25. Randomly choosing from a list with weighted probabilities
  26. Planar Graph Layouts
  27. When is each sorting algorithm used? [closed]
  28. Difference between Big-Theta and Big O notation in simple language
  29. 3-PARTITION problem
  30. Binary tree level order traversal

Leave a Comment