Friday, November 4, 2016

Buildings which can see the sun

Problem
An array of integers is given which represents the heights of n buildings.Sun start falling from the left side. If there is a building of certain Height, all the buildings right of it having lesser heights cannot see the sun. Find the no. of buildings which can see the sun.

Solutions
Starting from we have to find the building which has same or bigger height than building on left side. Which means we have to list out local maximum in the array, which will give us the building which can see the sun.
Solution below uses an temp list for storing the local maximum so far.

import java.util.ArrayList;
import java.util.List;

public class SunViewBuilding {

    public static int GetSunViewCount(int[] buildingHeights){
        if (buildingHeights.length <= 0)
            return 0;

        List localMax = new ArrayList<>();

        localMax.add(buildingHeights[0]);
        for (int i =1;  i < buildingHeights.length; i++){
            if (localMax.get(localMax.size()-1) <= buildingHeights[i]){
                localMax.add(buildingHeights[i]);
            }
        }

        return localMax.size();
    }

    public static void main(String[] args) {
        int[] input = {12, 11, 13, 5, 30, 6, 30};
        System.out.println("Buildings which can see the sun : " + GetSunViewCount(input));
    }
}

Comments are welcome. Question source geeksforgeeks

No comments:

Post a Comment