Triplets with Sum between given Range

Arrays are the most commonly used data structure in programming and today we are going to discuss an array based problem called as "Triplets with Sum between given range problem".

Problem Description

In this problem, we are provided with an array of distinct integers and a range [x, y]. Our task is to count the number of triplets whose sum lies in the given range [x, y], i.e., find all triplets (a,b,c) such that x < (a+b+c) < y

Approach

There can be two different approaches to this problem. The first one is the brute force approach wherein we form all the triplets from the array elements and then check their sum in the given range. The second approach is a more efficient one since here we first find all the triplets with sum less than the upper limit (x) and then subtract the triplets which have lesser sum than the lower limit. In this way we obtain the required triplets in a more efficient manner. 

Method 1: Brute-force Approach

This is a simple approach where we find the various triplets from the array elements by running three loops. Then we find the sum for each individual triplet and check if it lies in the given range [x, y]. If the sum lies in the given range, we increment our counter. At the end, we display the final counter value that tells the number of desired triplets.

Pseudocode

In the above pseudocode, the function tripletCheck() first declares a variable count to store the count of all the triplets that have sum within our given range.Then we run three loops to form all the possible triplets: 

1. The first i loop is used to set the first number and it runs from 0 to n-2. 
2. The second j loop sets the second number runs from i+1 to n-1.
3. After setting the first two numbers we run the third k loop from j+1 to n and search for the third number to form a triplet.

We check for each triplet if its sum lies within [x, y] and if so, we increment the count. At last, we return the count value. The below illustartion shows how all triplets are formed and then checked:

Code

#include <iostream>
using namespace std; 
  
// Function to check valid triplets 
int tripletCheck(int arr[], int n, int x, int y) 
{ 
    int count = 0; 
  
    
    for (int i = 0; i < n - 2; i++)
    { 
        for (int j = i + 1; j < n - 1; j++) 
        {  
            for (int k = j + 1; k < n; k++) 
            {
                if (arr[i] + arr[j] + arr[k] >= x && arr[i] + arr[j] + arr[k] <= y) 
                    count++; 
            }
        } 
    } 
  
    return count; 
} 
  
// Driver Code 
int main() 
{ 
    int arr[] = { 1, 2, 3, 4, 5 }; 
    int n = sizeof arr / sizeof arr[0]; 
    int x = 2, y = 8; 
    cout << "Number of valid triplets is "<<tripletCheck(arr, n, x, y) << endl; 
    return 0; 
} 

class CodesDope 
{ 
      
// Function to check valid triplets 
public static int tripletCheck(int []arr, int n, 
                                int x, int y) 
{ 
    int count = 0; 
  
    for (int i = 0; i < n - 2; i++) 
    { 
        for (int j = i + 1; j < n - 1; j++)  
        { 
  
            for (int k = j + 1; k < n; k++) 
            { 
                if (arr[i] + arr[j] + arr[k] >= x && arr[i] + arr[j] + arr[k] <= y) 
                    {
                        count++;
                    } 
            } 
        } 
    } 
  
    return count; 
} 
  
// Driver Code 
public static void main(String[] args) 
{ 
    int[] arr = { 1, 2, 3, 4, 5 }; 
    int n = arr.length; 
    int x = 2, y = 8; 
    System.out.println("Number of valid triplets is " + tripletCheck(arr, n,  
                                        x, y)); 
} 
} 

# Function to check valid triplets 
def tripletCheck(arr, n, x, y): 
	count = 0

	for i in range(0, n - 2): 
	 
		for j in range(i + 1, n - 1): 

			for k in range(j + 1, n): 
			    if ((arr[i] + arr[j] + arr[k] >= x) and (arr[i] + arr[j] + arr[k] <= y)): 
			            count += 1
						
	return count 

# Driver code 
arr = [ 1, 2, 3, 4, 5 ] 
n = len(arr) 
x = 2
y = 8
print("Number of valid triplets is",tripletCheck(arr, n, x, y)) 

Output:

Method 2: Efficient Approach

Pseudocode

• In the above pseudocode, the first function tripletsLessThan() is our main code since it finds the number of triplets whose sum is less than a given value. Here we first sort the array elements in an ascending order and then initialize our counter and sum variables. Then we run a for loop from 0 to n-2 and this loop selects the first item of the triplet. 
  
• After selecting the first element, we select the other two elements by first selecting values of j and k as the border values of the remaining subarray and then selecting other values in a meet in the middle manner. The while loop runs till our counters for second and third elements don't overlap and we find the sum for each triplet.
• If the sum is greater than the given value, we move the third element counter (k) one step closer as the elements are sorted and we require a smaller element to make our sum less than the given value. If the sum is less than or equal to the given value, we increment count c by (k-j). This is because we have sorted our elements first and if the sum of the triplet formed by last elements is less than the given value, all preceding triplets will also have a smaller sum.
• This way the outer for loop checks for all triplet sums and at the end we return the final number of triplets with sum less than the given value.
• The second method, tripletCheck() simply finds the number of triplets less than upper limit and the lower limit and their difference is our final answer.
  

Code

#include <bits/stdc++.h> 
using namespace std; 

// Function to find count of triplets having sum less than or equal to val. 
int tripletsLessThan(int arr[], int n, int val) 
{ 
	sort(arr, arr + n);  
	int c = 0, j, k; 
	// Variable to store sum of triplets 
	int s; 

	// Fix the first element 
	for (int i = 0; i < n - 2; i++) { 

		// Initialize other two elements as corner elements of subarray 
		// arr[j+1..k] 
		j = i + 1; 
		k = n - 1; 

		// Using Meet in the Middle concept
		while (j != k) { 
			s = arr[i] + arr[j] + arr[k]; 

			// If triplet sum is greater,reduce it by decreasing k
			if (s > val) 
				k--; 

			// If sum is less than or equal to given value, then add possible 
			// triplets (k-j) to result
			else { 
				c += (k - j); 
				j++; 
			} 
		} 
	} 

	return c; 
} 

// Function to return valid triplets in range [x, y].
int tripletCheck(int arr[], int n, int x, int y) 
{ 
	int ans; 

	ans = tripletsLessThan(arr, n, y) - tripletsLessThan(arr, n, x - 1); 

	return ans; 
} 

// Driver Code 
int main() 
{ 
	int arr[] = { 1, 2, 3, 4, 5 }; 
	int n = sizeof arr / sizeof arr[0]; 
	int x = 8, y = 10; 
	cout << "Number of valid triplets is "<< tripletCheck(arr, n, x, y) << endl; 
	return 0; 
} 

import java.util.*;
class CodesDope 
{ 
// Function to find count of triplets having sum less than or equal to val. 

public static int tripletsLessThan(int []arr,int n, int val) 
{ 
    Arrays.sort(arr); 
    int c = 0, j, k; 
	// Variable to store sum of triplets 
	int s; 

	// Fix the first element 
	for (int i = 0; i < n - 2; i++) { 

		// Initialize other two elements as corner elements of subarray 
		// arr[j+1..k] 
		j = i + 1; 
		k = n - 1; 

		// Using Meet in the Middle concept
		while (j != k) { 
			s = arr[i] + arr[j] + arr[k]; 

			// If triplet sum is greater,reduce it by decreasing k
			if (s > val) 
				k--; 

			// If sum is less than or equal to given value, then add possible 
			// triplets (k-j) to result
			else { 
				c += (k - j); 
				j++; 
			} 
		} 
	} 

	return c; 
} 
  
public static int tripletCheck(int arr[], int n, int x, int y) 
    { 
      int ans; 

	  ans = tripletsLessThan(arr, n, y) - tripletsLessThan(arr, n, x - 1); 

	  return ans; 
    } 
  
// Driver Code 
public static void main(String[] args) 
{ 
    int[] arr = { 1, 2, 3, 4, 5 }; 
    int n = arr.length; 
    int x = 8, y = 10; 
    System.out.println("Number of valid triplets is " + tripletCheck(arr, n, x, y)); 
} 
} 

# Function to find count of triplets having sum less than or equal to val. 
def tripletsLessThan(arr, n, val): 
	arr.sort() 
	c = 0
	j , k = 0, 0
	# Variable to store sum of triplets
	s = 0
	# Fix the first element 
	for i in range(0,n-2): 

		# Initialize other two elements as corner elements of subarray 
		# arr[j+1..k] 
		j = i + 1
		k = n - 1

		# Using Meet in the Middle concept
		while j != k : 
			sum = arr[i] + arr[j] + arr[k] 
			
			# If triplet sum is greater,reduce it by decreasing k
			if sum > val: 
				k-=1
			# If sum is less than or equal to given value, then add possible 
			# triplets (k-j) to result
			else : 
				c += (k - j) 
				j += 1
	return c 

# Function to return valid triplets in range [x, y]. 
def tripletCheck(arr, n, x, y): 
	
	ans = 0
	ans = (tripletsLessThan(arr, n, y) - tripletsLessThan(arr, n, x - 1)) 

	return ans 

# Driver code 
arr = [ 1, 2, 3, 4, 5 ] 
n = len(arr) 
x = 8; y = 10
print("Number of valid triplets is",tripletCheck(arr, n, x, y)) 

Output:

Complexity Analysis

The naïve approach checks for all the triplets and then compares there sum within our given range. It uses three loops to generate triplets and thus the time complexity is of the order of O(N³).

The second approach is much more efficient since it uses the meet in the middle pattern to generate triplets and also we only find triplets less than our given range borders, this way we skip many unwanted values in the computation and the overall tie complexity comes out to be O(N²) only. 

Both of these approaches do not require any extra space, so their space complexity is O(1).

In this way we have seen two approaches to solve the "Triplets with sum between given range" problem.