Add K Streetlights at Integer Positions to Minimize the Longest Dark Stretch
Solve this Problempositions. You may add up to k new streetlights, each also at an integer position (any position is allowed, not only ones already listed). Find the placement that minimizes the longest stretch of road between any two consecutive streetlights (existing or new), and return that minimized length.
Because every position must be an integer, splitting one existing gap of length g into pieces no longer than a candidate length L takes a fixed, computable number of new lights: ⌈g / L⌉ - 1. That's what makes this version different from the classic continuous-position variant of this problem — no floating-point search is needed, since the cost of any candidate stretch length is an exact integer.
The total new-light cost only ever decreases (or stays flat) as the candidate stretch length grows, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate stretch length). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger candidate keeps working too. — search directly over candidate stretch lengths rather than trying every possible placement.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ number of existing streetlights ≤ 10⁴ - ◆
0 ≤ positions[i] ≤ 10⁶, given in strictly increasing order - ◆
0 ≤ k ≤ 10⁴ — the number of new streetlights that may be added - ◆
Every streetlight (existing or new) must sit at an integer position
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Stretch Length From 1 Upward
BruteSince every streetlight — new or old — must sit at an integer position, splitting one existing gap of length g into pieces no longer than some candidate length L takes exactly ⌈g / L⌉ - 1 new lights (⌈g / L⌉ equal-or-smaller pieces, one fewer light than pieces). Try L = 1, 2, 3, ... and sum that cost across every existing gap; the first L whose total fits within k new lights is the answer, since a longer L can only ever need the same number of new lights or fewer. Correct, but checking every candidate length one at a time is wasteful once the gaps get large.
O(n · maxGap)O(1)1class Solution {
2 public int minMaxGap(int[] positions, int k) {
3 int maxGap = 0;
4 for (int i = 1; i < positions.length; i++) maxGap = Math.max(maxGap, positions[i] - positions[i - 1]);
5 for (int gap = 1; gap <= maxGap; gap++) {
6 if (lightsNeeded(positions, gap) <= k) return gap;
7 }
8 return maxGap;
9 }
10
11 private int lightsNeeded(int[] positions, int gap) {
12 int total = 0;
13 for (int i = 1; i < positions.length; i++) {
14 int g = positions[i] - positions[i - 1];
15 int pieces = (g + gap - 1) / gap;
16 total += pieces - 1;
17 }
18 return total;
19 }
20}Optimal — Binary Search on the Stretch Length
OptimalThe number of new lights needed only ever goes down (or stays the same) as the target stretch length grows — a longer allowed stretch can never need more new lights. That monotonic relationship is exactly what binary search needs: search the candidate stretch lengths between 1 and the largest existing gap, and whenever a candidate's total new-light cost fits within k, remember it and try a shorter stretch; otherwise it's too ambitious, so search longer.
O(n · log(maxGap))O(1)1class Solution {
2 public int minMaxGap(int[] positions, int k) {
3 int lo = 1, hi = 0;
4 for (int i = 1; i < positions.length; i++) hi = Math.max(hi, positions[i] - positions[i - 1]);
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 if (lightsNeeded(positions, mid) <= k) {
9 ans = mid;
10 hi = mid - 1;
11 } else {
12 lo = mid + 1;
13 }
14 }
15 return ans;
16 }
17
18 private int lightsNeeded(int[] positions, int gap) {
19 int total = 0;
20 for (int i = 1; i < positions.length; i++) {
21 int g = positions[i] - positions[i - 1];
22 int pieces = (g + gap - 1) / gap;
23 total += pieces - 1;
24 }
25 return total;
26 }
27}