Getting a TLE when trying to solve the "Maximum Subarray"problem on Leetcode

Python
#1

I was trying to solve the Maximum Subarray - LeetCode on Leetcode and my code is getting a TLE.

My code:

class Solution:
    def maxSubArray(self, nums):
        maxSum = nums[0]
        for i in range(0, len(nums)):
            for j in range(0, len(nums)):
                if sum(nums[i:i+j+1]) > maxSum:
                    maxSum = sum(nums[i:i+j+1])
        return maxSum
#2

Right, what you have there is what we call a “brute force” solution. It is just trying every conceivable possibility. This has a loop inside a loop so it is an O(n^2) solution. This will increase in time exponentially as the data get larger.

If I remember correctly, there is an O(n) solution to this.

A lot of these on these algo sites are trying to get you to find the less obvious. more elegant solution. But it will take some thinking.

1 Like
#3

Yeah, I heard of that before.

I’m not able to find any other way to solve this problem.

I thought of it for an hour I was unable to come up with anything below O(n2)

#4

I thought of it for an hour I was unable to come up with anything below O(n2)

Yup, it’s a tricky one, that’s for sure.

Keep in mind that if I were doing this on a job interview, if I wasn’t confident in my “better” approach, I’d probably do the brute force first and then try the more subtle one.

#5

I’m glad I’m not the only one finding it tricky.

Ok.

#6

It’d be great if you could show me how I can come up with an O(n) solution.

#7

Just click on the “discussion” tab and find literally hundreds of topics in which people share working solutions.

If you want to come up with it yourself - well good luck?
I mean, you can start by reading the task and wondering, why it’s only asking for the sum, not the array itself. You are looking at every possible subarray - so you could actually return the subarray itself. Yet the test is not asking for the array itself, almost as if you can find the solution without creating any subarray.
You can spent hours trying to figure that out, if you want.

Personally, I’d just look at a solution, try to understand it and then move on once I can.

#8

This sort of thing is why I’m lukewarm about Leetcode and similar sites. It’s all about recognizing and replicating the correct algorithm rather than practicing problem solving.

2 Likes
#9

Okay, I’ll just do that.

#10

I thought I was expected to come up with my own solution lol. I actually looked the solution up and it’s called “Kadane’s Algorithm” and fun fact, he came up with this in a minute.

#11

I would be dubious of any story of an algorithm being developed in a minute, but even if it was, that would be after years of experience working with algorithms.

But rarely do you need to invent a brand new algorithm. There are tons out there for these Leetcode types of problems.

#12

I hate to be pedantic, but in this case it matters. An O(n^2) solution does not increase in time exponentially as the data gets larger. It increases quadratically.

An O(x^n) solution, for fixed x, increases exponentially. There’s a massive difference in those asymptotic growth rates.

As for the solution, the given code continually recomputes subarray sums. There’s no reason to do that once we know there’s one bigger. Memoization (trading space for time) will help quite a bit here.

jrm

1 Like
#13

Yeah, fair point. I’m aware of the distinction. While you’re definitely correct, the word “exponentially” also has a more loose meaning in common speech. A word lik “quadratically” might be off putting or seem pedatically pompous. But I guess since we are discussing tecnicalities, it is appropriate to get technical.

#14

I think you’d learn a lot more if you struggled with it. I know it’s tough, but when you run into a tough problem at work, there usually won’t be a way to cheat. Part of what you are learning here is how to force yourself to turn a problem over in your mind and think of it a different way, to go beyond your most instinctual way of thinking about the problem. You aren’t going to learn that by peaking at answers.

#15

He would’ve found patterns in them and just applied them to his own. Now it doesn’t seem that impressive ; but still, pretty great.

#16

Okay. So was I expected to be aware of this algorithm or am I supposed to come up with this on my own?

#17

Wow, I didn’t know that. I didn’t know why people called O(n2) quadratic time complexity.

You’re not being pedantic at all.

#18

I meant I would do it in this case. Not every time.

#19

A way would be to Google for the algorithm, in this way you find a language agnostic solution and have to apply to this problem

Once you found a solution and it is not fast enough, try optimising, changing approach etc. but most often than not the most efficient algorithm already exists

I would suggest to avoid the algorithm already implemented in the language you are using

2 Likes
#20

Yes. And no. I don’t think it’s reasonable to expect someone to be aware of every algorithm that’s every been developed. I do think it’s reasonable to expect a developer to be able to google for existing algorithms. I also think it’s reasonable for a developer to be able to develop algorithms for relatively simple problems from first principles.

However…that last point strays into the relatively ill-defined distinctions between programming, software engineering, and computer science. I’m a computer scientist, so I expect developers to understand and be able to apply design and analysis of algorithms at least at the undergraduate level. I also freely admit that’s probably not reasonable. Several of the programmers I’ve managed were unfamiliar with algorithm design and analysis. Ultimately, that was a limiting factor. So we trained them better.

jrm

2 Likes