Sorting Code Challenge Breakdown

Hold on Surely Fünke! Surely Fünke –how we ♥ thee–

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 is 1

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 = 0
  for (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++
  }
  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 = 0
  for (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 getMedianx2().

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: 5
initialize:
  count array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  notices: 0
load 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 = 2
output:
  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