# Sorting Code Challenge Breakdown

It’s time once again for a breakdown of a HackerRank code challenge. In particular, a code challenge called *Fraudulent Activity Notifications*. The theme is befitting of Maeby Fünke’s dubious alter ego: Surely, who suffers from a disease called “BS”, and will gladly accept monetary donations in her support.

This code challenge is a tricky and interesting one. Its principal facet is efficiently sorting things, but it requires the use of a less common algorithm: counting sort. (There is a solution which employs priority queues, but that’s another article.) Additionally, this challenge requires the calculation of medians, careful consideration for how certain numeric values are treated, and the use of a sliding window to isolate specific data per iteration.

I struggled to solve this challenge for quite a while. At first, because I didn’t know about counting sort, so I learned about counting sort. Then, I still struggled to find a solution because I couldn’t make sense of how to properly integrate counting sort into the context. I danced around the solution for a while, then submitted, and accessed the problem’s editorial explanation. I *still* struggled to understand, so I referenced solutions by others, but they were in languages I’m not most familiar with, and in some cases erroneous.

After further dissecting the problem and piecing together clues, I finally succeeded in writing a solution in `JavaScript`

that met the performance requirements and passed all test cases. I’d like to thank a programmer who goes by JJromi. They posted a `Java`

solution to this challenge that was clever and finally provided me with the *Aha!* moment of understanding. In addition to explaining the code mechanics of the solution for everyone, this article provides a solution to be referenced by others working with `JavaScript`

!

# Fraudulent Activity Notifications:

## Problem Statement:

There is a bank that has a policy for notifying its clients of possible fraudulent activity in their account. If the amount spent by a client on a particular day is greater than or equal to twice (`2x`

) the median spending amount of a specified number of trailing days—days which precede the present day—the bank will send the client a notification of potential fraudulent activity. The bank will not send a notification to the client until the specified number of trailing days has occurred.

Given the number of trailing `days`

and the client’s total daily `debits`

for a period of `n`

days, determine the number of notifications the client will receive during the period. For example:

const days = 3

const debits = [10, 20, 30, 40, 50]// the first three days (idx 0, 1, 2), the bank just collects data// on day four (idx 3), there are 3 trailing days: 10, 20, 30

// the daily debit is 40, and the median is 20

// 40 >= 20 * 2 => true

// 1 fraud notification is sent to the client// on day five (idx 4), there are 3 trailing days: 20, 30, 40

// the daily debit is 50, and the median is 30

// 50 >= 30 * 2 =>false

// no fraud notification is sent to the client// total notifications for the period is1

**Note:**

The median of a list of numbers can be found by arranging the numbers from smallest to greatest—*sorting* them. If there is an odd amount of numbers, the median is the middle number. If there is an even amount of numbers, the median is the average of the *two* middle numbers.

## Function Description:

The `activityNotifications()`

function must return an integer representing the number of notifications sent to the client.

**Input Parameters:**

`debits`

: an`Array`

of integers representing daily expenditures`days`

: an integer representing the required number of trailing days

**Constraints:**

`0 <= debits[i] <= 200`

: any daily debit amount cannot exceed`200`

.

## Brute Force Solution:

Let’s start by reviewing my first draft. It functions correctly and produces the desired output, but is not efficient enough to pass all test cases, primarily because it is not time efficient.

function activityNotifications(debits, days) {

let notices = 0 for (let i = days; i < debits.length; i++) {

const trail = debits.slice(i - days, i).sort((a, b) => a - b)

const median = trail.length % 2 === 0 ?

trail[(trail.length / 2) - 1] + trail[(trail.length / 2)] :

trail[Math.floor(trail.length / 2)] * 2 if (debits[i] >= median) notices++

} return notices

}

This brute force solution is good to analyze because it approximates the basic mechanics of the needed function and highlights the needed improvements.

- There is a function declaration with its parameters.
- There is a counter variable
`notices`

which will keep track of how many notifications are sent and act as the return value. - There is a
`for loop`

which iterates over the`debits`

`Array`

*starting from*the first index greater than the specified trailing`days`

. - There is a sliding window used to highlight and evaluate specific portions of the
`debits`

`Array`

, built by using the`.slice()`

method and`.sort()`

method and assigned to the variable`trail`

. **Put a pin in this*. - There is a rather convoluted conditional operator assigned to the variable
`median`

which uses the window (`trail`

) to take advantage of the values being sorted, evaluate whether there is an odd or even amount of values within the trailing days, and produce a median of the daily debits with the appropriate mathematical calculation. - There is an
`if`

statement which performs a straightforward evaluation to check whether the daily debit is greater than or equal to the median spending amount of the trailing days. If so, the counter variable`notices`

is incremented by`1`

. - There is a
`return`

statement which returns the integer represented by`notices`

—the amount of fraudulent activity notices sent to the client.

This function follows decent logic, but has some crucial flaws that require a major refactor. Convoluted median calculation by conditional operator aside, notice that, for each iteration of the `for loop`

, the sliding window `trail`

is constructed with iterators: `.slice()`

and `.sort()`

. This majorly impacts the time and space complexity of the function.

Consider that `.slice()`

affects the space complexity by creating a shallow copy of the `debits`

`Array`

at each iteration, but, more specific to this challenge’s test cases, when regarding nested loops, *e.g.* `for loop () { Array.sort() }`

, the time complexity becomes quadratic (`O(n²)`

), which is not optimal and becomes an issue when the input size becomes great.

The calculation of medians is essential to this function, which requires a sorted list of numbers. How can the process of sorting lists of integers at each window slide be performed while optimizing the function, improving its time complexity, and enhancing its performance?

## Optimized Solution:

The solution this code challenge seeks performs in linear time (`O(n)`

), and to achieve this we’ll need to employ a sorting algorithm capable of performing linearly. In this case, we can use counting sort. I’m going to focus explanation on how counting sort applies to this solution, and on the solution itself, more so than *exactly* how counting sort works. If you don’t know how counting sort works, I recommend you pause here and learn about how it works. I can recommend this informational article I wrote about it.

There is a key reason that counting sort is applicable. Notice that in the function description there is a constraint which dictates that the value of any daily debit, *i.e.* any element in the input `Array`

, cannot exceed `200`

. This relatively small number allows us to create the frequency `Array`

that counting sort depends on. Let’s start with the good bones from the brute force solution and build upon them to produce the optimized solution.

function activityNotifications(debits, days) {

let notices = 0 for (let i = days; i < debits.length; i++) {

const median = // work to figure the median

if (debits[i] >= median * 2) notices++

} return notices

}

Those are the bones we want to work with. The next step is to integrate counting sort. We start by initializing the frequency `Array`

. We can call it `countArr`

. Recall that the `0`

index needs to be accommodated, so the size of the `Array`

is set to `201`

, not `200`

.

function activityNotifications(debits, days) {

const countArr = new Array(201).fill(0)

let notices = 0 for (let i = days; i < debits.length; i++) {

const median = // work to figure the median

if (debits[i] >= median * 2) notices++

} return notices

}

Now that the `countArr`

is initialized, we can load it. Recall that we want to use a sliding window to evaluate only the required number of trailing days at each iteration. Knowing this, we start by loading `countArr`

for only the first window by using a `for loop`

with the counter limit set to the number of `days`

.

function activityNotifications(debits, days) {

const countArr = new Array(201).fill(0)

let notices = 0for (let i = 0; i < days; i++) {for (let i = days; i < debits.length; i++) {

countArr[debits[i]]++

}

const median = // work to figure the median

if (debits[i] >= median * 2) notices++

} return notices

}

The function prepares `countArr`

for the first iteration of the `for loop`

, but we need to slide that window to the next set of trailing days at each iteration so an updated `countArr`

is available for each next iteration. In case this procedure is unclear at this point, picture this:

// loop 1

[ 0 0 0 ] 0 0 0// loop 2

0 [ 0 0 0 ] 0 0// loop 3

0 0 [ 0 0 0 ] 0

The way to achieve this with counting sort and its complex index magic is to *decrement* the value in `countArr`

at the index equal to the *first* value of the trailing days, and *increment* the value in `countArr`

at the index equal to the value *just after* the trailing days. In other words, use an origin and a terminus regarding the window, *e.g.* debits: `0 0 [o 0 0] t`

, as corresponding indices for `countArr`

, and increment/decrement accordingly.

Yes, that *is* confusing, but, once you learn how counting sort works, you’ll be able to make sense of it. The terminus falling outside of the window is to account for an index shift, so you can think of this more simply as using the numbers from the *beginning* and *end* of the window. Shifting the entire window by its ends, like if you were to grab either end of a dining tray and move it to the next station in a cafeteria line. This article will also include a log of the function work to help demonstrate how the mechanics are manipulating values.

Let’s add the code that will handle the sliding window procedure. Notice that it comes at the end of the work done in the `for loop`

, allowing the median calculation to be performed before `countArr`

is adjusted for the next iteration.

function activityNotifications(debits, days) {

const countArr = new Array(201).fill(0)

let notices = 0for (let i = 0; i < days; i++) {

countArr[debits[i]]++

} for (let i = days; i < debits.length; i++) {

const median = // work to figure the median

if (debits[i] >= median * 2) notices++

countArr[debits[i - days]]--

countArr[debits[i]]++

} return notices

}

At this point, this function is practically complete. Except, of course, for the line that says: `const median = // work to figure the median`

. As convenient as that would be, we’re going to need to help the computer out. We’re going to outsource this work by way of a helper function. The purpose of the helper function will be to calculate the median spending amount of each window of trailing days.

This helper function will accept two arguments: `countArr`

and `days`

, which will come from the scope of the main function. The helper function will return the currently evaluated median times two (`* 2`

), which, at this point, is work done in the main function, but will be more valuable to calculate within the helper function. Let’s call our helper function `getMedianx2()`

.

function getMedianx2(countArr, days) {

let sum = 0 for (let i = 0; i < countArr.length; i++) {

sum += countArr[i]

if (sum * 2 === days) return (i * 2 + 1)

if (sum * 2 > days) return (i * 2)

}

}

Let’s break down the `getMedianx2()`

helper function. Firstly, let’s highlight the significance of the arguments given to the function. `countArr`

is used to find the median of each window because `countArr`

is a sorted reference to the debits `Array`

, and we need a sorted list of numbers to determine a median. `days`

is used to determine how the median needs to be calculated. Recall that different operations are required depending on whether the list of numbers is odd or even. The median of an odd list is the middle number. The median of an even list is the average of the middle two numbers. `days`

is either an odd or even number.

Next, we have a counter variable called `sum`

. This will represent the accumulative sum of the values in `countArr`

as they are iterated over. Calculating an accumulative sum is a necessary step for counting sort. A `for loop`

performs the iteration over `countArr`

, adding the current value to `sum`

at each iteration.

Now, here’s the clever part: There are two conditionals—two `if`

statements— within the loop that if met will break out of the loop and produce a return value. Instead of division, which is more computationally expensive and can produce pitfalls like floating point decimals, multiplication is used to determine if `days`

is odd or even. The multiplier we’ll use is `2`

because we want to double the value we’re evaluating, as the main function checks if the median *times two* (`* 2`

) is greater than or equal to the daily debit. Hence, our helper is called `getMedian`

.**x2**()

If, on any iteration, `sum * 2`

is equal to `days`

, we can determine that `sum`

is even because `days`

can be evenly divided by `2`

. Because of how counting sort hashes indices, we can use `days`

as an upper limit for `sum`

, which breaks the loop and targets the current index `i`

, which correlates to the value from the debits `Array`

, and consequently translates to the median value of the current window.

Note, though, that since the first conditional considers an even list of numbers in the window, the average of the middle two numbers is the desired value. Because of how this clever line of code and the counting sort magic work out, and because multiplication is used instead of division, the same result can be achieved by simply adding `1`

, or rounding up the result: `(i * 2) + 1`

.

If the first conditional is passed by and the second conditional—`sum * 2 > days`

—is met, it can be determined that `days`

is an odd number, and the correct median can be returned by simply multiplying the current index `i`

by `2`

. No rounding is necessary in this case.

Now that our helper function is set, the last thing to do is plug it into the main function. Note that the variable previously called `median`

will be changed to `medianx2`

to be more specific about what value the variable is holding. One more added nicety is to place a conditional paired with a `break`

statement before the window sliding procedure. This way, when the *last* daily debit is evaluated, the window sliding procedure will not be performed, as it would be unnecessary. Here’s the complete solution:

function getMedianx2(countArr, days) {

let sum = 0 for (let i = 0; i < countArr.length; i++) {

sum += countArr[i]

if (sum * 2 === days) return (i * 2 + 1)

if (sum * 2 > days) return (i * 2)

}

}function activityNotifications(debits, days) {

const countArr = new Array(201).fill(0)

let notices = 0 for (let i = 0; i < days; i++) {

countArr[debits[i]]++

} for (let i = days; i < debits.length; i++) {

const medianx2 = getMedianx2(countArr, days)

if (debits[i] >=medianx2) notices++

if (i === debits.length - 1) break

countArr[debits[i - days]]--

countArr[debits[i]]++

} return notices

}

## Process Log:

Here’s a log of how the data is being passed through the function and manipulated. Hopefully, it helps to further illustrate the explanation.

const days = 5

const debits = [2, 3, 4, 2, 3, 6, 8, 4, 5]activityNotifications(debits, days)// LOG /////////////////////////////////////////////////////////////input:

debits array: [2, 3, 4, 2, 3, 6, 8, 4, 5]

days span: 5initialize:

count array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

notices: 0load count array:

count array: [0, 0, 2, 2, 1, 0, 0, 0, 0, 0]main loop:

iteration 1

daily debit: 6

trailing days: [2, 3, 4, 2, 3] get median function:

count array: [0, 0, 2, 2, 1, 0, 0, 0, 0, 0]

trailing day count: 5

getMedian loop:

iteration 1

accumulation sum: 0

current index: 0

iteration 2

accumulation sum: 0

current index: 1

iteration 3

accumulation sum: 2

current index: 2

iteration 4

accumulation sum: 4

current index: 3 medianx2: 6

daily debit(6) is greater than or equal to median * 2 = 6

increment notices

notices + 1 = 1 count array before adjustment: [0, 0, 2, 2, 1, 0, 0, 0, 0, 0]

countArr[2]--

countArr[6]++

count array after adjustment : [0, 0, 1, 2, 1, 0, 1, 0, 0, 0]iteration 2

daily debit: 8

trailing days: [3, 4, 2, 3, 6] get median function:

count array: [0, 0, 1, 2, 1, 0, 1, 0, 0, 0]

trailing day count: 5

getMedian loop:

iteration 1

accumulation sum: 0

current index: 0

iteration 2

accumulation sum: 0

current index: 1

iteration 3

accumulation sum: 1

current index: 2

iteration 4

accumulation sum: 3

current index: 3 medianx2: 6

daily debit(8) is greater than or equal to median * 2 = 6

increment notices

notices + 1 = 2 count array before adjustment: [0, 0, 1, 2, 1, 0, 1, 0, 0, 0]

countArr[3]--

countArr[8]++

count array after adjustment : [0, 0, 1, 1, 1, 0, 1, 0, 1, 0]iteration 3

daily debit: 4

trailing days: [4, 2, 3, 6, 8] get median function:

count array: [0, 0, 1, 1, 1, 0, 1, 0, 1, 0]

trailing day count: 5

getMedian loop:

iteration 1

accumulation sum: 0

current index: 0

iteration 2

accumulation sum: 0

current index: 1

iteration 3

accumulation sum: 1

current index: 2

iteration 4

accumulation sum: 2

current index: 3

iteration 5

accumulation sum: 3

current index: 4 medianx2: 8

daily debit(4) is less than median * 2 = 8

no adjustment to notices

notices = 2 count array before adjustment: [0, 0, 1, 1, 1, 0, 1, 0, 1, 0]

countArr[4]--

countArr[4]++

count array after adjustment : [0, 0, 1, 1, 1, 0, 1, 0, 1, 0]iteration 4

daily debit: 5

trailing days: [2, 3, 6, 8, 4] get median function:

count array: [0, 0, 1, 1, 1, 0, 1, 0, 1, 0]

trailing day count: 5

getMedian loop:

iteration 1

accumulation sum: 0

current index: 0

iteration 2

accumulation sum: 0

current index: 1

iteration 3

accumulation sum: 1

current index: 2

iteration 4

accumulation sum: 2

current index: 3

iteration 5

accumulation sum: 3

current index: 4 medianx2: 8

daily debit(5) is less than median * 2 = 8

no adjustment to notices

notices = 2output:

notices: 2

Counting sort is a little hard to wrap your head around, but it can be very powerful in the right situation. Try to dig deeper into the magic that’s occurring under the hood while using counting sort. It’s a good brain builder. And try your hand at solving the *Fraudulent Activity Notifications* challenge!

github.com/dangrammer

linked.com/in/danieljromans

danromans.com