HackerRank - Flatland Space Stations (EASY)

Difficulty Level: $\mathtt{EASY}$
This is a HackerRank question. Find the DESCRIPTION HERE

	/* File: FlatlandSpaceStations.java
	* Created: 9/12/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	import java.util.Arrays;
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class FlatlandSpaceStations {
	/**
	* main method
	*
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println(flatlandSpaceStations(6, new int[]{0, 1, 2, 4, 3, 5})); // expected 0
	System.out.println(flatlandSpaceStations(5, new int[]{0, 4})); // expected 2
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* Computes the maximum distance among all distances from a city to nearest space station
	*
	* @param n number of cities
	* @param c array of cities with space stations
	* @return maximum distance
	*/
	static int flatlandSpaceStations(int n, int[] c) {
	Arrays.sort(c);
	int stationIndex = 0;
	int prevStation = c[stationIndex];
	int nextStation = prevStation;
	int max = -1;
	for (int i = 0; i < n; i++) {
	int cityDistance = Math.min(Math.abs(i - prevStation), Math.abs(i - nextStation));
	max = Math.max(max, cityDistance);
	if (i == nextStation) {
	stationIndex++;
	prevStation = nextStation;
	nextStation = stationIndex < c.length ? c[stationIndex] : prevStation;
	}
	}
	return max;
	} // flatlandSpaceStations
	} // FlatlandSpaceStations

view raw FlatlandSpaceStations.java hosted with ❤ by GitHub

Complexity

The time complexity is $\cal{O(nlogn)}$.

The space complexity is also $\cal{O(n)}$.

---

---

---