Problem link -  Four Sum | CodeChef

Algorithm(s) - 3 pointer method

Time complexity  - O(N²)

Short Editorial

Create a pair of 2 pointers where each pair calculates frequency of sum of the 2 numbers pointed to by the pointers. 

Detailed Editorial

In this problem, we are given a set of numbers (N <= 5000) and we are asked to find number of ways of selecting 4 numbers whose sum equals a given number T (<= 10⁶).

A brute force algorithm using 4 pointers can be used to solve this problem in O(N⁴) time but that will not fit the time limit. Given the size of N, we need an O(N²) algorithm.

To solve this problem, we set up three pointers (i,j,k). Pointer i iterates from 1 to n-1, pointer j iterates from i+1 to n-1 and pointer k iterates from 0 to i-1.

Pointers i & j are used to calculate sum of 2 numbers pointed to by these pointers and pointers i & k are used to calculate sum of two numbers pointed to by these 2 pointers. However, pointer i in these pairs will not be pointing to the same number as it would have moved by one position to right before it will be used so using these 3 pointers we will be able to calculate sum of 4 numbers.

While we iterate over the input array, we will maintain an auxiliary array called frequency that will store the number of ways of forming a sum pointed to by the two pointers.

Line by line Editorial

    for(int i = 1; i < n; i++){

        for(int j = i+1; j < n; j++){

Two nested loop for 2 pointers i & j as described above.

            ans += freq[t-nums[i]-nums[j]]; 

Since pointers i & j are pointing to two numbers, we can get sum of these two numbers. We need to find the number of ways of generating the remaining sum which will be stored in the freq array which is updated in the later part of the code.

        for(int k = 0; k < i; k++){

Loop for the 3rd pointer. This loop is nested inside the loop for i poiner.

            freq[nums[i]+nums[k]]++;

Pointers i & k are pointing to two numbers. This line updates the freq array to increment number of ways of forming a sum of two numbers pointed by these 2 numbers by one.

Note that since loop for pointer k starts after loop for pointer j ends, the next iteration of loop j will use the next value of pointer i and not the same value of i that will be used by the loop for pointer k. This will ensure that two nested loops (i & j and i & k) use separate values of i, thus pointing a sum of 4 values and not 3. 

Complete Code

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n, t;

    cin >> n >> t;

    vector<int> nums(n), freq(t+1);

    for(int i = 0; i < n; i++)

        cin>>nums[i];

    sort(nums.begin(), nums.end());

    long long ans = 0;

    for(int i = 1; i < n; i++){

        for(int j = i+1; j < n; j++){

            if(nums[i]+nums[j] > t)

                break;

            ans += freq[t-nums[i]-nums[j]];

        }

        for(int k = 0; k < i; k++){

            if(nums[i]+nums[k] > t)

                break;

            freq[nums[i]+nums[k]]++;

        }

    }

    cout<<ans;

}