Histogram Melting Time


  • 0
    N

    Given a histogram chart with values say {5,4,3,6,0,1}. Get the total count required to completely melt the histogram. A column with value 5 has 5 blocks in it. Any block which has air on any of its side gets melted.

    Sample 1

    {5,4,3,6,0,1} - > {0,3,2,0,0}->{0,0,0,0,0} => count=3

    Sample 2

    {0,1,1,1,1,0} - > {0,0,0,0,0} => count=2


  • 2
    N
    public void histogram(int[] values)
    	{		
    		int[] tmpvalues= new int[values.length];
    		int count =0;
    		tmpvalues[0]=0;
    		tmpvalues[values.length-1]=0;
    		int flag =1;
    		while(flag==1)
    		{
    			for(int i=1;i<values.length-1;i++)
    			{
    				if(values[i]>values[i-1] || values[i]>values[i+1])
    				{
    					tmpvalues[i]=Math.min(values[i-1], values[i+1]);
    				}
    				else
    				{
    					if(values[i]>0)
    					{
    						tmpvalues[i] = values[i] -1;
    					}
    				}
    					
    			}
    			System.out.println("\n");
    			for(int i=0;i<values.length;i++)
    			{
    
    				System.out.print(tmpvalues[i]+"-");
    				values[i] = tmpvalues[i];
    			}
    			count++;
    			for(int i=0;i<values.length;i++)
    			{
    				if(values[i]!=0)
    				{
    					flag=1;
    					break;
    				}
    				else
    				{
    					flag=0;
    				}
    			}
    		}
    		
    		System.out.println("Count = "+count);
    	}

  • 0
    H

    Can you explain this question?
    How does the melting work exactly?
    Why before melting it was length 6 and after melting it become 5 length?


  • 0
    D
    def meltTimes(self, heights):
        s = i = prevHeight = 0
        while i < len(heights):
            s += heights[i]
            newHeight = 0 if i == 0 or i == len(heights) - 1 else max(0, min(min(prevHeight, heights[i + 1]), heights[i] - 1))
            prevHeight = heights[i]
            heights[i] = newHeight
            i += 1
        return 1 if s == 0 else 1 + self.meltTimes(heights)

  • 1
    P

    Very much like 298 Game of Life


  • 1
    C

    @hyacinthD18 Hey, so I draw the diagram. The leftmost column and rightmost column will all melt because their other side is in contact with air. That means you'll only be protected if your neighbors are all higher than you. But any column will at least have their top in contact with air.

    So from these, it's easy to derive a recursive formula. Let C[i][j] be the height of i column in j iteration. C[i][j+1] = min( C[i][j] - 1, C[i+1][j], C[i-1][j] ). (Out of boundary columns can be treated as 0.)


  • 1
    M

    Here's a python pseudocode to solve the problem. Runtime O(n^2)

    def solve(hist):
        n=len(hist)
        left=[]
        right=[]
        while(1):
            if(len(hist)==0):
                break
            for i in range(len(hist)):
                if(i==0 or left[i-1]<hist[i]):
                    left.append(hist[i])
                    del hist[i]
            for i in range(len(hist)-2,-1,-1):
                if(i==n-1 or right[i-1]<hist[i]):
                    right.append(hist[i])
                    del hist[i]
            count+=1
        return count

  • 0
    H

    @pushazhiniao Actually Simulating this like Game of Life would take O(n^2) time.

    We can do BFS to solve it in O(n) time.

    • Add all the 'exposed' nodes to the queue and marked the as visited.
      -When a node is popped, add all it's 'unexposed' neighbors to the queue and ,mark them as visited.
    • A measure of depth can be maintained with each node added to the queue.

  • 0

    Another way to think about the problem is to realize that you only need to find the longest subsequence between two zeroes (air) after removing duplicates (a duplicated is considered same block). The size of that subsequence will be the maximum time needed to melt everything. time_to_melt = 1 + ceil(len(subsequence)/2). In the examples such sequences had size 4 and 1, so the results are 3 and 2. Time complexity o(n) and space o(1).


  • 0
    G

    @pbg that's not correct try [3,1,4,1,5,1,6,1]


  • 0

    @godwinls it does not seem incorrect. Maybe I am interpreting the problem wrong. According to my proposal time_to_melt = 1 + ceil(len(subsequence)/2). In your example the subsequence is all the sequence (no zeroes in the sequence). So time_to_melt = 1 + 8/2 = 5

    This corresponds to these steps:
    [3,1,4,1,5,1,6,1]
    [0,1,4,1,5,1,6,0]
    [0,0,4,1,5,1,0,0]
    [0,0,0,1,5,0,0,0]
    [0,0,0,0,0,0,0,0]

    5 steps


  • 0
    P

    @pushazhiniao hello i am unable to get the problem in less than o(n^2). do u have the optimal solution in lesser time complexity [someone mentioned below O(n)] using queue


  • 0

    Say the array is A. Consider the transformation T A = the array after one turn. Evidently, T: A[x] -> min(A[x-1], A[x] - 1, A[x+1]), where we assume that the array is padded with zeros. (Let's also assume any negative values of the array are replaced by zero for convenience.)

    Let's investigate T^2 A[x]. This is:
    min(T A[x-1], T A[x] - 1, T A[x+1])
    = min(min(A[x-2], A[x-1]-1, A[x]), min(A[x-1], A[x] - 1, A[x+1]) - 1, min(A[x], A[x+1] - 1, A[x+2]))
    = min(A[x-2], A[x-1] - 1, A[x] - 2, A[x+1] - 1, A[x+2]).

    We can show by induction or otherwise that:
    T^k A[x] = min_{0 <= j <= k} (A[x ± j] - (k-j) )

    When T^k A[x] is positive, all of these terms are positive, namely A[x ± j] > k-j for all 0 <= j <= k. Graphically, A contains a pyramid with heights [1, 2, ..., k, k+1, k, ..., 2, 1], and we want to know the largest pyramid contained in A.

    If we can know L(x) = the largest k with up-staircase [1, 2, 3, ..., k] that ends at A[x], and R(x) = the largest k with down-staircase [k, k-1, ..., 2, 1] starting at A[x], then the largest pyramid centered at x will have height min(L(x), R(x)), and we can find the maximum over all x. Finding R is similar to finding L, so let's just focus on finding L.

    Say L(x) = k, and let's figure out what L(x+1) is.

    • If A[x] >= k+1, L(x+1) is k+1.
    • If A[x] < k+1, then L(x+1) is A[x].

    Thus, L(x+1) = min(L(x) + 1, A[x]) is a recursion for L.

    Putting that all together:

    def solve(A):
        A = [0] + A + [0]
        def staircase(A):
            #L[x] = largest staircase ending at x
            L = []
            for i, u in enumerate(A):
                L.append(min(L[-1] + 1, u) if i else 0)
            return L
        L = staircase(A)
        R = staircase(A[::-1])[::-1]
        return max( min(L[i], R[i]) for i in xrange(len(A)) ) + 1
    

  • 0

    @cau-seoi-dyun-dou Sorry I still don't understand how 6 columns in example one turned to 5 columns and how the values changed. Could you/anyone give some more explanation on it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.