very easy to understand 4ms O(1) solution with detailed explanation


  • 1
    Q

    Let's clarify the question first: what is considered to be O(1) in this question

    The following space should not count:

    1. the result array.
    2. the stack in memory when calling recursion

    And all other non constant variable should be not be considered as O(1). Thus, any list (arraylist, linkedlist etc), map should not count as the O(1) solution.

    In order to come up with a O(1) solution, let's come up with a O(n) solution first. A simple example would be to traverse the tree in order and get a list. The list then will be sorted. Then count the occurrence of each element and get the max occurrence. Having the max occurrence, we can then find out every element with same occurrence.

    This is a 3 pass solution. An O(1) solution will have similar process. In order to get rid of the sorted array holding all elements, we have to go recursive since the memory stack doesn't count (I think it's cheating). We can traverse the tree in order recursively and only remember the previous element.

    Then, we need to know the max occurrence and how many elements have that occurrence. The size of the final result is needed because we can't use a list but array which requires the size when declared in JAVA (maybe other language doesn't have know the size ahead?). We can then traverse the tree twice, the first is to get max occurrence and how many elements have that occurrence, the second time is to construct the final result.

    public class Solution {
         int size;
         int count;
         TreeNode pre;
         int local_count;
        
        public  int[] findMode(TreeNode root) {
            if (root == null) {
                return new int[0];
            }
            
            size = 0;
            count = 0;
            local_count = 0;
            
            helper(root, null);
            int[] res = new int[size];
            local_count = 0; // reset the local_count var
            helper(root, res);
            
            return res;
        }
        
        private void helper(TreeNode cur, int[] res) {
            if (cur == null) {
            	return;
            }
            
            helper(cur.left, res);
            
            if (pre != null && pre.val == cur.val) {
            	local_count++;
            }  else {
            	local_count = 1;
            }
            
           // only in the first pass, we calculate the count and size
            if (res == null) {
            	if (local_count > count) {
            		count = local_count;
            		size = 0;
            	}
            	if (local_count == count) {
            		size++;
            	}
            }
            
            if (res != null && local_count == count) {
                res[--size] = cur.val;
            }
            
            pre = cur;
            
            helper(cur.right, res);
        }
    }
    

    Here I used the result array being null or not to decide if it is the first pass or the second. If you don't like this, you can simply pass in a boolean. As seen in the code, only in the first pass, we calculate the occurrence. In the second pass, we only need to check if an element has max occurrence


Log in to reply
 

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