Shinzy's blog

Why is this giving TLE?
By Shinzy, history, 8 months ago, In English

Here's The Problem Link:

Problem Link

I analyzed the Time Complexity of my code as O(T*N) and Space Complexity as O(1)

Which should technically satisfy the constrains given, But to my surprise it gives TLE on Test 3:

Here's My Java Submission:

Java Submission

Here's My Python Submission:

Python Submission

Please Help Me Out Guys!, Thanks For Your Valuable Time :)

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
8 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

The solution is doing a million string addition operations in the worst case, which is very expensive and take linear time.

Doing += to a string creates a new string every time. Maybe a string builder will help, but i don't know about python that much

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks For The Help, I really appreciate it!

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because of the string operations he's not right about the time complexity. The string prepends take linear time, so the solution is actually $$$O(T*N^2)$$$

    → Reply