I came across a proposed solution for the 4SUM problem which supposedly solves it in O(nlogn) time.-CodePudding

The time complexity for this seems to be O(nlogn) as we first sort the array and then perform a 4 pointer approach (which is linear in time complexity).

They use 4 pointers LL, LR, RR and RL where the sums of the 4 pointers are added and based on the most optimal movements, they choose to move the pointers accordingly.

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n = 8;
    int a[n] = {1, 2, 3, 4, 6, 5, 7, 8};
    int x = 16;
    sort(a, a   n);
    for (int i = 0; i < n; i  )
    {
        cout << a[i] << ",";
    }
    cout << endl;
    int LL = 0;
    int LR = 1;
    int RL = n - 2;
    int RR = n - 1;
    //cout << LL << "," << LR << "," << RL << "," << RR << endl;
    while (LR < RL)
    {
        if ((a[LL]   a[LR]   a[RL]   a[RR]) > x)
        {
            //cout << (a[LL]   a[LR]   a[RR]   a[RR]) << endl;
            if (a[RL] - a[RL - 1] < ((a[RR]   a[RL]) - (a[RL]   a[RL - 1])))
            {
                RL--;
            }
            else
            {
                RL--;
                RR--;
            }
        }
        else if ((a[LL]   a[LR]   a[RL]   a[RR]) < x)
        {

            if (a[LR   1] - a[LR] < ((a[LR   1]   a[LR]) - (a[LL]   a[LR])))
            {
                LR  ;
            }
            else
            {
                LL  ;
                LR  ;
            }
        }
        else
        {
            cout << "The four elements are:" << a[LL] << "," << a[LR] << "," << a[RL] << "," << a[RR];
            return 0;
        }
        //cout << LL << "," << LR << "," << RL << "," << RR << endl;
    }
    cout << "No such four elements exists";
    return 0;
}

CodePudding user response：

I could take this (any, at that) solution to 4SUM, add a zero to the multiset and use it to solve 3SUM.

CodePudding user response：

Your logic is O(nlogn) but it doesn't do what you think. Your 4SUM algorithm works mostly but here is a counterexample.

First of all let me simplify the "if" and "else if" statements of your 4SUM logic. Here's an equivalent:

if ((a[LL]   a[LR]   a[RL]   a[RR]) > x)
{
    if (a[RL] < a[RR])
    {
        RL--;
    }
    else
    {
        RL--;
        RR--;
    }
}
else if ((a[LL]   a[LR]   a[RL]   a[RR]) < x)
{

    if (  a[LR] >  a[LL])
    {
        LR  ;
    }
    else
    {
        LL  ;
        LR  ;
    }
}
else
{
    cout << "The four elements are:" << a[LL] << "," << a[LR] << "," << a[RL] << "," << a[RR];
    return 0;
}

Here a counter example:
Ordered array: 1, 2, 3, 5, 6, 7
Goal sum: 14

Iteration 1:
LL = 1, LR = 2, RL = 6 and RR = 7
16 > 14 and RL < RR then RL--

Iteration 2:
LL = 1, LR = 2, RL = 5 and RR = 7
15 > 14 and RL < RR then RL--

Iteration 3:
LL = 1, LR = 2, RL = 3 and RR = 7
13 < 14 and LR > LL then LR

Iteration 4:
LL = 1, LR = 3, RL = 3 and RR = 7
Invalid, using twice the same number