Find the minimal absolute value of a sum of two elements

Question

I am solving the Codility problem provided below,

Let A be a non-empty array consisting of N integers.

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 ≤ P ≤ Q < N.

For example, the following array A:

A[0] = 1 A1 = 4 A[2] = -3 has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2). The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2. The abs sum of two for the pair (0, 1) is A[0] + A1 = |1 + 4| = 5. The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2. The abs sum of two for the pair (1, 1) is A1 + A1 = |4 + 4| = 8. The abs sum of two for the pair (1, 2) is A1 + A[2] = |4 + (−3)| = 1. The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6.`

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array.

For example, given the following array A:

A[0] = 1 A1 = 4 A[2] = -3 the function should return 1, as explained above.

Given array A:

A[0] = -8 A1 = 4 A[2] = 5 A[3] =-10 A[4] = 3 the function should return |(−8) + 5| = 3.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

I write the solution provided below.

public static int solution(int[] A) {

        int N = A.length;
        Arrays.sort(A);

        if (A[0] >= 0) {
            return 2 * A[0];
        }

        int i = 0;
        int j = N - 1;

        int sum = Math.abs((A[i] + A[j]));

        // -10, -8, 3, 4, 5
        while (i <= j) {

            if (Math.abs(A[i + 1] + A[j]) < sum) {

                ++i;
                sum = Math.abs(A[i] + A[j]);

            } else if (Math.abs(A[i] + A[j - 1]) < sum) {

                --j;
                sum = Math.abs(A[i] + A[j]);
            } else {

                i++;
                j--;
            }
        }

        return sum;
    }

The solution gets hanged in the online judge and seems it enters in a forever loop. Is there a possibility that the code can enter a non-ending loop?

UPDATE

After I update the solution with the all negatives check, the code passed the online judge and provides a good performance.

        if(A[N-1] <=0){
            return 2* Math.abs(A[N-1]);
        }

Answer 1

I would like to explain the algorithm that I have implemented and then the implementation in C++.

1. Sort the array because otherwise we would need to check any two arbitrary indices. That brute-force solution would result in O(N ^ 2) runtime complexity.

2. We initialise the min abs sum to something higher than the possible value in the arrays.

3. Apply the caterpillar method by having front and back indices.

4. In every iteration, update the min abs sum as and when needed.

5. There two special cases:

a. all values are zero or positive. We could return A[front] * 2 early.
b. all values are negative or zero. We could return A[back] * 2 early.

In both cases, we could return early, however, it would result in a bit more code, so I personally avoid that. In the above cases, we can still go through the array without degrading the overall runtime complexity. In these cases, it also does not matter how we go through the array with regards to the result, so I just go through the array in one way in both cases. But the code will be shared with the third case.

6. In the third case, where the array, and thereby the sorted array, contains both negative and positive values, we try to keep the sum of front and back to zero since this when the abs sum value is minimised. In other words, we try to keep the balance between the negative and positive numbers by keeping their distance to the minimum.

7. Therefore, if the sum of front and back are less than zero, then we know that the negative front value is greater than the positive back value. As a direct consequence of that, we need to advance the front index.

8. If the sum of front and back are equal to zero, then we found the smallest min abs sum that is ever possible. The absolute value cannot be less than zero. Whilst I could return at this point in the code for some constant optimisation, I do not do so to keep the code the minimal and also functional.

9. If the sum of front and back are greater than zero, then we know that the negative front value is less than the positive back value. As a direct consequence of that, we need to decrease the index.

10. We loop until the front and back indices meet, but we handle the case when they are equal since according to the task specification, the same index can be used twice for the absolute sum.

The runtime complexity of this solution is O(N * logN) because the sorting of the array is O(N * logN) and the loop is O(N) since we go through every element. Therefore, the sorting runtime complexity dominates the loop.

The space complexity is O(1) because we only allocate constant space independently from the number of inputs. The sorting is done in place.

int solution(vector<int> &A)                                                    
{                                                                               
  const int N = A.size();                                                       
  sort(A.begin(), A.end());                                                     
  int min_abs_sum_of_two = INT_MAX;                                             
  for (int front = 0, back = N - 1; front <= back;) {                           
    const int ef = A[front];                                                    
    const int eb = A[back];                                                     
    min_abs_sum_of_two = min(min_abs_sum_of_two, abs(ef + eb));                 
    if (ef + eb < 0) ++front; else --back;                                      
  }                                                                             
  return min_abs_sum_of_two;                                                    
}

Answer 2

The Answer is late but I hope to help anyone have the same question

//============================================================================
// Author: Hamdy Abd El Fattah
// Code is like humor. When you have to explain it, it’s bad.
//============================================================================
#include <bits/stdc++.h>
#define FIO cin.tie(0), cin.sync_with_stdio(0)
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int main() {
    FIO;
    ll n , m = INF , x;
    vector<ll> positive,negative;
    cin>>n;
    while(n--){
        cin>>x;
        if(x < 0)
            negative.push_back(x * -1);
        else if(x > 0)
            positive.push_back(x);
        else
            m = 0;
    }

    if(m == 0){
        cout<<"0\n";
    }else{

        sort(positive.begin(), positive.end());
        sort(negative.begin(), negative.end());
        int i= 0, j = 0;
        int positive_size = positive.size(), negative_size =negative.size();
        while(i < positive_size || j < negative_size){
            if(abs(positive[i] - negative[j]) < m){
                m=abs(positive[i] - negative[j]);
                m=min(min(m,positive[i]*2),negative[j] * 2);
            }
            if((i < positive_size && positive[i] <= negative[j]) || j == negative_size)
                i++;
            else if((j < negative_size && positive[i] > negative[j]) || i == positive_size)
                j++;
        }
        cout<<m<<endl;
    }


    return 0;
}

Answer 3

I got 100% for following code ( java). Slightly modified version of https://www.techiedelight.com/find-pair-array-minimum-absolute-sum/

import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
         // sort the array if it is unsorted
         Arrays.sort(A);
          int low = 0;
        int high = A.length - 1;
   if (A[0] >= 0) {
            return 2 * A[0];
        }
          if (A[high] <= 0) {
            return -2 * A[high];
        }
        // maintain two indexes pointing to endpoints of the array
       
 
        // `min` stores the minimum absolute difference
        int min = Integer.MAX_VALUE;
        int i = 0, j = 0;
 
        // reduce the search space `A[low…high]` at each iteration of the loop
        int sum = 0;
        // loop if `low` is less than `high`
        while (low < high)
        {
            // update the minimum if the current absolute sum is less.   
            sum = A[high] + A[low];
            if (Math.abs(sum) < min)
            {
                min = Math.abs(sum);
                i = low;
                j = high;
            }
 
            // optimization: pair with zero-sum is found
            if (min == 0) {
                break;
            }
 
            // increment `low` index if the total is less than 0;
            // decrement `high` index if the total is more than 0
            if (sum < 0) {
                low++;
            }
            else {
                high--;
            }
        }
        return min;

    }
    
}

Answer 4

For input arrays e.g({-1, -2, -3}, {-1, -2}, {-1} your algorithm throws ArrayIndexOutOfBoundsException, so arrays when there are only negative numbers and there is no repeats

There is no chance to reach endless loop because either i or j change only + or - 1