Count Good Triplets In An Array - Leetcode Solution

Problem Description:

Given an array nums of integers, return the number of good triplets.

A triplet (nums[i], nums[j], nums[k]) is called good if the following conditions are true:

1. 0 <= i < j < k < nums.length
2. |nums[i] - nums[j]| <= a
3. |nums[j] - nums[k]| <= b
4. |nums[i] - nums[k]| <= c

Where |x| denotes the absolute value of x

Solution:

We will use the brute force approach where we will try to find all the possible combinations of triplets present in the array and then verify if it satisfies the given conditions. We will use three nested loops to generate all the possible combinations of triplets.

For each triplet we will check if the given conditions are satisfied. If the conditions are true then we will increment the count otherwise we will continue to the next triplet combination.

Let us implement the code to solve the problem:

class Solution { public int countGoodTriplets(int[] nums, int a, int b, int c) { int n = nums.length; int count = 0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ if(Math.abs(nums[i] - nums[j]) <= a && Math.abs(nums[j] - nums[k]) <= b && Math.abs(nums[i] - nums[k]) <= c){ count++; } } } } return count; } }

Time complexity: O(n^3)

Space complexity: O(1)

Although this approach is a brute force approach, the time complexity of this approach is O(n^3) but it still passes all the test cases on LeetCode.

This concludes our solution for the problem.

1