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

1function activityNotifications(expenditure, d) {
2  const RANGE = 201
3  let notifications = 0
4  const getDoubleMedian = (count, d) => {
5    const N = count.length
6    const countPrefix = Array.from(count)
7    for (let i = 0; i < N; i++) {
8      countPrefix[i] += countPrefix[i - 1] || 0
9    }
10    let a = 0
11    let b = 0
12
13    // only need the middle elements, so skip build the array to avoid TLE
14    if (d % 2 === 0) {
15      let first = Math.floor(d / 2)
16      let second = first + 1
17      let i = 0
18      for (; i < RANGE; i++) {
19        if (first <= countPrefix[i]) {
20          a = i
21          break
22        }
23      }
24      for (; i < RANGE; i++) {
25        if (second <= countPrefix[i]) {
26          b = i
27          break
28        }
29      }
30    } else {
31      let first = Math.floor(d / 2) + 1
32      for (let i = 0; i < RANGE; i++) {
33        if (first <= countPrefix[i]) {
34          a = i
35          b = i
36          break
37        }
38      }
39    }
40
41    return a + b
42  }
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 table
57    count[expenditure[i]]++
58    count[expenditure[i - d]]--
59  }
60
61  return notifications
62}

References

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