Solving HackerRank Problem: Hackerland Radio Transmitters  using Javascript

Problem

Complete the hackerlandRadioTransmitters function in the editor below. It must return an integer that denotes the minimum number of transmitters to install.

hackerlandRadioTransmitters has the following parameter(s):

  • x: integer array that denotes the locations of houses
  • k: an integer that denotes the effective range of a transmitter

See the full description of the problem Hackerland Radio Transmitters

Solution

First, sort the array to so duplicate houses dont cause any errors when looking for where to place the transmitter. Then, use greedy algorithm to always place the transmitter at the house furthest to the right possible to cover the range.

Time complexity: O(n log(n)) //Finding the furthest transmitter range

Space complexity: O(1)   //No additional space was used

Credit: @github.com/RyanFehr