Why this results in StackOverflowError?


  • 1
    M
    public class Solution {
        private int maxNode = -1;
        private int maxDist = 0;
        private ArrayList<Integer>[] adj;
        private int[] h1;
        private int[] h2;
        private int[] prevDep;
        private int[] suc;
        
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            List<Integer> res = new ArrayList<>();
            h1 = new int[n];
            h2 = new int[n];
            prevDep = new int[n];
            suc = new int[n];
            adj = new ArrayList[n];
            
            if (edges == null || edges.length == 0) {
                if (n == 1) {
                    res.add(0);
                }
                
                return res;
            }
            
            int i, j;
            int cur;
            int cnt;
            
            for (int[] e : edges) {
                i = e[0];
                j = e[1];
                
                if (adj[i] == null) {
                    adj[i] = new ArrayList<>();
                }
                
                if (adj[j] == null) {
                    adj[j] = new ArrayList<>();
                }
                
                adj[i].add(j);
                adj[j].add(i);
            }
            
            dfs(0);
            
            cur = maxNode;
            cnt = h2[maxNode];
            
            while (cnt != (maxDist - 1) / 2) {
                cur = suc[cur];
                cnt++;
            }
            
            res.add(cur);
            
            if (maxDist % 2 == 0) {
                res.add(suc[cur]);
            }
    
            return res;
        }
        
        private void dfs(int n) {
            h1[n] = prevDep[n];
            
            for (int next : adj[n]) {
                adj[next].remove(Integer.valueOf(n));
                
                prevDep[next] = prevDep[n] + 1;
                suc[next] = n;
                
                dfs(next);
                
                int tmpDep = h1[next] == prevDep[next] ? h2[next] + 1 : h1[next] + 1;
                
                if (tmpDep > h1[n]) {
                    h2[n] = h1[n];
                    h1[n] = tmpDep;
                    suc[n] = next;
                }
                else if (tmpDep > h2[n]) {
                    h2[n] = tmpDep;
                }
            }
            
            if (h1[n] + h2[n] + 1 > maxDist) {
                maxDist = h1[n] + h2[n] + 1;
                maxNode = n;
            }
        }
    }
    

    I've tried my best to remove the number of parameters passed into the dfs() method. But it still results in StackOverflowError. But I've seen similar solution that's accepted. Can anyone help? Thx!


  • 0
    L

    After several attempts, I somewhat figure out the reason. If you change the type of your adj from ArrayList to (say) HashSet, your code simply passes through.

    In fact, the remove operation of ArrayList runs in linear worst time, not O(1) time, which may result in an O(n2) solution. But I am not quite sure why it causes the StackOverflowException, and in fact, your code does not trigger the exception in my local machine for the same test case.

    I am still investigating about this, and if you have any thoughts, please let me know. :-)


  • 0
    M

    Thank you so much for the reply. Nice catch! Didn't think much about the O(n) complexity of the remove operation. I used it to avoid passing in the parent. Still SOF after changing to HashSet.


  • 0
    M

    Solved after using a boolean array visited.. So the stack is just one call away from overflow?.. Interesting


  • 0
    L

    I guess it might be because the Stack Limit set by Leetcode is relatively small, and for this particular problem, the memory occupied is just above or below the threshold, which makes the behavior really subtle. In fact, I changed ArrayList to HashSet and got accepted. Anyway, I guess it is more important to know how the solution works. :-P


  • 0
    M

    Agree. Thank you!


Log in to reply
 

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