Algorithm


Problem Name: Data Structures - Triplets

Problem Link: https://www.hackerrank.com/challenges/triplets/problem?isFullScreen=true

In this HackerRank in Data Structures - Triplets solutions,

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;
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor

#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();
    }
}
Copy The Code & Try With Live Editor

#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)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Subtrees And Paths solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Beautiful Segments solution in Hackerrank - Hacerrank solution C, C++, java,js, Python