I recently attended an interview and they asked me to solve the below problem by using O(n) time complexity. (Hackerranker)

Problem:

Given an integer array and there will be l integer and r integer. Need to find the which are all the pair of elements sum will be equal and in between l and r value;

Example:

int[] array = {2,3,4,5}; int l=5, int r=7;

Output: 4

Input properties:

• The input is unsorted.
• The input will have duplicate elements.
• The input array is non-negative.

The below combination will return the sum which will be equal and in between l and r range value, where if the pair is less than l or greater than r it should be skipped. And pairs can't be duplicated:

array[0]   array[1] = 5 -> counter  
array[0]   array[2] = 6 -> counter  
array[0]   array[3] = 7 -> counter  
array[1]   array[2] = 7 -> counter  
array[1]   array[3] = 8 -> greater than r, no counter increment

I tried the below approach and it works fine but its time complexity is O(n^2):

 public static int sumPairs(int[] array,int l, int r)
    {
        int counter=0;
        for(int i=0;i<array.length;i  )
        {
            for(int j=i 1;j<array.length;j  )
            {
                int sum = array[i] array[j];
                
                if(sum<=r && sum>=l)
                {
                    counter  ;
                }
            }
        }
        
        return counter;
    }

Can someone help me to find a way to optimize the above code to become O(n) time complexity?

CodePudding user response：

To find the number of pairs of elements in an array summing up to a value within given range. The maximum possible int value is assumed to be known in advance, as it is with the usual int type (i.e. not bignums):

1. Sort the array by radix sort in O(n) in ascending order.
2. Scan the array from i=0 with j=1 incrementing j while a[i] a[j] < l, next with k=j incrementing k until a[i] a[k] > r. Decrement k. Set count = k-j 1.
3. Increment i once, possibly repeatedly decrementing j and k to maintain the boundary conditions, making sure i =< j =< k and i,j,k are valid access.
4. If there are no valid i,j,k, go to 6. Otherwise,
5. Increment count by k-j 1 and go back to 3.
6. Stop. count is the result.

(adjust the above for corner cases as needed.)

CodePudding user response：

Here's my approach using a cumulative histogram instead of a sort. In c , sorry.

static int sumPairsLinear(int *pArray,int iArraySize, int l, int r)
{
    int iResult = 0;
    // 1. Iterate the array and toss any entries larger than r
    for (int i=0;i<iArraySize;)
    {
        if (pArray[i] > r)
            pArray[i] = pArray[--iArraySize];
        else
            i  ;
    }
    // 2. Allocate a zero initialised array of ints, of size `r 1`.
    int *pHistogram = new int[r 1];
    memset(pHistogram, 0, sizeof(int)*(r 1));
    // 3. Fill the histogram
    for (int i=0;i<iArraySize;i  )
    {
        pHistogram[pArray[i]]  ;
    }
    // 4. Convert it to a cumulative histogram. 
    for (int i=1;i<=r;i  )
    {
        pHistogram[i]  = pHistogram[i-1];
    }
    // 5. Iterate through the values again. Use the cumulative histogram to calculate the number of valid pairs.
    for (int i=0;i<iArraySize;i  )
    {
        int iVal = pArray[i];
        int iIndex = l-iVal-1;
        iResult  = pHistogram[r-iVal] - ((iIndex >= 0) ? pHistogram[iIndex] : 0);
        // Don't pair with self
        iVal *= 2;
        if (iVal <= r &&
            iVal >= l)
        {
            iResult--;
        }
    }
    // 6. Half iResult because we counted each pair twice.
    iResult /= 2;

    delete[] pHistogram;
    return iResult;
}

Horrible performance if r is large but otherwise reasonable and still O(N).