Adam wants to watch a football game from the top of the building that is arranged in a straight line.

1. Adam can watch the football match from the top of ith building if there exists a maximum of K[i] buildings in front of Adam with a height less than or equal to the height of ith building.
2. If there is any building in front of Adam with a height more than the height of ith position building then he cannot see the match from this ith building.

Count the positions of buildings where Adam can see the match from the top of the buildings.

Example: Both arrays have the same length.

B (Buildings) = [2,1,3] represents the height of buildings
K = [1,2,1] 

Answer: 1

Explanation:

For B[0] = 2 we have K[0] = 1. The number of buildings in front of it that have a height smaller than or equal to 2 is 0. This is <= K[0] So Adam can see the match.

For B[1] = 1, we have K[1] = 2. The number of buildings in front of it that have a height smaller than or equal to 1 is 0. But B[0] = 2 so Adam cannot see the match.

For B[2] = 3, we have K[2] = 1. The number of buildings in front of it that have a height smaller than or equal to 3 is 2. But this value is >= K[2] i.e 1 so Adam cannot see the match

The total positions where Adam can see the match is 1.

Constraints:

Array size is 1 to 10^5
Each element in Arrays is 1 to 10^5

This is the code I tried with the time complexity of O(n^2):

public static int process(int[] buildings, int[] K) {
    int n = buildings.length;
    int answer = 0;
    for(int i=0; i<n; i  ) {
        int count = 0;
        boolean valid = true;
        for(int j=i-1; j>=0; j--) {
            if(buildings[j] <= buildings[i]) count  ;
            if (buildings[j] > buildings[i]) {
                valid = false;
                break;
            }
        }
        if(valid && count <= K[i]) answer  ;
    }
    return answer;
}

This program works for arrays of small size but fails for large arrays as the time complexity of my program is O(n^2).

What is the better approach to solve this and how can we reduce the time complexity?

CodePudding user response：

you have 2 conditions which we look on one by one but we'll start from the second:

The second condition can be interpreted as if ith building is the highest building from any other building in front of it. this can be achieved by checking the max hight to the ith position and update it as you go.

if the second condition is true that's means you have i-1 buildings in front of the ith building that are equal or smaller than it (i instead of i-1 if you start to count from 0 like in array). so the first condition would be true only if k[i] is bigger than (i-1) you just need to compare between them.

here is the code in java:

import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        List<Integer> buildings = Arrays.asList(2, 1, 3);
        List<Integer> K = Arrays.asList(1, 2, 1);
        System.out.println(process(K, buildings));
    }

    
    public static Integer process(List<Integer> K, List<Integer> buildings){
        Integer maxHightBuilding = buildings.get(0);
        Integer sum = 0;
        for(Integer i = 0; i < buildings.size(); i  ){
            if(buildings.get(i) >= maxHightBuilding ){
                maxHightBuilding = buildings.get(i);
                if(i <= K.get(i)){
                    sum  ;
                }
            }
        }
        return sum;
    }
}

CodePudding user response：

I think if you retain the biggest value in front of actual index, you can just check with the value and when your index pass the biggest value you update him.

(find biggest value from end of array)

HF !