Java AC Solution, not sure this should be called extra space


  • 0
    G

    Just see it as a sorted integer array.
    The only thing I care about is that what should be treated as "extra space"? Well at least we need to memorize those elements which are equally frequent until we find something more frequent. So for worst cases, we still need O(n) space to store everything when every element appears exactly once.
    Below is my solution, welcome any comments.

    List<Integer> list = new ArrayList<>();
    Integer prev = null, maxFreq = 0, count = 0;
    
    public int[] findMode(TreeNode root) {
        if (root == null) return new int[0];
        inorder(root);
        if (count == maxFreq) {
            list.add(prev);
        } else if (count > maxFreq) {
            list = new ArrayList<>();
            list.add(prev);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev == null) {
            prev = root.val;
            count++;
        } else if (root.val == prev) {
            count++;
        } else {
            if (count == maxFreq) {
                list.add(prev);
            } else if (count > maxFreq) {
                list = new ArrayList<>();
                list.add(prev);
                maxFreq = count;
            }
            prev = root.val;
            count = 1;
        }
        inorder(root.right);
    }

  • 0

    @glbydl said in Java AC Solution, not sure this should be called extra space:

    So for worst cases, we still need O(n) space to store everything when every element appears exactly once.

    I think it's reasonable to not count the result space as extra space. That is, extra space being in addition to the obvious space needs of input and output. Otherwise the problem would ask us to do something impossible. But I mention an even "worse" case here: https://discuss.leetcode.com/topic/77335/proper-o-1-space


Log in to reply
 

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