In a programming challenge, sometimes creating and bringing over a sorted array while traversing another array seems the answer. In my experience, it is one of the common artificial pitfalls, and you are tested if you have roamed long enough in the field of competitive programming. When maintaining a sorted array comes to your mind, think twice. Probably you are expected to do better than that.

Adopting a dictionary is a good idea. Let me explain using an example problem.

Input:
 arr: a list of numbers. For all i, 0 <= arr[i] <=200.
 w: the window size
Output:
 medians: the array of numbers where medians[i] is the median of numbers in arr[i:w+i].
Example:
 Input:
   arr: [1, 2, 1, 2, 3]
   w: 3
 Output:
   medians: [1, 2, 2]

You will be shot to death in the desert if you naively create a sorted array of length w and bringing over the entire iterations. What you should notice is the constraint on the alphabet size described as in "For all i, 0 <= arr[i] <= 200". That means the alphabet is {0, 1, 2, ..., 200} and its size is 201 hence constant.  What you should bring over is not a sorted array but a dictionary whose keys are the alphabet (or, indices in an array). What should the dictionary hold as the value? This stage needs some creativity but storing the number of appearances in the window is a good choice.

Maintaining a dictionary is computationally more efficient than maintaining a sorted array. Here is the comparison.

• Adding an item
  • Dictionary: O(1)
  • Sorted Array: O(w)
• Removing an item
  • Dictionary: O(1)
  • Sorted Array: O(w)
• Finding the median
  • Dictionary: O(1) because the alphabet size is constant (i.e. 201)
  • Sorted Array: O(1)

Reference

Fraudulent Activity Notifications | HackerRank

Print the number of times a customer receives a notification

HackerRank

FraudulentActivityNotifications.ts

GitHub Gist: instantly share code, notes, and snippets.

Gist262588213843476