Hills and Soldier

A trivial solution that comes to mind is for each hill we can check all the hills ‘j’ that come earlier in the ‘HILLS’ array. Let’s consider the current hill as ‘HILLS[i]’ and for some ‘HILLS[j]’ where( j < i ) there should not be any hill in-between ‘i’ and ‘j’ such that it is taller than any of the hills. We are counting only for previous hills because if we count for hills ahead as well then we will be counting each pair twice. 

The steps are as follows:

countPairs( n, hills ):

1. Initialize a variable ‘count’ to store the count of hill pairs.
2. Traverse the hills array for ‘i’ 0 to n-1.
   • Declare a variable ‘maxTillNow’ with a value 0.
   • For all the previous hills ‘j’ from i-1 to 0:
     • if(maxTillNow<=hills[i] and maxTillNow<= hills[j])
       • Increase ‘count’ by 1.
   • Update ‘maxTillNow’ with max(maxTillNow,hills[j]).
3. Return ‘count’.

Trivially all the soldiers of consecutive hills can see each other as there are no other hills between them so the answer will be at least ‘N’-1. 

We can use a stack to store a pair of the height of the current hill and the number of hills we can see from the current hill which can be on the left and right. 

The execution of the program will happen in the following way:

If the stack is not empty:

We remove all the people from the stack whose height is less than the current person because they won’t be able to see the hills next to the current hill, As the current hill is higher than the previous hills. So we remove them from the stack and increase the answer by the number of hills we can see from the hills that are being removed from the answer.

If the stack is empty, then we can insert the height of the current hill and 1 in the stack as the person at the current hill can look at the torch at the direct next hill if there is any on the right. We are not looking at the back because the previous hill person already counts the answer.

Else if the top element of the stack has the same height as the current hill’s height, Then we increase the answer by the number of hills the top element hill can see. Now the current hill soldier can see all the soldiers the previous hill soldier can see. Also, the current soldiers can also see the top element of stack hill’s soldiers so we increase the count of the number of soldiers top element hill’s soldiers can see as both the hills has the same height. If there is more than 1 element in the stack, then that means there are elements greater than the height of the current hill then the first greater element can also see the current soldiers so we increase the count of answers by 1.

Else the top element must have a height greater than the current one then the soldiers at that hill can also see the soldiers at the next upcoming hill so we increase the answer count by 1 and push the height of the current hill and 1 as pair in the stack.

The steps are as follows:

countPairs( n, hills ):

1. Declare a stack named ‘hillStack’ of pair int and int where the first one represents the height of the hill and the second one represents the number of hills it can see.
2. Declare a variable ‘count’ which stores the count of pairs initialized with 0.
3. For i in range[0, n-1]
   • while( hillStack is not empty() and top element of stack’s hill height is < current hill height.
     • Increase count with hillStack.top().second;
     • Remove the top element of the stack.
   • If stack is empty()
     • Insert [HILLS[i], 1] in the stack.
   • Else if(hillStack.top().first==HILLS[i])
     • Count += hillStack.top().second;
     • If size of stack is greater than 1:
       • Increase count by 1.
     • Increase hillStack.top().second by 1.
   • else :
     • Increase count by 1.
     • Inset [a[i], 1]
4. Return count.