# Happiness Counter

Happiness Counter is the fourth problem of the HackerRank Contest GOC-18. It is a hard problem. The minimum requirement to solve this problem is the knowledge of dynamic programming. To solve this problem we discuss two solution.

You are given \(n\) houses with some number of floors and you are asked to find the Happiness number of each house on the basis of following condition:

- if two adjacent houses are having different number of floors then the member of the house having higher number of floors will have higher Happiness number.
- If two adjacent houses are having same number of floors then Happiness number relative to each other doesn’t matter.

Lets try to understand with the Sample test case provided.

**Input:**

\(6\)

\(1\, 4\, 3\, 6\, 2\, 1\)

**Output:**

\(10\)

We can distribute the happiness in the following way: \(1\, 2\, 1\, 3\, 2\, 1\).

The second house has to receive more Happiness number than the first due to its higher number of floors. The fourth must receive more than fifth, which in turn must receive more than sixth. Thus the total becomes \(10\).

**Naive Approach**

To follow the given rule, a house must be offered at least \(x+1\) where \(x\) is maximum of following two:

- Number of houses on left in increasing order.
- Number of houses on right in increasing order.

A naive method of solving this problem would be for each house, go to the left until altitude increases, and do the same for the right.

This Naive Approach has complexity of \( \mathcal O(n^2) \) for each test case which is definitely going to give you **TIMEOUT**.

**Dynamic Programming Approach**

By using Dynamic Programming, we can improve the time complexity. In this method, we create a structure of length \(n\) which maintains the maximum decreasing chain to the left of each house and the maximum decreasing chain to the right of each house. We go through once from \(0\) to \(n\) setting the value of left for each house. We then go from \(n\) to \(0\) setting the value of right for each house. We then compare the two and pick the maximum for each house.

We provide C++ code for the above problem:

#include <iostream< using namespace std; // To store count of increasing order house // on left and right (including current house) struct House { int L; int R; }; House chainSize[1000001]; int n, houseHeight[1000001]; // Returns count of minimum offerings for // n houses of given heights. int offeringNumber() { // Initialize counts for all houses for (int i = 0; i < n; ++i) { chainSize[i].L = -1; chainSize[i].R = -1; } // Values corner houses chainSize[0].L = 1; chainSize[n-1].R = 1; // Filling left and right values using same // values of previous(or next) for (int i=1; i<n; ++i) { if (houseHeight[i - 1] < houseHeight[i]) chainSize[i].L = chainSize[i - 1].L + 1; else chainSize[i].L = 1; } for (int i=n-2; i>=0; --i) { if (houseHeight[i + 1] < houseHeight[i]) chainSize[i].R = chainSize[i + 1].R + 1; else chainSize[i].R = 1; } // Computing max of left and right for all // houses and returing sum. int sum = 0; for (int i = 0; i < n; ++i) sum += max(chainSize[i].L, chainSize[i].R); return sum; } int main() { std::ios::sync_with_stdio(false); int t; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) cin>>houseHeight[i]; cout<<offeringNumber()<<endl; } return 0; }

Time complexity of above method is \( \mathcal O(n) \).

This editorial is contributed by Ravi Kant. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help others. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.