• Register
248 points
3
Hello reader, Welcome to my post:)

In this post, we shall be discussing the algorithm for finding a triplet whose value would be equal to a given sum. Although there are many ways to find the triplet, we would be discussing in detail about the approach which utilises hash based collection to find the triplet. 

 

Problem statement:

We shall begin by explaining the requirement of the problem statement without neglecting any of the details. Assume that the problem statement gives us an array of integers, from which we have to arrive at one or more triplets whose sum would be equal to the given sum. The triplets can be explained as three integers which may be contiguous or non-contiguous inside the array, which when added together sums up to the given value. The array can contain both negative and non negative integers. The naive way of finding the triplet values is by using three “nested for” loops, each loop starting from the consecutive elements present inside the array. Once when we arrive at the sum of the respective three values inside the loop, the value would be compared with the given sum value. If they are found equal, a triplet is found. Even though this naive approach works well, the time complexity it takes in order to find the triplets comes up to be N^3. We can reduce the time complexity of the algorithm by adopting either the two pointer approach or the hash based approach which subsequently reduces the time complexity to N^2. 

 

How to use the hash based approach for finding triplets:

Using a hash based approach reduces time complexity and it is a relatively simpler approach compared to the naive and the two pointer approaches. To begin with, the hash based approach leverages two “for” loops for accomplishing its function. The outer loop starts from the start of the array (let say i) and iterates upto the end of the array. Whereas the inner loop starts from the subsequent element in the array (j =i+1) and iterates upto the end of the array. We declare a hash map or a hash set (any of the two can be used) inside the outer loop. Now, how does a hashmap help to eliminate the other third loop? Well, this can be explained in such a way that we tend to subtract the outer loop value and as well as the inner loop value from the given sum, and then we tend to check whether the resultant value would be present inside the hash collection. In case if the hash collection contains the value, we can confirm that there exists a triplet. The hash collection gets its input feed inside the inner loop. The below code snippet explains how the hash map can be used in order to find one or more triplet values present inside the array.

public void findTriplet(int[] arr, int sum) {

	int size = arr.size();

	for (int i=0; i<size-2; i++) {

		Map<Integer> s = new HashMap<Integer>();
		int checkSum = sum-a[i];

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

			if(s.contains(checkSum-a[j]) {

				System.out.println(“triplet is found. The values are ” + checkSum, a[i], a[j]);

			}
		
		s.add(a[j]);

		}

	}



}

Although the hash based approach reduces the time complexity, it introduces an additional space for the hash map.

Thus we have come to the end of this post. Hope you found this post informative. Please do share in case you have any comments.

Thanks for reading :)

1 Comment

Please write more on this topic. Your explanation skill is amazing.