12ms Java, beat 99.77%, using ArrayList/Array to store/sort sums for each node


  • 0
    W

    The submission is 12ms and beating 99.77%. But given Arrays.sort()'s O(nlogn) complexity, i don't see why it can beat other solutions using HashMap in terms of complexity.

    My solution stored sum of each node directly into a ArrayList during Post Order traversal. Later the arraylist of sums are transformed into Array which can then be sorted (O(nlogn)) and aggregated.

    '''
    public class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
    if (root == null) return new int[0];

        ArrayList<Integer> sums = new ArrayList<Integer>(); 
        getAllSums(root, sums); 
        
        return findMostFrequentSums(sums);
    }
    
    /*
    * recursive find sums for each node.
    */
    public int getAllSums(TreeNode n, ArrayList<Integer> sums){
        if (n == null) return 0;
        
        int currSum = n.val + getAllSums(n.left, sums) + getAllSums(n.right, sums);
        sums.add(currSum);
        //System.out.println("n.val =" + n.val + ", currSum= " + currSum);
        return currSum;
    }
    
    public int[] findMostFrequentSums(ArrayList<Integer> sums){
        
        //System.out.println(" sums = " + sums);
        int[] sortedSums = toIntArray(sums); 
        Arrays.sort(sortedSums);
        //System.out.println(" sorted = " +  Arrays.toString(sortedSums));
        int maxFrequence = -1;
        int currSum = sortedSums[0];
        int currFrequence = 1;
        
        ArrayList<Integer> tiedSums= new ArrayList<Integer>();
        for (int i = 1; i < sortedSums.length ; i++){
            
            if (sortedSums[i] != currSum) {
                if (currFrequence > maxFrequence) { // find new most frequence sum
                    maxFrequence = currFrequence;
                    tiedSums.clear();
                    tiedSums.add((Integer)currSum);
                    
                } else if (currFrequence == maxFrequence){ // find another sum also has max frequence
                    tiedSums.add((Integer)currSum);
                }
                currSum = sortedSums[i];
                currFrequence = 1;
            } else {
              currFrequence ++;
            }
        }
        if (currFrequence > maxFrequence) {
            tiedSums.clear();
            tiedSums.add((Integer)currSum);
        } else if (currFrequence == maxFrequence){
            tiedSums.add((Integer)currSum);
        }
        return toIntArray(tiedSums);
    }
    
    public int[] toIntArray(ArrayList<Integer> sums){
        int[] res = new int[sums.size()];
        for (int i = 0; i < sums.size(); i++){
            res[i] = (int) sums.get(i);
        }
        return res;
    }
    

    }
    ''''


Log in to reply
 

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