# Hackerrank: Fraudulent Activity Notifications Solution

## Approach

Counting sort (because the elements is in specific range)

We only need the middle element so we skip the array building from count table

## Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}function activityNotifications(expenditure, d) {2  const RANGE = 2013  let notifications = 04  const getDoubleMedian = (count, d) => {5    const N = count.length6    const countPrefix = Array.from(count)7    for (let i = 0; i < N; i++) {8      countPrefix[i] += countPrefix[i - 1] || 09    }10    let a = 011    let b = 012
13    // only need the middle elements, so skip build the array to avoid TLE14    if (d % 2 === 0) {15      let first = Math.floor(d / 2)16      let second = first + 117      let i = 018      for (; i < RANGE; i++) {19        if (first <= countPrefix[i]) {20          a = i21          break22        }23      }24      for (; i < RANGE; i++) {25        if (second <= countPrefix[i]) {26          b = i27          break28        }29      }30    } else {31      let first = Math.floor(d / 2) + 132      for (let i = 0; i < RANGE; i++) {33        if (first <= countPrefix[i]) {34          a = i35          b = i36          break37        }38      }39    }40
41    return a + b42  }43
44  //45  const count = Array(RANGE).fill(0)46  for (let i = 0; i < d; i++) {47    count[expenditure[i]]++48  }49
50  for (let i = d; i < expenditure.length; i++) {51    const median = getDoubleMedian(count, d)52    if (expenditure[i] >= median) {53      notifications++54    }55
56    // update el count table57    count[expenditure[i]]++58    count[expenditure[i - d]]--59  }60

## References

https://www.geeksforgeeks.org/counting-sort/

hackerrank

sorting

## Next Post

Hackerrank: Balanced Brackets

Jan 28, 2021

Search Posts