,  

Count triplets with sum smaller than a given value

Problem: Given an array of distinct integers and a sum value. Find count of triplets with sum smaller than given sum value.

For example: 
Input arr[] = {5, 2, 7, 8, 4, 3}
        Sum = 14
Output: 7

There are 7 triplets with sum smaller than given sum value (5, 2, 4), (5, 2, 3), (5, 4, 3), (2, 7, 4), (2, 7, 3), (2, 8, 3), (2, 4, 3)
Method 1: The brute-force solution is to run three loops to consider all triplets one by one. For every triplet, compare the sums and increment count if triplet sum is smaller than given sum. 
class InterviewDesk
{    
    static int countTriplets(int arr[], int n, int sum)
    {
        /* initialize result */
        int ans = 0;
      
        /* fix the first element as arr[i] */
        for (int i = 0; i < n-2; i++)
        {
            /* fix the second element as arr[j] */
            for (int j = i+1; j < n-1; j++)
            {
               /* now look for the third number */
                for (int k = j+1; k < n; k++)
                if (arr[i] + arr[j] + arr[k] < sum)
                {
                    ans++;
                }
            }
        }
      
        return ans;
    }
     
    /* driver function */
    public static void main(String[] args) 
    {
        int arr[] = {5, 2, 7, 8, 4, 3};
        int sum = 14; 
        System.out.println(countTriplets(arr, arr.length, sum));
    }
}
Output: 
7
Time Complexity: O(n3)

Method 2: We can do this problem in O(n2) by help of following approach:
  1. Sort the input array in increasing order.
  2. Initialize result as 0.
  3. Run a loop from i = 0 to n-2. An iteration of this loop finds all triplets with arr[i] as first element.
    • Initialize other two elements as corner elements of subarray arr[i+1..n-1], i.e. j = i+1 and k = n-1
    • Move j and k toward each other until they meet, i.e. while (j < k)
      •  if (arr[i] + arr[j] + arr[k] >= sum), 
        • then do k-- 
      •  Else Do ans += (k - j) followed by j++
import java.util.Arrays;

class InterviewDesk
{
     
    static int countTriplets(int arr[], int n, int sum)
    {
        /* sort input array */
        Arrays.sort(arr);
      
        /* initialize result */
        int ans = 0;
      
        for (int i = 0; i < n - 2; i++)
        {
            /* Initialize other two elements as corner elements
               of subarray arr[j+1..k] */
            int j = i + 1, k = n - 1;
      
            /* move j and k toward each other until they meet */
            while (j < k)
            {
                /* If sum of current triplet is more or equal,
                   move right corner to look for smaller values */
                if (arr[i] + arr[j] + arr[k] >= sum)
                    k--;
      
                /* else move left corner */
                else
                {
                    /* for current i and j, there can be total k-j 
                       third elements */
                    ans += (k - j);
                    j++;
                }
            }
        }
        return ans;
    }
     
    /* driver function */
    public static void main(String[] args) 
    {
        int arr[] = {5, 2, 7, 8, 4, 3};
        int sum = 14; 
        System.out.println(countTriplets(arr, arr.length, sum));
    }
}
Output: 
7
Time Complexity: O(n2)