Hackerland Radio Transmitters

I wanted to do a practice and randomly picked: Hackerland Radio Transmitters. I highly encourage you to give it a shot, I at least enjoyed working on it.

Please do not proceed if you want to solve it yourself!

To summarize, challenge goes as follows:


Hackerland is a one-dimensional city with n houses, where each house i is located at some xi on the x-axis. The Mayor wants to install radio transmitters on the roofs of the city's houses. Each transmitter has a range, k, meaning it can transmit a signal to all houses ≤ k units of distance away.


Given a map of Hackerland and the value of k, can you find the minimum number of transmitters needed to cover every house?

My implementation is as follows:

```
package biz.tugay;

import java.util.*;

public class HackerlandRadioTransmitters {

public static int minNumOfTransmitters(int[] houseLocations, int transmitterRange) {
// Sort and remove duplicates..
houseLocations = uniqueHouseLocationsSorted(houseLocations);

int towerCount = 0;
for (int nextHouseNotCovered = 0; nextHouseNotCovered integers = new HashSet<>();
final int[] houseLocationsUnique = new int[houseLocations.length];

int innerCounter = 0;
for (int houseLocation : houseLocations) {
if (integers.contains(houseLocation)) {
continue;
}
houseLocationsUnique[innerCounter] = houseLocation;
integers.add(houseLocationsUnique[innerCounter]);
innerCounter++;
}
return Arrays.copyOf(houseLocationsUnique, innerCounter);
}

// Given an array of house locations, INDEX of the starting house that is not covered by a transmitter, and the transmitter range,
// This method returns the index where the tower can be farthest placed, in order for house at location houseLocations[houseNotCoveredIndex]
// gets covered.

// For example an array of {1, 5, 9} indicates the following house locations:

Double sort?

The way you sort your input array is like this:

houseLocations = uniqueHouseLocationsSorted(uniqueHouseLocationsSorted(houseLocations));

Notice how you call your sort function twice. I'm not sure why you did that but it shouldn't be necessary.
Duplicate removal can be simplified

Currently, you sort your input array and then use a HashSet to remove duplicates from it. Actually, removing duplicates from a sorted array can be much simpler than that.

• Copy the first element of the input array to the output array.

• For each remaining element, compare the element to the previous element. If they are equal, then skip it (because it is a duplicate). Otherwise, copy it to the output array.

This removes the need to create a whole HashSet just to check for duplicates.

StackExchange Code Review Q#161129, answer score: 2