Why is my Java Solution so Slow?


  • 0

    I'm a C++ developer by trade but am doing these exercises in an attempt to gain competence in Java.

    I have developed a solution to this problem but it only beats 31.63% of javasubmissions, however to me it looks functionally identical to 'UpTheHell's solution which reportedly beats 98% of solutions. I'm just wondering what it is that is so expensive in my solution.

    My solution:

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // Quick Return if only 1 number
            if(l1==null) return l2;
            if(l2==null) return l1;
    
            // Dummy node used to start the list
            ListNode newNode = new ListNode(-1);
            ListNode rv = newNode;
    
            // Declare variables before loop
            int carry=0, digitSum;
    
            // Loop over all input digits
            while (l1 != null || l2 != null || carry != 0)
            {
                digitSum=carry;
                
                if (l1 != null)
                {
                    digitSum += l1.val;
                    l1 = l1.next;
                }
    
                if (l2 != null)
                {
                    digitSum += l2.val;
                    l2 = l2.next;
                }
    
                newNode.next = new ListNode(digitSum % 10);
                carry = digitSum / 10;
                
                newNode = newNode.next;
            }
            
            // Return node after dummy
            return rv.next;
        }
    }
    

    UpTheHell's ssolution:

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null) return l2;
            if(l2==null) return l1;
    
            int carry=0;
            ListNode fakeHead=new ListNode(9); // add all node at the tail of fakeHead
            ListNode tail=fakeHead;
    
            while(carry>0 || l1!=null || l2!=null){ //check if next node exsits
                int n1=l1==null?0:l1.val;  // get value of number 1
                    l1=l1.next;
                    
                int n2=l2==null?0:l2.val; // get value of number 2
                if(l2!=null)
                    l2=l2.next;
    
                int sum=n1+n2+carry;
                carry=sum/10; // calculate carry
    
                ListNode cur=new ListNode(sum%10);
                tail.next=cur; 
                tail=cur; // add node at the end of tail
            }
            return fakeHead.next;
        }
    
    }
    

  • 0

    I suggest you submit UpTheHell's solution and see what happens.


  • 0

    @StefanPochmann
    Yeah, I actually did try running his and it fails due to the missing "Null check" for the line l1=l1.next;.

    When I added the null check his solution came out at about 31% as well so I figured I'd misunderstood something.

    Is it possible that UpTheHell's solution was in the top 2 percentile when it was first written but that it's now slipped to 31%? That seems a long way to slide. Is it likely that UpTheHill simply lied about how many submissions this solution beat. Seems a silly lie to tell as surely you're bound to be caught out, but the fact that there is that missing null check seems odd too.

    In any event, even if UpTheHill's solution is invalid can anyone see how to improve my solution. It seems close to optimal as it is but 31% is surprisingly low.

    One improvement I was considering was that if one number runs out of digits, and there is no carry you could just tack the remainder of the remaining number on the end of your answer thus preventing the need to create new nodes.

    As in for 1,000,001 + 1 you could simply reuse many of the original numbers digits:

    [0] -> [0] -> [0] -> [0] -> [0] -> [0] -> [1]
    [1]     ^
     =      |
    [2] - - +
    

  • 0

    @S.Bartfast said in Why is my Java Solution so Slow?:

    Is it possible that UpTheHell's solution was in the top 2 percentile when it was first written but that it's now slipped to 31%?
    That seems a long way to slide.

    Not really. Could be the difference between 3.49 ms and 3.50 ms or between 3.99 and 4.00 (depending on how leetcode rounds, which I don't know).

    Also, a large test case was added just recently, and the statistics probably still include the times from before.


  • 0

    Man. I just implemented a recursive solution that takes advantage of using the tail of long numbers as discussed above, and I'm still coming in at 31.63%

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            return addTwoNumbers(l1, l2, 0);
        }
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
            // Quick Return if only 1 number.
            if (carry == 0)
            {
                if (l1==null) return l2;
                if (l2==null) return l1;
            }
            
            int digitSum = (l1==null?0:l1.val) + (l2==null?0:l2.val) + carry;
    
            // Create a new node for the first digit
            ListNode newNode = new ListNode(digitSum % 10);
            
            // Recersivly append the next digit.
            newNode.next = addTwoNumbers(l1==null?l1:l1.next, l2==null?l2:l2.next, digitSum/10);
    
            // Return the resault.
            return newNode;
        }
    }
    

Log in to reply
 

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