SkylineProblem in Java

Question

taken from leetcode.com:

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively. [...] enter image description here

please review this code. I'm most interested in feedback about OOP-Principles (SOLID, readability, etc.) and second most interested on performance.

class Solution

public class Solution {
 public static void main(String[] args) {
 final int[][] input = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
 Solution solution = new Solution();
 System.out.println("amount : "+solution.getSkyline(input));
 }
 //this crude method is a HARD REQUIREMENT and may not be changed!
 public List<List<Integer>> getSkyline(int[][] buildings) {
 SkyLineConverter skyLineConverter = new SkyLineConverter();
 SkyLine skyLine = skyLineConverter.convert(buildings);
 Set<Edge> edges = skyLine.getEdges();
 return sortList(edges);
 }
 private List<List<Integer>> sortList(Set<Edge> edges) {
 List<List<Integer>> result = new ArrayList<>();
 List<Edge> list = new ArrayList<>(edges);
 list.sort(Comparator.comparingInt(o -> o.x));
 for(Edge edge: list){
 List<Integer> intList = new ArrayList<>();
 intList.add(edge.x);
 intList.add(edge.height);
 result.add(intList);
 }
 return result;
 }
}

class SkyLineConverter

public class SkyLineConverter {
 public SkyLine convert(int[][] raw) {
 BuildingConverter buildingConverter = new BuildingConverter();
 List<Building> buildings = buildingConverter.convert(raw);
 return new SkyLine(buildings);
 }
}

class Building

public class Building {
 public final int x;
 public final int width;
 public final int height;
 public Building(int x, int width, int height) {
 this.x = x;
 this.width = width;
 this.height = height;
 }
}

class BuildingConverter

public class BuildingConverter {
 private static final int FROM_INDEX = 0;
 private static final int TO_INDEX = 1;
 private static final int HEIGHT_INDEX = 2;
 public List<Building> convert(int[][] raw) {
 List<Building> buildings = new ArrayList<>();
 for (int[] buildingRaw: raw){
 int x = buildingRaw[FROM_INDEX];
 int width = buildingRaw[TO_INDEX] - buildingRaw[FROM_INDEX];
 int height = buildingRaw[HEIGHT_INDEX];
 buildings.add(new Building(x,width,height));
 }
 return buildings;
 }
}

class Skyline

public class SkyLine {
 private final int width;
 private final Set<Edge> edges = new HashSet<>();
 private final List<Building> buildings;
 public SkyLine(List<Building> buildings) {
 this.buildings = buildings;
 Building mostRight = findMostRight(buildings);
 width = mostRight.x + mostRight.width;
 addEdge();
 }
 private void addEdge() {
 buildings.forEach(b -> {
 addEdge(b.x);
 addEdge(b.x + b.width);
 });
 edges.add(new Edge(width, 0));
 }
 private void addEdge(int x) {
 int skyline = getSkyLine(x);
 int previous = x == 0 ? 0 : getSkyLine(x - 1);
 if (previous < skyline || previous > skyline) {
 edges.add(new Edge(x, skyline));
 }
 }
 private int getSkyLine(int x) {
 List<Building> aroundThisPoint = buildings.stream().
 filter(b -> b.x <= x && b.x + b.width > x).
 collect(Collectors.toList());
 return aroundThisPoint.stream().mapToInt(b -> b.height).max().orElse(0);
 }
 private Building findMostRight(List<Building> buildings) {
 Optional<Building> mostRight = buildings.stream().reduce((a, b) ->
 a.x > b.x ? a : b);
 //noinspection OptionalGetWithoutIsPresent
 return mostRight.get();
 }
 public Set<Edge> getEdges() {
 return edges;
 }
}

class Edge

public class Edge {
 public final int x;
 public final int height;
 public Edge(int x, int height){
 this.x = x;
 this.height = height;
 }
}

Answer 1

I noticed you have used stream library in most of your code, so I thought about increasing readability with less lines of code using streams if possible because other parts looks fine to me. In your Solution class you have the following method :

private List<List<Integer>> sortList(Set<Edge> edges) {
 List<List<Integer>> result = new ArrayList<>();
 List<Edge> list = new ArrayList<>(edges);
 list.sort(Comparator.comparingInt(o -> o.x));
 for(Edge edge: list){
 List<Integer> intList = new ArrayList<>();
 intList.add(edge.x);
 intList.add(edge.height);
 result.add(intList);
 }
 return result;
}

You could directly iterate over the edges set combining Stream#sorted and Stream#map, so avoiding the need of explicitly instantiate a list like my method below:

private List<List<Integer>> sortList(Set<Edge> edges) {
 
 return edges.stream()
 .sorted(Comparator.comparingInt(edge -> edge.x))
 .map(edge -> List.of(edge.x, edge.height))
 .collect(Collectors.toList()); 
}

In your BuildingConverter class you have the following method:

public List<Building> convert(int[][] raw) {
 List<Building> buildings = new ArrayList<>();
 for (int[] buildingRaw: raw){
 int x = buildingRaw[FROM_INDEX];
 int width = buildingRaw[TO_INDEX] - buildingRaw[FROM_INDEX];
 int height = buildingRaw[HEIGHT_INDEX];
 buildings.add(new Building(x,width,height));
 }
 return buildings;
}

It is possible streaming every row of your int[][] raw 2d array with Arrays#stream and Stream#map obtaining the same expected result like below:

public List<Building> convert(int[][] raw) {
 return Arrays.stream(raw)
 .map(arr -> new Building(arr[FROM_INDEX], 
 arr[TO_INDEX] - arr[FROM_INDEX], 
 arr[HEIGHT_INDEX]))
 .collect(Collectors.toList());
}

In your class SkyLine you have the following two methods that can be simplified:

private int getSkyLine(int x) {
 List<Building> aroundThisPoint = buildings.stream().
 filter(b -> b.x <= x && b.x + b.width > x).
 collect(Collectors.toList());
 return aroundThisPoint.stream().mapToInt(b -> b.height).max().orElse(0);
}
private Building findMostRight(List<Building> buildings) {
 Optional<Building> mostRight = buildings.stream().reduce((a, b) ->
 a.x > b.x ? a : b);
 //noinspection OptionalGetWithoutIsPresent
 return mostRight.get();
}

In your getSkyLine method there is no need to instantiate an intermediate list that will be streamed, you can combine your code lines in a more succinct method:

private int getSkyLine(int x) {
 
 return buildings.stream()
 .filter(b -> b.x <= x && b.x + b.width > x)
 .mapToInt(b -> b.height)
 .max()
 .orElse(0);
}

Your findMostRight method could be simplified using the Collections#max like below:

private Building findMostRight(List<Building> buildings) {
 return Collections.max(buildings, Comparator.comparingInt(b -> b.x));
}

• Martin Frank: wow - java8 and streams are already so old and i still do not know how to use them properly - thank you very very much for these improvements!
• dariosicily: @MartinFrank You are welcome, that also applies to me, I don't remember all the stream methods and without ide autocomplete I would be lost :-)
• dariosicily: Thanks mdfst13 for the grammar corrections.