HackerRank Favorite sequence problem solution

In this HackerRank Favorite sequence problem solution In the input, there are N sequences of natural numbers representing the N copies of the sequence M after Mary’s prank. In each of them, all numbers are distinct. Your task is to construct the shortest sequence S that might have been the original M. If there are many such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.

Problem solution in Python.

# Enter your code here. Read input from STDIN. Print output to STDOUT

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import defaultdict, deque
import bisect

class Graph:
    def __init__(self, vertices, graph=defaultdict(list), in_coming=defaultdict(int)):
        self.V = vertices  # No. of vertices
        self.graph = graph  # dictionary containing adjacency List
        self.in_coming = in_coming
        self.n = len(vertices)
        # print(self.V)
        # print(self.graph)

    def recursion(self, node, visited, res):
        visited[node] = True
        for c in self.graph[node]:
            if not visited[c]:
                self.recursion(c, visited, res)
        res.append(node)
        
        
    def topological_sort(self):
        res = []
        # temp_mark = [False] * self.n
        visited = {node: False for node in self.V}
        for node in self.V:
            if not visited[node]:
                self.recursion(node, visited, res)
                # visited[i] = True                  
        # res.append(self.V[i])
        return res[::-1]
    
    def kahn_algo(self):
        res = []
        s = deque([node for node in self.V if node not in self.in_coming])
        while len(s):
            node = s.popleft()
            res.append(node)
            c_list = self.graph[node]
            while len(c_list):
                c = c_list.pop()
                self.in_coming[c] -= 1
                if self.in_coming[c] == 0:
                    bisect.insort(s, c)
        return res
                

def favourite_sequence(n, copies):
    # Write your code here
    edges = defaultdict(list)
    in_coming = defaultdict(int)
    nodes = set()
    # in_coming = set()
    for c_list in copies:
        k = len(c_list)
        # in_coming = in_coming.union(set(c_list[1:]))
        nodes = nodes.union(set(c_list))
        for i in range(k-1):
            edges[c_list[i]].append(c_list[i+1])
            in_coming[c_list[i+1]] += 1
            
    # no_coming = nodes.difference(in_coming)
    # no_coming = sorted(list(no_coming))
    nodes = sorted(list(nodes)) # reverse=True
    for node in edges.keys():
        edges[node].sort(reverse=True) # reverse=True
        
    g = Graph(nodes, edges, in_coming)
    # res = g.topological_sort()
    res = g.kahn_algo()
    return res

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    copies = []
    
    for t_itr in range(n):
        
        k = int(input())
        
        copies.append(list(map(int, input().rstrip().split())))


    result = favourite_sequence(n, copies)

    fptr.write(' '.join(map(str, result)))
    # fptr.write('n')

    fptr.close()

Problem solution in Java.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.TreeSet;

public class Solution {
    public static final int MAXN = 1000000;
        public static void main(String[] args) {
                int[] cnt = new int[MAXN+1];
                int[] pcnt = new int[MAXN+1];
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
                TreeSet<Integer> tree = new TreeSet<Integer>();
                Scanner sc = new Scanner(System.in);
                int N = sc.nextInt();
                int[][] A = new int[N][];
                int pnum = 0;
                int mp = 0;
                for (int i = 0; i < N; ++i) {
                        int M = sc.nextInt();
                        int[] AM = new int[M];
                        A[i] = AM;
                        pnum = 0;
                        for (int j = 0; j < M; ++j) {
                                cnt[pnum] += 1;
                                pnum = sc.nextInt();
                                AM[j] = pnum;
                                pcnt[pnum]++;
                                if (pnum > mp) {
                                        mp = pnum;
                                }
                        }
                }
                int[][] B = new int[mp + 1][];
                B[0] = new int[N];
                int[] BP = new int[mp + 1];
                for (int i = 0; i <= mp; ++i) {
                        B[i] = new int[cnt[i]];
                }
                
                for (int i = 0; i < N; ++i) {
                        int M = A[i].length;
                        int[] AM = A[i];
                        pnum = 0;
                        int[] Bpnum = B[pnum];
                        for (int j = 0; j < M; ++j) {
                                int AMj = AM[j];
                                Bpnum[BP[pnum]++] = AMj;
                                pnum = AMj;
                                Bpnum = B[pnum];
                        }
                }
                
                for(int i=0;i<B[0].length;++i) {
                        pcnt[B[0][i]]--;
                }
                
                for (int i = 1; i <= mp; ++i) {
                        if(cnt[i]>0 || pcnt[i]>0) {
                                tree.add((i - 1) + pcnt[i] * MAXN);
                        }
                }                
                
                try {
                        boolean first = true;
                        while (true) {
                                Integer t = tree.pollFirst();
                                if (t == null) {
                                        break;
                                }
                                int tv = t % MAXN + 1;
                                if(first) {
                                        first = false;
                                }else {
                                        bw.write(' ');
                                }
                                bw.write(Integer.toString(tv));
                                int[] Btv = B[tv];
                                for (int i = 0; i < Btv.length; ++i) {
                                        assert(pcnt[Btv[i]]>0);
                                        tree.remove((Btv[i] - 1) + (pcnt[Btv[i]]--) * MAXN);
                                        tree.add((Btv[i] - 1) + (pcnt[Btv[i]]) * MAXN);
                                }
                        }
                } catch (IOException e) {
                }finally {
                        try {
                                bw.close();
                        } catch (IOException e) {
                                e.printStackTrace();
                        }
                }
        }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

int main() {
    set<int> s;
    map<int, vector<int> > g;
    map<int, int> c;
    
    int n, k;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> k;
        int tmp, past;
        cin >> tmp;
        past = tmp;
        c[tmp];
        for(int j = 1; j < k; ++j){
            cin >> tmp;
            g[past].push_back(tmp);
            c[tmp]++;
            //cout << past << " " << tmp << " " << c[tmp] << endl;
            past = tmp;
        }
    }
    
    for (std::map<int,int>::iterator it=c.begin(); it!=c.end(); ++it){
        //cout << it -> first << " " << it->second << endl;
        if(it->second == 0)
            s.insert(it->first);
    }
    vector<int> ans;

    while(!s.empty()){
        int curr = *(s.begin());
        ans.push_back(curr);
        s.erase(curr);
        
        for(int i = 0; i < g[curr].size(); ++i){
            c[g[curr][i]]--;
            if(c[g[curr][i]] == 0)
                s.insert(g[curr][i]);
        }
    }
    for(int i =0; i < ans.size(); ++i){
        if(i != 0)
            cout << " ";
        cout << ans[i];
    }
}

Problem solution in C.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct node
{
    int val;
    struct node* next;
}node;

node* a[100010]; 
int h[1000010],f[1000010],g[1000010],b[1000010],len,d[1000010],e[1000010];

void swap(int e,int f)
{
    int temp=b[e];
    b[e]=b[f];
    b[f]=temp;
}

node* Insert(node *head,int val)
{
    node* temp;
    temp=(node*)malloc(sizeof(node*));
    temp->val=val;
    temp->next=NULL;
    if(head==NULL)
    {
        head=temp;
        return head;
    }
    temp->next=head;
    return temp;
}

void shift_up(int idx)
{
    if(idx/2<1)
        return;
    if(b[idx]<b[idx/2])
    {
        swap(idx,idx/2);
        shift_up(idx/2);
    }
    return;
}

void shift_down(int idx)
{
    int lc=2*idx,rc=2*idx+1;
    if(lc>len)
        return;
    if(lc==len)
    {
        if(b[idx]>b[len])
            swap(idx,len);
        return;
    }
    if(b[lc]<=b[rc] && b[lc]<b[idx])
    {
        swap(lc,idx);
        shift_down(lc);
    }
    else if(b[rc]<=b[lc] && b[rc]<b[idx])
    {
        swap(rc,idx);
        shift_down(rc);
    }
    return;
}

void insert(int x)
{
    len++;
    b[len]=x;
    shift_up(len);
    return;
}

void delete()
{
    swap(1,len);
    len--;
    shift_down(1);
    return;
} 

int main()
{
    node* temp;
    int x,n,i,l=1,r;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&x,&g[1]);
        h[g[1]]=1;
        for(i=2;i<=x;i++)
        {
            scanf("%d",&g[i]);
            a[g[i-1]]=Insert(a[g[i-1]],g[i]);
            d[g[i]]++;
            h[g[i]]=1;
        }
    }
    for(i=1;i<=1000000;i++)
        if(h[i]==1 && d[i]==0)
            insert(i);
    while(len>0)
    {
        r=0;
        temp=a[b[1]];
        while(temp!=NULL)
        {
            x=temp->val;
            d[x]--;
            if(d[x]==0)
                f[r++]=x;
            temp=temp->next;
        }
        e[l++]=b[1];
        delete();
        for(i=0;i<r;i++)
            insert(f[i]);
    }
    for(i=1;i<l;i++)
        printf("%d ",e[i]);
    printf("n");
    return 0;
}