Redirecting to
NADOS


  Prev   Next

Temple Offerings







The best preparation for tomorrow is doing your best today.
~ H. Jackson Brown, Jr.

Temple Offerings

Introduction: Welcome back, dear reader. So, how is it going? In this article, we will discuss a very interesting problem called TEMPLE OFFERINGS. So, what does this problem say?

Question Overview:We have a mountain range and the temples are located on it in rows at different heights. We wish to give minimum offerings but to all the temples such that we follow these two rules:

  1. If two adjacent temples are at different heights, then the temple which is situated at greater height should receive more offerings.

  2. If two adjacent temples are at the same height, their offerings related to each other does not matter.

Since we have to give offerings to all the temples, we can add one more rule that no temple should have 0 offerings. We recommend you refer to the TEMPLE OFFERINGS VIDEO to understand the question completely and then try to solve it yourself first and then move to the solution.

Important Link : Problem Link, Solution Video Link

Approach:

Time Complexity: O(n) where n is the size of the input array

Space Complexity: O(n)

Explanation:

We will break this problem into WHAT, HOW and WHY. Let us start with the WHAT of the problem i.e. let us first focus on what we have to do to solve it.

What of the problem

Let us say we are given a mountain range (array of heights) as shown in the figure:

img

We have not represented an array or not even written any values of heights here as we do not need specific values. Here, we just need to compare the heights which are clearly visible in the diagram. So, we will make a dp array dp1 of the size same as that of the input array.

  1. If the height of the current temple is greater than the previous adjacent temple i.e. height[i]>height[i-1], put dp1[i]=dp2[i-1]+1 i.e. add 1 to the previous adjacent offering value.
  2. If the height of the current temple is less than or equal to the previous temple i.e. height[i] < = height[i-1], put dp1[i]=1.

So, let us start filling this dp1 array following the above 2 rules. We will start filling from left to right. The first value of offering will be 1. Why?

This is because we have to give offerings to every temple so the value cannot be 0 but, it has to be minimum too. So, we select 1.

img

After this, we move to the next temple. The height of the second temple is greater than the previous height. So, according to the rules mentioned above, we will add 1 to the previous height.

img

The same will be the case for the next 2 heights as well.

img

Now, we move to the 5th temple. The height of this temple is equal to the height of the previous temple. So, as discussed in the rules above, we will put 1 in dp1 whenever the height of the current temple is less than or equal to the previous.

img

The next temple is again higher. So, we will just add 1 to the height as shown in the diagram below:

img

Now, the height is less than the previous height. So, we will put 1 in dp1[i].

img

So, in this way, we can fill this entire dp1 array as shown in the diagram below:

img

We will create another array dp2 of the same size as that of the input array.. Here, we will fill the values from right to left following the same rules as above.

For instance, the first value will be 1. After this, the height is increasing and so will the values as shown in the image below:

img

Now, the heights of the next temples are less than the heights of the previous temples. So, we will put 1 in dp2 at all those places.

img

So, we can fill this entire array too in the same way.

img

Now, we will select the maximum out of the 2 values present at each temple i.e. the values from dp1 and dp2 and the max out of them will be added to the answer. This is shown in the diagram below:

img

So, the minimum offerings that we can offer to all the temples is 44. This is the entire procedure that we have to follow. We hope that you have understood the complete procedure. This was the "what" of the procedure. Do not think about "why" we did this procedure. We will discuss it later. Let us now discuss the "how" of the procedure i.e. how we can implement this in code.


How of the problem


Dear reader, we hope that you have understood the complete procedure from above. You may refer to the solution video to clear your doubts regarding the procedure if any. Now that we have understood everything, let us write the code.

import java.io.*; import java.util.*; public class Main { public static int totaloffering(int[] height) { // write your code here int[] dp1=new int[height.length]; dp1[0]=1; for(int i=1;i< dp1.length;i++) { if(height[i]>height[i-1]) { dp1[i]=dp1[i-1] + 1; } else { dp1[i]=1; } } int[] dp2=new int[height.length]; dp2[dp2.length-1]=1; for(int i=dp2.length-2;i>=0;i--) { if(height[i]>height[i+1]) { dp2[i]=dp2[i+1] + 1; } else { dp2[i]=1; } } int ans=0; for(int i=0;i< height.length;i++) { ans= ans+ Math.max(dp1[i],dp2[i]); } return ans; } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int height[] = new int[n]; for (int i = 0; i < n; i++) { height[i] = scn.nextInt(); } scn.close(); System.out.println(totaloffering(height)); } }
java; true";

The code is written and explained in the solution video. We recommend you refer to it to clear your doubts regarding it if any. Let us discuss the time and space complexity of this code.

Time and Space Complexity Analysis:

Time Complexity: The time complexity of the above code is O(n) where n is the size of the input array. This is because we are traversing n elements 3 times. Once for filing dp1, then for dp2 and finally for calculating the answer.

Space Complexity: The space complexity of the above code is O(n) also as we have made 2 dp arrays of size n each.

Why of the problem

We increased the value whenever we got to increasing heights. This is simple and can be understood very easily to be compatible with the question as we are given that the higher of the two adjacent temples will have more offerings. But, the question is: why we calculated from both left and right directions and why we took the maximum?

A mountain is made from both left and right upstrokes as shown in the figure:

img

If it was only made of left upstroke, we would easily increase the values going upwards but if it was made of both the left and the right upstroke, there is a problem.

img

So, to decide upon the value in such a situation, we have filled 2 dp arrays one from left to right and the other from right to left to get both the upstrokes. Why did we take the maximum?

The maximum value will satisfy the numbers on both left and the right upstrokes as it will be larger than all the values on either side of it i.e. it will be the correct peak. Hence, we took the maximum of the two values at every point.

So, dear reader, we hope that you have got everything. You may refer to the solution video to clear your doubts regarding the "why" of the problem completely. With this, we have completed this problem.

Suggestions:

Here are a few suggestions from our side that you don't want to miss:

  1. We suggest you refer to the complete solution video once as it will help you understand the concepts in depth and will help in giving you the best insight.
  2. We have solved this problem in O(n) time complexity using 3 loops. Can we solve this problem using less number of loops but the same complexity? Try this out on your own. Till then, Happy Coding!!!

Temple Offerings
Author: Guneet Malhotra
 
Run
Id Name