Problem Statement
Given an array of size n, a triplet (a[i], a[j], a[k]) is called a Magic Triplet if a[i] < a[j] < a[k] and i < j < k. Count the number of magic triplets in a given array.
Problem statement: https://practice.geeksforgeeks.org/problems/magic-triplets4003/1
Example 1:
Input: arr = [3, 2, 1]
Output: 0
Explanation: There is no magic triplet.
Example 2:
Input: arr = [1, 2, 3, 4]
Output: 4
Explanation: Fours magic triplets are
(1, 2, 3), (1, 2, 4), (1, 3, 4) and
(2, 3, 4).
Approach
Example
[1, 2, 3] -> 1
1,2,3
[1, 2, 3, 4] -> 4
1,2,3
1,2,4
1,3,4
2,3,4
So Naive Solution can be via approaching all 3 variables independently.
Like,
for i in [0, n]:
first_number = a[i] # first number
for j in [i+1, n]:
if a[j] > first_number:
second_number = a[j] # second number
for k in [j+1, n]:
if a[k] > second_number:
third_number = a[k]
overall_count += 1 # as we got all three numbers
This as we could see costs us O(N3) time complexity
Could we avoid it,
Yes, we could.
We do not need to display all three numbers, we just wanted to count such triplets. Let's think this way, if we got first_number and then second_number we just wanted to know how many numbers are next to second_number which are greater than second_number.
For this, we need to have a pre-iteration of the list to know how many numbers next to the current are greater in value, let's call this array as lookupTable.
Know how to generate the lookup table.
Once we got lookupTable we just need to find the first two numbers and for the second number need to look into the lookup table.
class Solution {
private int[] generateLookupTable(int[] a) {
int[] res = new int[a.length]; // result array
// for every element
for (int i = 0; i < a.length; i++) {
int count = 0;
for (int j = i+1; j < a.length; j++) {
// previous value is lesser than new value
if (a[i] < a[j])
count++;
}
res[i] = count;
}
return res;
}
public int countTriplets(int[] a) {
final int[] lookupTable = generateLookupTable(a);
int res = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] < a[j])
res += lookupTable[j];
}
}
return res;
}
}
Top comments (0)