Heap structure bubble up update sum O(n)


  • 0
    S

    hi, I index tree like a array i start as 1
    1
    2 3
    4 5 6 7

    i should be find by the depth d and position p

    after that by look up parent node cumulated sum we can calculate the current
    sums[i] = sums[i/2] + v;

    after that we only the cumulated sum on the children's node
    we can start from the leaf and bubble up by setting zero of all its parent.

    class Solution {
        public int pathSum(int[] nums) {
            int[] sums = new int[(1 << 4) + 1];
            int result = 0;
            for (int n: nums) {
                int d = n / 100;
                int p = (n / 10) % 10;                
                int v = n % 10;
                            
                int i = p + (1 << (d - 1)) - 1; // index like heap
                sums[i] = sums[i/2] + v;            
            }
            
            int r = 0;
            
            for (int i = sums.length - 1; i > 0; i --) {
                int j = i;
                if (sums[j] != 0) {
                    j /= 2;
                    while (sums[j] != 0 && j != 0) {                    
                        sums[j] = 0;
                        j /= 2;
                    }    
                }            
                r += sums[i];
            }
            return r;
        }
    }
    

Log in to reply
 

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