# Goodland Electricity challenge – O(n)

In the previous post I discussed an algorithm that had a running time of . Well here is an algorithm to the Goodland Electricity challenge.

### Greedy algorithm

- For each city
`i`

store its preceding tower in`previousTowerFor[i]`

. If`i`

has a tower then`previousTowerFor[i] = i`

. If no tower precedes, set to`-1`

. For example for input:`0 1 1 1 1 0`

,`previousTowerFor`

will be:`-1 1 2 3 4 4`

- Iterate over all cities
`i`

.- Get the nearest possible tower using
`previousTowerFor`

. The right-most tower can at most have distance . So looking at the`previousTowerFor[i + k - 1]`

can either result at a tower to the right of`i`

(within distance) or to a tower to the left of`i`

(if the last preceding tower of index happens to be one on the left of`i`

). - If no such tower exists or distance of tower to city is , return
`-1`

. Else go to next uncovered city . - For the next uncovered city (which is ), the next possible tower will be at index ( coverage from plus for the next city plus coverage from the next tower). See illustration below:

- Get the nearest possible tower using

**Solution**

public class GoodlandElectricity { private static int solve(int n, int k, boolean[] hasTower) { int count = 0; int[] previousTowerFor = new int[n]; // previousTowerFor[i] holds index of the preceding tower or i if i is a tower. int last = -1; for (int i = 0; i < n; i++) { if (hasTower[i]) { last = i; } previousTowerFor[i] = last; } int city = 0; while (city < n) { // A tower can be at most k - 1 distance from city. When looking at previousTowerFor[city + k - 1] // we get the right-most tower from city (since previousTowerFor[city + k - 1] holds the latest tower to the left of index city + k - 1). int tower = previousTowerFor[Math.min(city + k - 1, n - 1)]; if (tower == -1 | city - tower >= k) { return -1; } else { // We found a tower within k distance of city. // Jump to next city that requires a tower. Since tower can cover k-1 cities, we jump to city = tower + k. city = tower + k; count++; } } return count; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); boolean[] hasTower = new boolean[n]; for (int i = 0; i < n; i++) { int t = in.nextInt(); hasTower[i] = t == 1; } System.out.println(solve(n, k, hasTower)); } }