Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/triplets/problem?isFullScreen=true
In this HackerRank in Data Structures -
There is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples ( d[i] < d[j] < d[k], i < j < k ) are present?
Input format
The first line contains an integer, N, denoting the number of elements in the array. This is followed by a single line, containing N space-separated integers. Please note that there are no leading spaces before the first number, and there are no trailing spaces after the last number.
Output format:
A single integer that denotes the number of distinct ascending triplets present in the array.
Constraints:
N <= 10**5
Every element of the array is present at most twice.
Every element of the array is a 32-bit non-negative integer.
Sample input:
6
1 1 2 2 3 4
Sample output:
4
Explanation
The distinct triplets are
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
The elements of the array might not be sorted. Make no assumptions of the same.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include<stdio.h>
#include<stdlib.h>
#define ll long long int
typedef struct _dInfo
{
unsigned int val;
int idx,sortedIdx,firstOcc,l,r,lastOcc;
}dInfo;
dInfo a[100005];
int tree[100005];
int compare(const void *a,const void *b)
{
dInfo *x1=(dInfo*)a;dInfo *x2=(dInfo*)b;
if((*x1).val<(*x2).val)return -1;
else if((*x1).val==(*x2).val &&
(*x1).idx < (*x2).idx)return -1;
return 1;
}
int compare1(const void *a,const void *b)
{
dInfo *x1=(dInfo*)a;dInfo *x2=(dInfo*)b;
if((*x1).idx < (*x2).idx)return -1;
return 1;
}
void update(int idx,int val,int maxIdx)
{
while(idx < =maxIdx)
{
tree[idx]+=val;
idx+=(idx & -idx);
}
}
int read(int idx>
{
int sum=0;
while(idx>0)
{
sum+=tree[idx];
idx-=(idx & -idx);
}
return sum;
}
int main()
{
int n,i,maxIdx;
ll triplets;
scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%u",&a[i].val);
a[i].idx=i;
}
qsort(a,n,sizeof(dInfo),&compare);
a[0].sortedIdx=1;
a[0].firstOcc=1;
for(i = 1; i < n; i++)
{
a[i].sortedIdx=(a[i].val==a[i-1].val)?
a[i-1].sortedIdx:a[i-1].sortedIdx+1;
a[i].firstOcc=(a[i].val==a[i-1].val)?0:1;
}
a[n-1].lastOcc=1;
for(i = n-2; i >= 0; i--)
{
a[i].lastOcc=(a[i].val==a[i+1].val)?0:1;
}
maxIdx=a[n-1].sortedIdx;
qsort(a,n,sizeof(dInfo),&compare1);
for(i = 0; i < = maxIdx; i++)
tree[i]=0;
for(i = 0; i < n; i++)
{
if(a[i].sortedIdx!=1)
a[i].l=read(a[i].sortedIdx-1);
else
a[i].l=0;
if(a[i].firstOcc)
{
update(a[i].sortedIdx,1,maxIdx);
}
}
for(i = 0; i <= maxIdx; i++)
tree[i]=0;
for(i = 0; i < n; i++>
a[i].sortedIdx=maxIdx+1-a[i].sortedIdx;
for(i = n-1; i >= 0; i--)
{
if(a[i].sortedIdx!=1)
a[i].r=read(a[i].sortedIdx-1);
else
a[i].r=0;
if(a[i].lastOcc)
update(a[i].sortedIdx,1,maxIdx);
}
qsort(a,n,sizeof(dInfo),&compare);
for(i = 0,triplets = 0; i < n; i++)
{
triplets=triplets+(ll)a[i].l*(ll)a[i].r;
if(a[i].val==a[i-1].val)
triplets=triplets-(ll)a[i-1].l*(ll)a[i].r;
}
printf("%lld\n",triplets>;
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
struct node{
node *left, *right, *parent;
int val, height, ownsize;
long long int size;
};
node* insert(node* root, int val, int size){
if(!root){
node *nn = new node;
nn->val = val;
nn->size = nn->ownsize = size;
nn->left = 0;
nn->right = 0;
return nn;
}
if(root->val == val){
if(size > root->ownsize){
root->size += size - root->ownsize;
root->ownsize = size;
}
}else if(root->val > val){
root->left = insert(root->left, val, size);
root->size = root->left->size + (root->right ? root->right->size : 0) + root->ownsize;
}else{
root->right = insert(root->right, val, size);
root->size = root->right->size + (root->left ? root->left->size : 0) + root->ownsize;
}
return root;
}
void inorder(node *root){
if(root){
inorder(root->left);
cout<<"["<<root->val<<","<<root->size<<"] ";
inorder(root->right);
}
}
int countLarger(node* root, int val){
if(root){
if(root->val < val>{
return countLarger(root->right, val);
}else if(root->val == val){
return root->right ? root->right->size : 0;
}else{
return countLarger(root->left, val) + root->size - (root->left ? root->left->size : 0);
}
}
return 0;
}
int main(){
int N, num;
cin>>N;
vector<int> nums;
vector<int> doublet(N, 0);
for(int i = 0; i < N; i++){
cin >> num;
nums.push_back(num>;
}
node root;
root.val = nums[N - 1];
root.height = 0;
root.size = 1;
root.ownsize = 1;
root.left = 0;
root.right = 0;
doublet[N - 1] = 0;
for(int i = N - 2; i >= 0; i--){
insert(&root, nums[i], 1);
doublet[i] = countLarger(&root, nums[i]);
}
root = node();
root.val = nums[N - 1];
root.height = 0;
root.size = 0;
root.ownsize = 0;
root.left = 0;
root.right = 0;
long long int sum = 0;
map < int, long long int> tri;
for(int i = N - 2; i >= 0; i--){
insert(&root, nums[i], doublet[i]);
tri[nums[i]] = countLarger(&root, nums[i]);
}
for(map < int, long long int>::iterator it = tri.begin(); it != tri.end(); it++){
sum += it->second;
}
cout << sum << endl;
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
public static class Triplets {
long[] lSmaller, rLarger, treeArray;
int[] dscArray, lFlags, rFlags;
int size, count = 0;
Triplets(int aSize, long[] inputArray) {
size = aSize;
lSmaller = new long[size];
rLarger = new long[size];
dscArray = new int[size];
long[] tmpArray = Arrays.copyOf(inputArray, inputArray.length);
Arrays.sort(tmpArray);
HashMap < Long, Integer> tmpMap = new HashMap<>(size);
for (int i = 0; i < size; i++) {
if (!tmpMap.containsKey(tmpArray[i])) {
count++;
tmpMap.put(tmpArray[i], count);
}
}
count++;
treeArray = new long[count];
lFlags = new int[count];
rFlags = new int[count];
for (int i = 0; i < size; i++) {
dscArray[i] = tmpMap.get(inputArray[i]);
}
}
void update(int idx) {
while (idx < count) {
treeArray[idx]++;
idx += (idx & -idx);
}
}
long read(int index) {
int sum = 0;
while (index > 0) {
sum += treeArray[index];
index -= (index & -index);
}
return sum;
}
void countLeftSmaller() {
Arrays.fill(treeArray, 0);
Arrays.fill(lSmaller, 0);
Arrays.fill(lFlags, 0);
for (int i = 0; i < size; i++) {
int val = dscArray[i];
lSmaller[i] = read(val - 1);
if (lFlags[val] == 0) {
update(val);
lFlags[val] = i + 1;
} else {
lSmaller[i] -= lSmaller[lFlags[val] - 1];
}
}
}
void countRightLarger() {
Arrays.fill(treeArray, 0);
Arrays.fill(rLarger, 0);
Arrays.fill(rFlags, 0);
for (int i = size - 1; i >= 0; i--) {
int val = dscArray[i];
rLarger[i] = read(count - 1) - read(val);
if (rFlags[val] == 0) {
update(val);
rFlags[val] = i + 1;
}
}
}
long countTriplets() {
long sum = 0;
for (int i = 0; i < size; i++) {
sum += lSmaller[i] * rLarger[i];
}
return sum;
}
}
// Complete the solve function below.
static long solve(long[] d) {
int n = d.length;
Triplets sol = new Triplets(n, d);
sol.countLeftSmaller();
sol.countRightLarger();
return sol.countTriplets();
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int dCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
long[] d = new long[dCount];
String[] dItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int dItr = 0; dItr < dCount; dItr++) {
long dItem = Long.parseLong(dItems[dItr]);
d[dItr] = dItem;
}
long result = solve(d);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
#4 Code Example with Python Programming
Code -
Python Programming
root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level*2 + 1)]
tree_2 = [0 for i in range(last_level*2 + 1)]
tri = [0 for i in range(100048)]
#zle jest, tzn kod a nie ogolnie
def less_than(x, tab):
index = root
sum = 0
c_level = last_level
while(index < x+last_level):
if x < c_level // 2:
index *= 2
else:
index *= 2
sum += tab[index]
index += 1
x -= (c_level//2)
# print(x)
# print(c_level)
c_level //= 2
return sum
def add_elem_1(x):
tree = tree_1
index = x + last_level
tree[index] = 1
index //=2
while index > 0:
tree[index] = tree[2*index] + tree[2*index + 1]
index //=2
def add_elem_2(x):
tree = tree_2
index = x + last_level
tree[index] = less_than(x, tree_1)
index //=2
while index > 0:
tree[index] = tree[2*index] + tree[2*index + 1]
index //=2
n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]
for i in input_array:
add_elem_1(i)
add_elem_2(i)
# print(less_than(i, tree_2))
# print(less_than(100, tree_1), less_than(100,tree_2))
tri[i] = less_than(i, tree_2)
sum = 0
for i in tri:
sum += i
print(sum)