find pair of numbers in array that add to given sum

Question

Question: Given an unsorted array of positive integers, is it possible to find a pair of integers from that array that sum up to a given sum?

Constraints: This should be done in O(n) and in-place (without any external storage like arrays, hash-maps) (you can use extra variables/pointers)

If this is not possible, can there be a proof given for the same?

Solution 1

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.

Solution 2

An O(N) time and O(1) space solution that works on a sorted array:

Let M be the value you're after. Use two pointers, X and Y. Start X=0 at the beginning and Y=N-1 at the end. Compute the sum sum = array[X] + array[Y]. If sum > M, then decrement Y, otherwise increment X. If the pointers cross, then no solution exists.

You can sort in place to get this for a general array, but I'm not certain there is an O(N) time and O(1) space solution in general.

Solution 3

My solution in Java (Time Complexity O(n)), this will output all the pairs with a given sum

import java.util.HashMap;
import java.util.Map;

public class Test {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Map<Integer, Integer> hash = new HashMap<>();
    int arr[] = {1,4,2,6,3,8,2,9};
    int sum = 5;
    for (int i = 0; i < arr.length; i++) {
        hash.put(arr[i],i);
    }
    
    for (int i = 0; i < arr.length; i++) {
        if(hash.containsKey(sum-arr[i])){
            //System.out.println(i+ " " +  hash.get(sum-arr[i]));
             System.out.println(arr[i]+ " " + (sum-arr[i]));
        }
    }
}
}

Solution 4

This might be possible if the array contains numbers, the upper limit of which is known to you beforehand. Then use counting sort or radix sort(o(n)) and use the algorithm which @PengOne suggested.

Otherwise I can't think of O(n) solution.But O(nlgn) solution works in this way:-

First sort the array using merge sort or quick sort(for inplace). Find if sum - array_element is there in this sorted array. One can use binary search for that.

So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).

Solution 5

AS @PengOne mentioned it's not possible in general scheme of things. But if you make some restrictions on i/p data.

1. all elements are all + or all -, if not then would need to know range (high, low) and made changes.
2. K, sum of two integers is sparse compared to elements in general.
3. It's okay to destroy i/p array A[N].

Step 1: Move all elements less than SUM to the beginning of array, say in N Passes we have divided array into [0,K] & [K, N-1] such that [0,K] contains elements <= SUM.

Step 2: Since we know bounds (0 to SUM) we can use radix sort.

Step 3: Use binary search on A[K], one good thing is that if we need to find complementary element we need only look half of array A[K]. so in A[k] we iterate over A[ 0 to K/2 + 1] we need to do binary search in A[i to K].

So total appx. time is, N + K + K/2 lg (K) where K is number of elements btw 0 to Sum in i/p A[N]

Note: if you use @PengOne's approach you can do step3 in K. So total time would be N+2K which is definitely O(N)

We do not use any additional memory but destroy the i/p array which is also not bad since it didn't had any ordering to begin with.

View more solutions

Comments

[Rohan Desai]

The given sum is not selected. It is given to you as part of the question.

[niting112]

If we know the upper limit on the elements of the array, one can use radix or counting sort (O(n)) and apply the algorithm which you stated.

[noMAD]

This solution assumes the array is sorted, which is not the question. Sorting takes O(n logn) and would defeat your argument that it runs in constant time. :) Thanks anyways

[Drone Brain]

A LSD radix sort takes O(k*n) and runs in place where c is the max number of digits. A hashmapping can have similar results although it does not run in place. So it is possible to pair this with a faster sort to get O(n) time on average.

[Drone Brain]

Hey noMAD. I've edited the solution and updated it with an algorithm that runs using unsorted arrays.

[user3068966]

Sorry, but what do you mean by "sorting can be made O(n) if you have a bound on the size"? To sort an array, the most efficient algorithm will take O(NlogN), isn't it? Please give more explaination. Thanks.

[Rohan Desai]

@user3068966: The O(NlogN) bound is for algorithms that are only allowed to compare numbers with each other and swap their positions. Things like CountingSort or RadixSort can be O(N) because they are not comparison-based algorithms.

[Clinton]

shouldn't it be a[i] + a[j'] > a[i*] + a[j*], since in your proof i would = i* and a[j'] is > a[j*]

[Rohan Desai]

@Clinton: oops! fixed

[sergeyan]

@missingno: As I understand, the problem requires to be solved in-place. I'm not familiar with Counting Sort algo, but Radix Sort definitely is not in place algo.

[Deepankar Singh]

This is not a proof that Solution is not possible in O(N) time and O(1) space,assuming bounds on size is not known.

[Anil]

Count sort has time complexity of O(n) ?? .. Wow !!

[user2001627]

The print statement should be "System.out.println(arr[i]+ " " + (sum-arr[i]));"

[dk123]

I don't quite understand a[i] + a[j'] > a[i*] + a[j*]. According to the question: a[j*] < a[j'], but a[i] < a[i*], isn't it?