DEV Community

Miss Pooja Anilkumar Patel
Miss Pooja Anilkumar Patel

Posted on

218. Leetcode Solution in java


class Solution {
  public List<List<Integer>> getSkyline(int[][] buildings) {
    final int n = buildings.length;
    if (n == 0)
      return new ArrayList<>();
    if (n == 1) {
      final int left = buildings[0][0];
      final int right = buildings[0][1];
      final int height = buildings[0][2];
      List<List<Integer>> ans = new ArrayList<>();
      ans.add(new ArrayList<>(Arrays.asList(left, height)));
      ans.add(new ArrayList<>(Arrays.asList(right, 0)));
      return ans;
    }

    List<List<Integer>> leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
    List<List<Integer>> rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
    return merge(leftSkyline, rightSkyline);
  }

  private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
    List<List<Integer>> ans = new ArrayList<>();
    int i = 0; // left's index
    int j = 0; // right's index
    int leftY = 0;
    int rightY = 0;

    while (i < left.size() && j < right.size())
      // choose the point with smaller x
      if (left.get(i).get(0) < right.get(j).get(0)) {
        leftY = left.get(i).get(1); // update the ongoing leftY
        addPoint(ans, left.get(i).get(0), Math.max(left.get(i++).get(1), rightY));
      } else {
        rightY = right.get(j).get(1); // update the ongoing rightY
        addPoint(ans, right.get(j).get(0), Math.max(right.get(j++).get(1), leftY));
      }

    while (i < left.size())
      addPoint(ans, left.get(i).get(0), left.get(i++).get(1));

    while (j < right.size())
      addPoint(ans, right.get(j).get(0), right.get(j++).get(1));

    return ans;
  }

  private void addPoint(List<List<Integer>> ans, int x, int y) {
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == x) {
      ans.get(ans.size() - 1).set(1, y);
      return;
    }
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == y)
      return;
    ans.add(new ArrayList<>(Arrays.asList(x, y)));
  }
}


Enter fullscreen mode Exit fullscreen mode

leetcode

challenge

Here is the link for the problem:
https://leetcode.com/problems/the-skyline-problem/

Top comments (8)

Collapse
 
zeeshanali0704 profile image
ZeeshanAli-0704

good

Collapse
 
chiki1601 profile image
Miss Pooja Anilkumar Patel

Thank you😊

Collapse
 
kalkwst profile image
Kostas Kalafatis

Good implementation, but lacks proper explanation and documentation

Collapse
 
chiki1601 profile image
Miss Pooja Anilkumar Patel

Thank you, I want to do that...but I don't to how can I create it with explanation.....
I don't know to create a blog.

Collapse
 
kalkwst profile image
Kostas Kalafatis

I understand that it can be intimidating at first, everyone here had, has or will have that feeling at some point.

But if you face that challenge, one step at a time, everything will be fine 🙂🙂🙂.

Some advices to get started:

Use JavaDoc in your code

Documentation might seem irrelevant, useless, or hard to write right now but trust me, it will help.

First of all you will start a habit of documenting your code, a habit that will help you down the line in your career. And you will get better over time, avoiding the mistakes we all make when documenting something.

For example, you have a function called addPoint. Someone reading the code will need to search for that function in your solution and perform some mental gymnastics to figure out what it does. It also has some scary parameters like List<List<Integer>>. You should write down what this thing does. I assure you that in a month, if you read your solution, you won't have a clue.

Documenting your code will also do half of the work of explanation for you. When I write something here, I create the code and then use the documentation to create the post. You just need to elaborate on the comments you've written.

Explain your thinking process

Why do you need the merge function? How do you calculate the points?

Split your solution in logical parts and try to explain what you did and what problem it solves, why you chose this approach and how you did it. It doesn't have to be long, a paragraph or two will suffice.

After all, you will get a lot more feedback and interaction with other people of various levels of experience, if you try to have some explanation.

And don't worry that you will make mistakes. Everybody does all the time. This is a really friendly community and I promise you that you will get a lot more out of it if you try to get out of your comfort zone. 🙂🙂🙂

Thread Thread
 
chiki1601 profile image
Miss Pooja Anilkumar Patel

Hello sir, Thank you me for understanding me......but I honestly tell you, it will take time to make Blogs for leetcode solution

Thread Thread
 
kalkwst profile image
Kostas Kalafatis

So it's quantity over quality

Thread Thread
 
chiki1601 profile image
Miss Pooja Anilkumar Patel

yeah