3
\$\begingroup\$

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;
    }

}
\$\endgroup\$
2
\$\begingroup\$

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));
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ Jun 3 at 4:09
  • 1
    \$\begingroup\$ @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 :-) \$\endgroup\$ Jun 3 at 5:42
  • 1
    \$\begingroup\$ Thanks mdfst13 for the grammar corrections. \$\endgroup\$ Jun 3 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.