Timeout Error in Fraudulent Activity Notification HackerRank

Question

I am solving this problem: Farudulent Activity Notification on HackerRank. I am done with my code and is working, but it is inefficient as well for very large inputs.

I don't know but after all my efforts, I am able to give out good solution to a problem of a MEDIUM LEVEL but this timeout error happens every time for very large inputs. I have tried optimizing my code and still I get timeout errors. My agendas for this question and upcoming questions are:

• How to put efficiency for very large inputs. What kind of intellect it requires.
• How to reach to that level. What should I prepare for this.
• Code optimization

I am open to learning, and I am really desperate to learn how to write a more advanced and optimized code to make myself better. I am open to do hard work.

My Algorithm:

1. For this problem we must go from incrementing variable i till len(givenArray)-d
2. Take a variable for the next variable to be compared, my case iterate is the variable
3. Pass the values to the particular array to the method for counting countFraud()
4. Add it to the count variable
5. Increment iterate variable

Code:

# this is for counting the trailing array
def countFraud(arr, nextNum):
    count = 0
    median = 0.0
    d = len(arr)
    #for calculating the median correctly
    arr.sort()
    if d%2 != 0:
        median = arr[int(d/2)]
    else:
        n = int(d/2)
        median = (arr[n] + arr[n-1]) / 2

    #now the opeartion for count from the array
    if nextNum >= 2*median: count += 1
    return count

# Complete the activityNotifications function below.
def activityNotifications(expenditure, d):
    count = 0
    iterate = d
    # it will go upto the len of array - d, so that it will go upto the d length
    # leaving the last element everytime for the comparision
    for i in range(len(expenditure)-d):
        count += countFraud(expenditure[i:iterate], expenditure[iterate])
        iterate += 1
    return count

Now previously I was doing two loops, adding the items to the new_array and passing it to the the countFraud(). But now I have optimized it and made it sort of O(N).

I don't know but this code is not getting submitted for all TCs due to Timeout Error. There is no problem in operation part. It is just with the efficiency of the code.

Timeout Error Input Example:

200000 10000

Link for input - Input Data

Expected Output:

633

I have read upon this article: HackerRank Environment to learn about the timing issue. For Python/Python 3 it is 10 seconds. My code is definitely taking more than that for values greater than 10^3 or 4.

My code has successfully passed 3 TCs though. Please help. Thank You :)

Vacuva

Answer 1

Since nobody actually gave me the answer. I really have to look to the solution in the leaderboard. I found every solution too much to assimilate, just one solution to be a good one.

Disclaimer: This is some advanced coding technique so you need to have a better understanding of the language before you proceed with the solution.

The Solution's algo:

1. This takes two arrays, one is t having total number of array elem and other one let us name it as listD just the first d elements in the sorted manner
2. A function to return the median value with the list containing first d elements
3. With the loop starting from the d and going till n-1, if t[i] >= 2*median(): increment var noti
4. Remove the first element from the listD using PYTHON BISECT ALGORITHM and add it the t[i] to the listD using PYTHON INSORT ALGORITHM in sorted manner
5. Return noti

Code:

from bisect import bisect_left, insort_left

n, d = map(int, input().split())
t = list(map(int, input().split()))
noti = 0

listD = sorted(t[:d])

def median():
  return listD[d//2] if d%2 == 1 else ((listD[d//2] + listD[d//2-1])/2)

for i in range(d,n):
  if t[i] >= 2*median(): noti += 1
  del listD[bisect_left(listD, t[i-d])]
  insort_left(listD, t[i])
print(noti)

Here, we've used BISECT and INSORT, what they do is basically, return the position of the element to be added and returns the sorted list after adding the elements. So the headache of sorting the array again and again is reduced, hence the time complexity is reduced and solves all the test cases.

You can read about it here: Python Bisect and Insort Algo. Thanks, and hope it helps some one in future.

Vacuva

Answer 2

Similarly to what you were doing, this approach uses two functions: one for the activity notifications and another to find the median.

Finding the median is easy. The approach used was to check if the lookback days for median spending, d, is odd or even and, based on that information, calculate accordingly.

Then, when it comes to activityNotifications, the key point was to know that expenditure[i] is between 0 and 200, including both numbers (201).

All in all

def findMedian(counter, d):
    count = 0
    median = 0

    if d%2 != 0:
        for i in range(len(counter)):
            count += counter[i]

            if count > d//2:
                median = i
                break
            
    else:
        first = 0
        second = 0

        for i, _ in enumerate(counter):
            count += counter[i]
            
            if first == 0 and count >= d//2:
                first = i
                
            if second == 0 and count >= d//2 + 1:
                second = i
                break
            
        median = (first+second) / 2
        
    return median


def activityNotifications(expenditure, d):
    count = 0
    counter = [0]*201
    
    for exp in range(d):
        counter[expenditure[exp]] += 1

    for i in range(d, len(expenditure)):
        new = expenditure[i]
        old = expenditure[i-d]
        median = findMedian(counter, d)
        
        if new >= 2*median:
            count += 1
            
        counter[old] -= 1
        counter[new] += 1
        
    return count

This will pass all the current 8 Test cases in HackerRank

Sources of inspiration:

• https://www.snoopybox.co.kr/1823
• https://sungjun221.github.io/algorithm/fraudulent-activity-notifications/

---

Note that there's also a great answer in Code Review using pandas. While it is very interesting take to solve the problem, it won't work in HackerRank

import pandas as pd

def activityNotifications(expenditure, d):
    df = pd.DataFrame(expenditure)
    return (df.shift(-1) > 2 * df.rolling(d).median())[0].sum()

Bimolecular

thanks, I like this solution without pandas. It helps me understand the solution. This kind of code helps us to improve our way of thinking, so for me, it's better to solve it without additional libraries other than the built-in ones – Sonorous

Answer 3

This one passed all test cases:-

    public static double findMedian(int a[]) {
        int n = a.length;
        if (n % 2 != 0)
            return (double) a[n / 2];

        return (double) (a[(n - 1) / 2] + a[n / 2]) / 2.0;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int activityNotifications(int[] expenditure, int d) {
        if (d >= expenditure.length) return 0;

        int numNotifications = 0;
        int[] trailingArr = new int[d];
        for (int i = 0; i < trailingArr.length; i++) {
            trailingArr[i] = expenditure[i];
        }
        Arrays.sort(trailingArr);
        for (int i = d; i < expenditure.length; i++) {
            double median = findMedian(trailingArr);
            if (expenditure[i] >= 2.0 * median) {
                numNotifications += 1;
            }
            int nextToRemoveElement = expenditure[i - d];
            int toInsertElement = expenditure[i];
            adjustTrailingArray(trailingArr, nextToRemoveElement, toInsertElement);
        }
        return numNotifications;
    }

    //This whole thing is O(d) time. Note that we are not sorting again as trailing array was already sorted
    // as preprocessing and now only one new element has to find its position in sorted array.

    private static void adjustTrailingArray(int[] trailingArr, int elementToRemove, int elementToInsert) {
        if (elementToInsert == elementToRemove) return;
        int foundIndex = 0;

        //The first element of unsorted trailing array will move out of the sliding window
        //Since the trailing array was sorted by us, we have lost the position of its first element in original array.
        //Hence, I search linearly for it and replace it with the new element.

        while (foundIndex < trailingArr.length) {
            if (trailingArr[foundIndex] != elementToRemove) {
                foundIndex++;
            } else {
                trailingArr[foundIndex] = elementToInsert;
                break;
            }
        }

        //Now we bubble the new element just inserted using bubble sort to left/right based on whether it was bigger
        //or smaller than the element that got removed.

        if (elementToInsert > elementToRemove) {
            int i = foundIndex;
            while (i < trailingArr.length - 1) {
                if (trailingArr[i] > trailingArr[i + 1]) {
                    swap(trailingArr, i, i + 1);
                    i += 1;
                } else break;
            }
        } else {
            int i = foundIndex;
            while (i > 0) {
                if (trailingArr[i] < trailingArr[i - 1]) {
                    swap(trailingArr, i, i - 1);
                    i -= 1;
                } else break;
            }
        }
    }

Discriminative

Answer 4

I don't know why no one mentioned Median of medians algorithm, whose complexity of finding a median from an array is O(n) and its irrelevant of the order of the array.

Quench

Answer 5

We can use counting sort technique here. The tricky thing here is that we cannot sort the entire range here every time we shift our range forward as this will increase the time complexity, instead, we should only modify the frequency array and then we can find the median simply summing the frequencies from the start of the range till sum becomes greater or equal to d/2.

An important point to note here: Median for odd and even 'd' differs slightly.

int median(int arr[], int d)
{
    int med;
    
    int sum = 0;
    for(int i = 0; i <= 200; i++)
    {
        sum = sum + arr[i];
        if(sum>=d)
        {
            med = i;
            break;
        }
    }
    return med;
}

int activityNotifications(vector<int> expenditure, int d) {
    int count  = 0;
    int n = expenditure.size();
    if(n==d)
    {
        return 0;
    }
    int temp[201]={0};
    for(int i = 0; i < d; i++)
    {
        temp[expenditure[i]]++;
    }
    
    int med = median(temp, d/2+d%2);
    for(int i = d; i < n; i++)
    {
        if(d%2==0)
        {
            int temp_med = median(temp, d/2+1);
            if(expenditure[i]>=med+temp_med)
            {
                count++;
            }
        }
        else
        {
            if(expenditure[i]>=med*2)
            {
                count++;
            }
        }
        
        temp[expenditure[i-d]]--;
        temp[expenditure[i]]++;
        med = median(temp,d/2+d%2);
    }
    return count;
}

Gaines

Answer 6

much simpler

1. for the very first window sort it - which takes O(dlog(d))

2. since its already sorted we can take advantage of this, for every next window just replace the new-incoming number into window with the number that is leaving the window and sort its correct position from there - which takes - O(d)

total complexity O(dlog(d) + (n-d-1)*(d)) = O(nd)

sorry if code looks bit messy

static int activityNotifications(int[] expenditure, int d) {
    int count = 0;
    int days = expenditure.length;
    int[]tempArr = Arrays.copyOfRange(expenditure,0,d);
    Arrays.sort(tempArr);//

    for(int i=0;d+i<days;i++){
        
       if(i>0 ){
      //rearrange them based on outgoing and incoming into the window
       int outgo = expenditure[i-1];
       int income = expenditure[i+d-1];
       rearrange(outgo,income,tempArr);}

    //get medain
     float median;
     int size= d;
     if(size%2==0){
        int mid = size/2;
       median = (float)(tempArr[mid-1]+tempArr[mid])/2;          
     }
    else{
        median = tempArr[size/2];
    }
   
    //checking notification         

        if(expenditure[d+i]>=2*median){
            count++;
        }

    }
return count;
}


  public static void rearrange(int outgo,int income,int[]arr){
  
  int len = arr.length;
  int i=0;
  for( i=0;i<len;i++){
      if(arr[i]==outgo){
          arr[i]=income;
          break;
      }          
  }
  

if(i==0){        
 if(arr[i+1]>=income){return;}
 else{
      while(i+1<len  && arr[i+1]<income){
         arr[i]=arr[i+1];
         i++;
     }
     arr[i]=income;
 }
}
else if(i==len-1){
    if(arr[i-1]<=income){return;}
 else{
     while( i>=1 & arr[i-1]>income ){
         arr[i]=arr[i-1];
         i--;
     }
     arr[i]=income;
 }
 }


else{
    if(arr[i+1]<income){
         while(i+1<len  && arr[i+1]<income){
         arr[i]=arr[i+1];
         i++;
     }
     arr[i]=income;
    }
     if(arr[i-1]>income){

         while( i>=1 && arr[i-1]>income ){
         arr[i]=arr[i-1];
         i--;
     }
     arr[i]=income;            
    }
}

Truncated

Answer 7

I have spend a lot of time on this question and have come up with a new algorithm of my own and its also giving Time Limit Exceeded (TLE) and only passed three test cases.

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstring>
using namespace std;
int maxlen=1,minlen=1,heapsize;
double median=0,ct=0;
void min_heapify(double arr[],int i)
{
    int l=(2*i);
    int r=(2*i+1);
    int smallest;
    if(l<=heapsize && arr[l]<arr[i])
    {
        smallest=l;
    }
    else
    {
        smallest=i;
    }
    if(r<=heapsize && arr[r]<arr[smallest])
    {
        smallest=r;
    }
    if(smallest==i)
        return;
    if(smallest!=i)
    {
        double swap=arr[i];
        arr[i]=arr[smallest];
        arr[smallest]=swap;
    }
    min_heapify(arr,smallest);
}
void max_heapify(double arr[], int i)
{
    int l=(2*i);
    int r=(2*i+1);
    int largest;
    if(l<=heapsize && arr[l]>arr[i])
    {
        largest=l;
    }
    else
    {
        largest=i;
    }
    if(r<=heapsize && arr[r]>arr[largest])
    {
        largest=r;
    }
    if(largest==i)
        return;
    if(largest!=i)
    {
        double swap=arr[i];
        arr[i]=arr[largest];
        arr[largest]=swap;
    }
    max_heapify(arr,largest);
}
void insert_valuein_minheap(double minh[], int i, double val)
{
    minh[i]=val;
    while(i>1 && minh[i/2]>minh[i])
    {
        double temp=minh[i/2];
        minh[i/2]=minh[i];
        minh[i]=temp;
        i=i/2;
    }
}
void insert_valuein_maxheap(double maxh[], int i, double val)
{
    maxh[i]=val;
    while(i>1 && maxh[i/2]<maxh[i])
    {
        double temp=maxh[i/2];
        maxh[i/2]=maxh[i];
        maxh[i]=temp;
        i=i/2;
    }
}
void insert_element(double maxh[], double minh[], double val, int size)
{
    if(val<=maxh[1])
    {
        maxlen+=1;
        insert_valuein_maxheap(maxh,maxlen,val);
    }
    else
    {
        minlen+=1;
        insert_valuein_minheap(minh,minlen,val);
    }
    if(maxlen==minlen)
    {
        median=(maxh[1]+minh[1])/2;
        ct=1;
        return;
    }
    if(maxlen<minlen)
    {
        maxlen+=1;
        insert_valuein_maxheap(maxh,maxlen,minh[1]);
        double temp=minh[1];
        minh[1]=minh[minlen];
        minh[minlen]=temp;
        minlen-=1;
        heapsize=minlen;
        min_heapify(minh,1);
    }
    else
    {
        minlen+=1;
        insert_valuein_minheap(minh,minlen,maxh[1]);
        double temp=maxh[1];
        maxh[1]=maxh[maxlen];
        maxh[maxlen]=temp;
        maxlen-=1;
        heapsize=maxlen;
        max_heapify(maxh,1);
    }
}
int main()
{
    int n,td,notif=0;
    cin>>n>>td;
    double array[n+1],maxh[n+1]={},minh[n+1]={};
    for(int i=1;i<=n;i++)
    {
        cin>>array[i];
    }
    double first,second;
    for(int i=1,j;i<=n-td;i++)
    {
        int count=2;
        first=array[i];
        second=array[i+1];
        if(first<=second)
        {
            maxh[1]=first;
            minh[1]=second;
        }
        else
        {
            maxh[1]=first;
            minh[1]=second;
        }
        maxlen=1;minlen=1;ct=0;
        for(j=i+2;count!=td;j++)
        {
            insert_element(maxh,minh,array[j],j);
            count++;
        }
        if(td%2!=0)
        {
            if(maxlen>minlen)
                median=maxh[1];
            else
                median=minh[1];
        }
        else if(ct==0)
        {
            median=(maxh[1]+minh[1])/2;
        }
        float nota=array[j];
        if(nota>=2*median)
        {
            notif++;
        }
    }
    cout<<notif<<endl;
}

Beverie

You should rather see this approach, this will solve your problem. codereview.stackexchange.com/questions/210005/… – Vacuva