CODEWITHSUNDEEP
javastringtime-complexitysingly-linked-listpalindrome
ARPAN NANDI
ARPAN NANDI

Reputation: 34

Leetcode 234. Palindrome Linked List, String solution gives time exceeded error, can anyone explain why?

Leetcode :234

This is the solution i have given.

class Solution {

    public boolean isPalindrome(ListNode head) {
       String s= "";
       String p= "";
        while(head != null){
            s= s+head.val;
            p = head.val+p;
            head = head.next;
        }
        return s.equals(p);
    }
}

I can understand i am creating multiple strings in string pool. but it doesnt show memory exceeded. it shows "Testcases passed, but took too long."

Output Error

Can someone kindly explain how is that exceeding time limit whereas all the other solutions has minmum of two loops? be it two pointer solution or the list solution or the stack solution.

I was expecting it to run properly, because I am just using one loop to create both the reverse and normal string and as far as i know equals is a O(1) process. So how does the time limit exceeds?

Upvotes: -1

Views: 182

Answers (1)

trincot
trincot

Reputation: 350766

I am just using one loop to create both the reverse and normal string and as far as i know equals is a O(1) process.

It is not, but that is not the problem. The slowdown is in the loop body. Both s+head.val and head.val+p are expressions that need to visit each character in the involved strings, and so they have a O(𝑛) time complexity where 𝑛 is the current size of s or p respectively. And this gives a total time complexity that is O(𝑛²).

To improve on this, use StringBuilder, whose append method has an amortised time complexity of O(1). Don't build p in the loop, only s, and reverse s at the end of the loop:

class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuilder s = new StringBuilder();
        while (head != null) {
            s.append(head.val);
            head = head.next;
        }
        return s.toString().equals(s.reverse().toString());
    }
}

This has the optimal -- O(𝑛) -- time complexity.

Note that this would not work if the values of the nodes could have multiple characters (when turned to string representation). But as the code challenge specifies in its constraints section that the values are single digit numbers, this is not an issue.

The auxiliary space complexity of this solution O(𝑛). A next challenge would be to solve this problem with just O(1) auxiliary space complexity...

Upvotes: 1

Related Questions