1534. Count Good Triplets
Problem Description
In this problem, we are provided with an array of integers arr
and three separate integers a
, b
, and c
. Our goal is to determine how many triplets (arr[i], arr[j], arr[k])
meet certain criteria, where i
, j
, and k
are distinct indices into the array with i < j < k
.
A triplet is considered "good" if it satisfies the following conditions:
- The absolute difference between
arr[i]
andarr[j]
is less than or equal toa
. - The absolute difference between
arr[j]
andarr[k]
is less than or equal tob
. - The absolute difference between
arr[i]
andarr[k]
is less than or equal toc
.
The problem asks us to return the total number of these good triplets.
Intuition
The straightforward way to find all good triplets is to check every possible triplet in the array to see if it meets the criteria. This involves using three nested loops to generate all possible combinations of i
, j
, and k
where 0 <= i < j < k < arr.length
.
Within these loops, we will calculate the absolute differences between arr[i]
, arr[j]
, and arr[k]
and check if they satisfy the conditions related to a
, b
, and c
. If a triplet satisfies all these conditions, we increment a counter.
This method is a brute-force approach since it explores all possible triplets without any optimizations. It ensures that all triplets are checked and counted correctly, albeit at the expense of potentially higher computational time, especially for large arrays.
Solution Approach
The implementation of the solution provided in the reference code uses the brute-force approach, which is a common pattern when dealing with problems that require us to explore all possible combinations of elements to find a particular set that satisfies certain conditions.
Algorithm steps:
- Initialize a counter
ans
to keep track of the number of good triplets found. - Calculate the length
n
of the input arrayarr
. - Iterate over the array with the first pointer
i
, which runs from the beginning of the array to the third-to-last element. - For each
i
, iterate with the second pointerj
, which runs from one element afteri
to the second-to-last element. - For each
j
, iterate with the third pointerk
, which runs from one element afterj
to the last element. - Inside the innermost loop (where
k
is iterating), check if the current triplet(arr[i], arr[j], arr[k])
is a good triplet by verifying the three conditions with the givena
,b
, andc
:abs(arr[i] - arr[j]) <= a
abs(arr[j] - arr[k]) <= b
abs(arr[i] - arr[k]) <= c
- If all three conditions are satisfied, increment the counter
ans
. - After all iterations are complete, return the value of
ans
.
This approach does not use any specific data structures or complex algorithms, but rather relies on nested loops to examine each triplet one by one. The only operations involved are arithmetic operations (-
and abs
) and simple comparisons (<=
).
While it is an exhaustive solution, it is not the most efficient in terms of time complexity. The time complexity of this approach is O(n^3)
, as there are three nested loops each iterating over the array. This solution can be quite slow for larger arrays but is perfectly fine for smaller input sizes where a more sophisticated algorithm might not lead to significant improvements in runtime or when fast and simple programming is required over an optimized, complex solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose we have the following:
arr = [2, 1, 3]
a = 1
b = 1
c = 1
Now we want to find the number of good triplets that satisfy all the given conditions.
We start by initializing our counter ans
to 0. Our array length n
is 3.
- We begin iterating with pointer
i
starting at 0. - For
i = 0
(arr[i] = 2
), we move on to pointerj
. - We let
j
iterate starting fromi + 1
, which is 1. - For
j = 1
(arr[j] = 1
), we then use pointerk
. k
starts iterating fromj + 1
, which is 2.- For
k = 2
(arr[k] = 3
), we now check if(arr[i], arr[j], arr[k]) = (2, 1, 3)
is a good triplet.- The absolute difference between
arr[i]
andarr[j]
is|2 - 1| = 1
, which is less than or equal toa
. - The absolute difference between
arr[j]
andarr[k]
is|1 - 3| = 2
, so this is not less than or equal tob
and we can ignore this triplet.
- The absolute difference between
Since there are no other combinations to check, our count ans
stays at 0. We conclude that there are no good triplets in the array [2, 1, 3]
with the given a
, b
, and c
values.
Applying the same approach in a larger array would involve more iterations, but the steps would be similar: iterate over each potential triplet and check if they satisfy the conditions.
Solution Implementation
1from typing import List # Import List from typing module for type annotations.
2
3class Solution:
4 def count_good_triplets(self, arr: List[int], a: int, b: int, c: int) -> int:
5 # Initialize the count of good triplets.
6 good_triplets_count = 0
7
8 # Get the length of the array.
9 array_length = len(arr)
10
11 # Iterate through each element of the array for the first element of the triplet.
12 for first_index in range(array_length):
13 # For the second element, start from the next index of the first element.
14 for second_index in range(first_index + 1, array_length):
15 # For the third element, start from the next index of the second element.
16 for third_index in range(second_index + 1, array_length):
17 # Check if the current triplet (arr[first_index], arr[second_index], arr[third_index])
18 # is a good triplet based on the provided conditions.
19 is_good_triplet = (
20 abs(arr[first_index] - arr[second_index]) <= a and
21 abs(arr[second_index] - arr[third_index]) <= b and
22 abs(arr[first_index] - arr[third_index]) <= c
23 )
24 # If it is a good triplet, increment the good_triplets_count.
25 good_triplets_count += is_good_triplet
26
27 # After checking all possible triplets, return the total count of good triplets.
28 return good_triplets_count
29
1class Solution {
2 public int countGoodTriplets(int[] arr, int maxDiffAB, int maxDiffBC, int maxDiffAC) {
3 // The length of the input array
4 int arrayLength = arr.length;
5 // Counter to keep track of the number of "good" triplets
6 int goodTripletsCount = 0;
7
8 // Loop over each element for the first value of the triplet
9 for (int i = 0; i < arrayLength; ++i) {
10 // Loop over each element after the first value for the second value of the triplet
11 for (int j = i + 1; j < arrayLength; ++j) {
12 // Loop over each element after the second value for the third value of the triplet
13 for (int k = j + 1; k < arrayLength; ++k) {
14 // Check the conditions to determine if the triplet (arr[i], arr[j], arr[k]) is "good"
15 if (Math.abs(arr[i] - arr[j]) <= maxDiffAB && // Condition for the difference between arr[i] and arr[j]
16 Math.abs(arr[j] - arr[k]) <= maxDiffBC && // Condition for the difference between arr[j] and arr[k]
17 Math.abs(arr[i] - arr[k]) <= maxDiffAC) { // Condition for the difference between arr[i] and arr[k]
18 // If all conditions are met, increment the count of "good" triplets
19 ++goodTripletsCount;
20 }
21 }
22 }
23 }
24 // Return the total number of "good" triplets found
25 return goodTripletsCount;
26 }
27}
28
1class Solution {
2public:
3 int countGoodTriplets(vector<int>& numbers, int limitA, int limitB, int limitC) {
4 int size = numbers.size(); // Size of the input array
5 int goodTripletsCount = 0; // Initialize count of good triplets
6
7 // Iterate over all possible triplets
8 for (int i = 0; i < size; ++i) {
9 for (int j = i + 1; j < size; ++j) {
10 // Check if the first condition is met to avoid unnecessary computations
11 if (abs(numbers[i] - numbers[j]) <= limitA) {
12 for (int k = j + 1; k < size; ++k) {
13 // accumulate 1 to the count if all three conditions are satisfied
14 goodTripletsCount += (abs(numbers[i] - numbers[j]) <= limitA &&
15 abs(numbers[j] - numbers[k]) <= limitB &&
16 abs(numbers[i] - numbers[k]) <= limitC) ? 1 : 0;
17 }
18 }
19 }
20 }
21 // Return the total count of good triplets
22 return goodTripletsCount;
23 }
24};
25
1// Define the function to count good triplets
2function countGoodTriplets(numbers: number[], limitA: number, limitB: number, limitC: number): number {
3 let size = numbers.length; // Size of the input array
4 let goodTripletsCount = 0; // Initialize count of good triplets
5
6 // Iterate over all possible triplets
7 for (let i = 0; i < size; ++i) {
8 for (let j = i + 1; j < size; ++j) {
9 // Check if the first condition is met to avoid unnecessary computations
10 if (Math.abs(numbers[i] - numbers[j]) <= limitA) {
11 for (let k = j + 1; k < size; ++k) {
12 // Increment the count if all three conditions are satisfied
13 goodTripletsCount += (Math.abs(numbers[i] - numbers[j]) <= limitA &&
14 Math.abs(numbers[j] - numbers[k]) <= limitB &&
15 Math.abs(numbers[i] - numbers[k]) <= limitC) ? 1 : 0;
16 }
17 }
18 }
19 }
20 // Return the total count of good triplets
21 return goodTripletsCount;
22}
23
Time and Space Complexity
The given Python code implements a function to count the number of good triplets in an array. A triplet (arr[i], arr[j], arr[k])
is considered good if it satisfies all of the following conditions:
0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
Where |x - y|
denotes the absolute value of the difference between x
and y
.
Time Complexity
The time complexity of the function is determined by the three nested for-loops. The outermost loop runs n
times, where n
is the length of the array. The middle loop runs up to n-1
times, and the innermost loop runs up to n-2
times. Therefore, the total number of iterations is governed by the series of descending integers starting from n
and decreasing to 1.
The time complexity can then be calculated as the sum of the series Ī£(i * (i-1) / 2)
, for i
from 1
to n-2
. This simplifies to O(n^3)
since the loop counters are independent and the series is a sum of cubic numbers.
Space Complexity
The space complexity of the solution is O(1)
. Other than the input array, only a fixed number of integer variables (ans
, n
, i
, j
, k
) are used, and their number does not depend on the input size n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!