HackerRank Street Lights

HackerRank Street Lights question

I just want to give a shout out to Clayton Herbst who helped solve this question during our weekly competitive programming white board session. 🤜🏻🤛🏻 - fist bump

In order to solve this question we must first try and understand what the question is asking of us.

We have a road and along this road, we have several street lights with each street light lighting up numerous points on either side of it. Our job is to figure out how many points these street lights light up in total. It’s usually best to draw a diagram to represent the problem so let’s do that.

As an example, if we have 2 street lights which light up 2 points on either side. We can represent this as the following.

street light question

From what we can see in the above image, the points in which the light polls light up are -1, 0, 1, 2, 3, 5, 6, 7, 8, 9 therefore the total number of points our street light covers is 10.

There are a few edge cases which we must consider.

What if two street lights are on the same point?

street light same point

Because street lights 1 and 2 light up the same points we still only include the number of points which are lit up and not the total number of points each street light lights up. Therefore are result here is still 10

What if we have two street lights which are not located on the same point but either light up the same points?

street light next to each other

Because both street lights light up point 3 we can only include 3 once so the total points here would be -1, 0, 1, 2, 3, 4, 5, 6, 7 therefore the total number of points would be 9.

The last edge case we must consider is if the lights overlap each other.

street light next to each other

The result of this is very similar to the result in the previous edge case. Because both lights light up points 2 and 3 we only include these points once which leaves the points lit up to be -1, 0, 1, 2, 3, 4, 5 and our result is therefore 7.

Approach

How I have approached this question may be different to how others have approached this question. Though this approach will get you 30/30 points on HackerRank.

If we line up all of our street lights side by side, and only calculate the left most light of the current street pole up to the left most light of the next street pole, then this will cater for any overlapping light.

street light next to each other

At each iteration of the street poles we can then calculate the difference between the bounds of the light

If we then add these together we get 7 but hold up wait a second shouldn’t the answer be 8 🧐

We know that for the difference in the bounds of each light we must also include the point for the light pole itself. In which case we have two lights. So then would we not add 2? If the lights were not overlapping or touching then yes we could include each light pole point in the total number of points but because in our example above they overlap so essentially it’s as if they were one light pole. So to overcome this we can keep track of the total number of light poles and each time one light pole’s light overlaps another light pole’s light we can deduct one from the total number of points.

Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int numTestCases;
  cin >> numTestCases;

  while (numTestCases--)
  {
    int n, k;
    cin >> n >> k;

    vector<pair<int, int>> coverage;

    while (n--)
    {
      int light;
      cin >> light;
      coverage.push_back({light - k, light + k});
    }

    sort(coverage.begin(), coverage.end());

    int count = coverage.size();

    for (int i = 0; i < coverage.size(); i++)
    {
      bool isLastLight = i == coverage.size() - 1;
      int lower = coverage[i].first;
      auto nextLight = isLastLight ? coverage[i].second : coverage[i + 1].first;
      int upper = min(coverage[i].second, nextLight);

      if (!isLastLight && coverage[i].second >= coverage[i + 1].first)
        count--;

      count += (upper - lower);
    }

    cout << count << "\n";
  }
}

Space and Time Complexity