Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k

by

If the arrays are sorted you can do it in linear time and constant storage.

  • Start with two pointers, one pointing at the smallest element of A, the other pointing to the largest element of B.
  • Calculate the sum of the pointed to elements.
  • If it is smaller than k increment the pointer into A so that it points to the next largest element.
  • If it is larger than k decrement the pointer into B so that it points to the next smallest element.
  • If it is exactly k you’ve found a pair. Move one of the pointers and keep going to find the next pair.

If the arrays are initially unsorted then you can first sort them then use the above algorithm. There a few different approaches for sorting them that you could use, depending on the type of data you expect:

A comparison sort will require O(n log n) time on average. The last two are faster than O(n log(n)) but can be impractical if the range of possible values in the input arrays is very large.

More Related Contents:

  1. generate all partitions of a set [closed]
  2. The intersection of all combinations of n sets
  3. Efficient algorithm for finding all maximal subsets
  4. Custom Weighted Scale [closed]
  5. HSL to RGB color conversion
  6. Constant Amortized Time
  7. What exactly does big Ө notation represent?
  8. Expand a random range from 1–5 to 1–7
  9. How to find the intersection point between a line and a rectangle?
  10. Quicksort: Choosing the pivot
  11. Breadth First Vs Depth First
  12. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  13. What is pseudopolynomial time? How does it differ from polynomial time?
  14. True random number generator [closed]
  15. What is the difference between tree depth and height?
  16. What would cause an algorithm to have O(log n) complexity?
  17. Programming theory: Solve a maze
  18. Finding the median of an unsorted array
  19. How to estimate download time remaining (accurately)?
  20. Sorting in linear time? [closed]
  21. Algorithm for finding numerical permutation given lexicographic index
  22. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  23. Why is the time complexity of both DFS and BFS O( V + E )
  24. How to compute a 3D Morton number (interleave the bits of 3 ints)
  25. Create non-intersecting polygon passing through all given points
  26. Enumerating all paths in a directed acyclic graph
  27. RGB value base color name
  28. Variation on knapsack – minimum total value exceeding ‘W’
  29. Path generation for non-intersecting disc movement on a plane
  30. Calculating frames per second in a game

Leave a Comment