a C++ algorithm problem- skyscrapers

[exception]

I must have overlooked the concrete running time. Still, the work has to be performed on the algorithm basis, not the implementation/optimization basis (just look at the code...)

for(int j=hts[i];j<=cur;j++)
  ++dp[j];

...obviously, the pre-/postincrement difference has much less impact than a change to "dp[j]+=cur-hts[i]" (assuming the increment does what one would suppose, of course)

A balanced tree would be suitable (and perhaps the best choice), but any DS which can perform lookups, insertions and deletions in amortized O(log n) time would work.

[jereme]

the algorithm is correct as I tried using many test cases and the answer was correct everytime.. anyways, I'm giving you a detailed explanation, that wil help u better understand it...

Consider this test case :

Buildings are : 2 3 6 1 5 2 (represented by their heights)
Days are : 6 2 1 5 3 ( represents the n-th day for which we have to find regions)


Hence, vector hts will contain { 2,3,6,1,5,2 }
and vector dts will contain {6, 2, 1 , 5, 3 }

Now, vector dp is supposed to contain the "number of regions" "
"for every possible day" starting from day 0 to day N ( where N is the day after which all the "buildings" will be flooded - which means N=maximum height of all buildings. ) For our problem, let N= {0,1....6} (as 6 is the last day i.e. for any day > 6, the number of regions is 0 ).

So let us assume dp.assign(7,0);, that wil make it easier to understand.

So vector dp contains: {0,0,0,0,0,0,0}

And we have a temporary variable "cur" which tells the height of the building "just before" the current one.


Now here's what happens : (Note all "increments" are by 1 )

0 cur -> 0
1 Run the loop from 0 to hts.size() (i.e. <number of buildings>)
2   If the current building's height is greater than "cur" (i.e. <height of prev. building>)
3      Set cur -> hts[i] - 1
4   Else
5    Increment all the values in "dp" from hts[i] to cur
6    Set cur -> hts[i] -1
7  EndIf
8 end loop
9 Increment all the values in "dp" from 0 to "cur"
10 "dp" contains the number of regions of every possible day
11 extract from "dp" the "required" solutions only, and return them as "ans" 

Now lets ur dry run this on our test case :

Initially,

hts ={ 2,3,6,1,5,2 }
dts = {6, 2, 1 , 5, 3 }
dp = {0,0,0,0,0,0,0}
cur=0

Now how my algo works is to go forward in hts array, until it finds a "drop" in height of the building.
In the given case, the drop occurs at (6 -> 1) & (5 -> 2)

Now take the 1st drop i.e " 6 -> 1 " : increment all values from dp[1] to dp[5]

hence, dp = { 0,1,1,1,1,1,0 }

Now take the 2nd drop i.e. "5 -> 2" : increment all values from dp[2] to dp[4]

hence dp = { 0,1,2,2,2,1,0 }

Finally, the LOOP ends here and STEP 9 is executed i.e. to increment all values from dp[0] to dp[cur] & cur=2-1=1

hence dp= { 1,2,2,2,2,1,0 }

This is the final dp, which means :

at day 0 : no. of regions=1
at day 1 : no. of regions = 2
.
.
.
at day 5 : no. of regions = 1
at day 6&above : no. of regions =0

finally, the ans vector will contain : { 0,2,1,2,2 }

You can test run the algo on any test case,it works! But it looks to me the algorithm is quite efficient,, but not the implementation....

[exception]

Argh. I just realized that I completely messed up the indices (no excuse for that, but writing the code with in the words you used to describe it in the first place might have been more beneficial for a faster understanding than "i" and "j"...)

Your algorithm has an average running time of O(b*h) (assuming uniformly distributed heights in the range [0; h] where h is the maximal height).

This is because the outer loop runs b times, the inner loop is executed cur-hts[i] times, which is in [0;h] and on average will be h/6 (if only taking positive height differences into account and assuming, as mentioned, uniformly distributed heights). So the average case complexity is O(b*(h/12)) = O(b*h).

As I outlined, this can be improved to O(b*log b) (+t, since you have to use this not-so-nice output format... I forgot that before).