Fraudulent Activity Notifications

activityNotifications.cpp

// problem : https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem

int activityNotifications(vector<int> expenditure, int d) {
    const int MAX_EXPENSE = 200;

    const bool isEven = ( d % 2 ) == 0;
    const int medianIndex = isEven ? ( d / 2 ) - 1 : d / 2;
    
    // setup counting sort
    vector<int> expenditureCounter( MAX_EXPENSE + 1, 0 );
    for( int j = 0; j < d; ++j )
    {
        ++expenditureCounter[ expenditure[ i - d + j  ] ];
    }
    for( int j = 0; j <= MAX_EXPENSE; ++j )
    {
        expenditureCounter[ j + 1 ] += expenditureCounter[ j ];
    }

    int notifyCount = 0;
    for( int i = d; i < expenditure.size(); ++i )
    {
        
        // find median
        double median = 0.0;
        for( int j = 0; j <= MAX_EXPENSE; ++j )
        {
            if( expenditureCounter[ j ] > medianIndex )
            {
                median = static_cast<double>( j );
                break;
            }
        }

        if( isEven )
        {
            // find another median
            for( int j = 0; j <= MAX_EXPENSE; ++j )
            {
                if( expenditureCounter[ j ] > ( medianIndex + 1 ) )
                {
                    median = ( median + static_cast<double>( j ) ) / 2.0;
                    break;
                }
            }
        }

        // check if it needs to notify
        if( median * 2.0 <= expenditure[ i ] )
        {
            ++notifyCount;
        }

        // remove oldest expenditure from trail
        for( int j = expenditure[ i - d ]; j <= MAX_EXPENSE; ++j )
        {
            --expenditureCounter[ j ];
        }

        // add today
        for( int j = expenditure[ i ]; j <= MAX_EXPENSE; ++j )
        {
            ++expenditureCounter[ j ];
        }
    }

    return notifyCount;
}