Interview question: three arrays and O(N*N)

by

This can be done in O(1) space and O(N2) time.

First lets solve a simpler problem:
Given two arrays A and B pick one element from each so that their sum is equal to given number K.

Sort both the arrays which takes O(NlogN).

Take pointers i and j so that i points to the start of the array A and j points to the end of B.

Find the sum A[i] + B[j] and compare it with K

  • if A[i] + B[j] == K we have found
    the pair A[i] and B[j]
  • if A[i] + B[j] < K, we need to
    increase the sum, so increment i.
  • if A[i] + B[j] > K, we need to
    decrease the sum, so decrement j.

This process of finding the pair after sorting takes O(N).

Now lets take the original problem. We’ve got a third array now call it C.

So the algorithm now is :

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

The outer loop runs N times and for each run we do a O(N) operation making the entire algorithm O(N2).

More Related Contents:

  1. maximize the top element of the stack after performing exactly K operations
  2. Algorithm for all subsets of Array
  3. How to sort in-place using the merge sort algorithm?
  4. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  5. Finding three elements in an array whose sum is closest to a given number
  6. Given an array of numbers, return array of products of all other numbers (no division)
  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. Given an array, find out the next smaller element for each element
  17. Binary Search algorithm implementations
  18. Algorithm to determine if array contains n…n+m?
  19. Find the 2nd largest element in an array with minimum number of comparisons
  20. Find all subsets of length k in an array
  21. Maximum single-sell profit
  22. In-place array reordering?
  23. find pair of numbers in array that add to given sum
  24. Regarding in-place merge in an array
  25. How to find repeating sequence of characters in a given array?
  26. Maximum sum of non consecutive elements
  27. Finding kth smallest number from n sorted arrays
  28. calculating the number of “inversions” in a permutation
  29. Algorithm to apply permutation in constant memory space
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment