#🔒 any suggestions on how to reduce the time complexity of this code for the following question

72 messages · Page 1 of 1 (latest)

balmy rampart
#

Q) https://leetcode.com/problems/container-with-most-water/

class Solution:
    def maxArea(self, height: List[int]) -> int:
        b=[]
        ans=0
        m=0
        for i in range(0,len(height)):
            for j in range(0,len(height)):
                if j==i:
                    continue
                if j>i:
                    width=j-i
                else:
                    width=i-j
                if height[i]>height[j]:
                    length=height[j]
                else:
                    length=height[i]
                p=width*length
                if p>m:
                    m=p
                if m>ans:
                    ans=m
        return ans
dusky owlBOT
#

@balmy rampart

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
balmy rampart
#

Right now i am getting the correct asnwer

#

but since i have used nested loop i am getting time complexity of order (n^2)

#

i would like suggestions to imrpove that

late ruin
balmy rampart
#

and saw

#

soltuion

#

apprlty i have to use two pointers

#

but i didnt really understand how two pointers works

# 
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l=0
        r=len(height)-1
        ans=0
        while l<r:
            n1=height[l]
            n2=height[r]
            w=r-l
            h=min(n1,n2)
            if height[l]<height[r]:
                l+=1
            else:
                r-=1
            area=w*h
            ans=max(area,ans)
        return ans
late ruin
# balmy rampart but i didnt really understand how two pointers works

The idea of two pointers is that at every step, you consider some slice of the sequence (between the first "pointer" and the second "pointer"). In the case of this problem, Suppose that you start at the edges:

1, 8, 6, 2, 5, 4, 8, 3, 7
^                       ^

The area is calculated as width * min(height1, height2) (a.k.a. (j - i) * min(height[j], height[i]) ).
Let's consider the starting case. We start at the highest possible width. If we take any other combination of points, we'll have a smaller width; so to have any chance of improving the area, we'll need a bigger height.

#

The height of the container is the smallest of the two, so if we want to increase the container height, we will need to move the smallest border eventually. Therefore we move the smallest pointer: 1, 8, 6, 2, 5, 4, 8, 3, 7 ^ ^ then we note the new container area and update the max_area if needed.

#

If we didn't move the 1 pointer, our container height would be capped at 1, but the width would only be decreasing. That's why we must move the "shortest" pointer.

balmy rampart
#

so basicly the task that my nested loop does

#

this one while loop does?

late ruin
#

Well, it does solve the same problem of course

#

In these problems, you reduce the complexity of your solution by considering fewer cases.

#

(for example, it won't consider the case of a container between 1 and 3)

balmy rampart
#

i somewhat understood how this works but i possibely couldnt have come up with this solution for the above question on my own

late ruin
#

That's perfectly fine. I had to look at the hints myself, because I haven't solved leetcode style problems in over a year 🙂

balmy rampart
#

i started solving questions like a week ago lol

late ruin
#

If you practice a lot, it will get easier

balmy rampart
#

im beginer

balmy rampart
late ruin
#

Why are you solving leetcode problems?

balmy rampart
#

i am trying to irmpove my coding skills

#

and to partice

late ruin
#

The best way to practice programming is to build projects.

#

LeetCode provides you with data-structures-and-algorithms problems, which can be helpful, but they're not representative of most of the code you're going to write, in most cases.

#

It also doesn't teach you anything about building larger programs, or maintaining existing code

balmy rampart
#

so should i spend time on leetcode or not? if yes how should use leetcode

late ruin
#

Have you built any projects on your own?

balmy rampart
#

no

#

i havent

#

i dont have enough knowldge in ml to start porjects yet

late ruin
#

You don't need ML to make programming projects, no

#

Start with something simple, like a calculator or a to-do list. Learn how to handle user input, how do handle errors, and how to work with files.

balmy rampart
#

if those count as projects

#

i have done many

#

then

#

lol

#

i made a atm system , a monthly expense tracker , a login system ,etc

late ruin
#

Do you have the code somewhere?

balmy rampart
#

anywhere

#

am i cooked?

late ruin
#

wdym cooked

#

Well, you might want to bulid a more complex project next, with more moving parts. If the expense tracker program doesn't have an HTML interface, add that (with Flask or Django) -- so that you can search the expenses via a browser

balmy rampart
#

so basically i should focus on making projects instead of leetcode?

late ruin
#

That's what I would recommend, yes

#

LeetCode is very different from "real programming", it's more of a brain teaser collection

balmy rampart
#

aight thx

balmy rampart
#

then

balmy rampart
#

thats why i was doinf

#

do u know any discord servers for comp programing

late ruin
#

(as well as codewars problems, which I just find more interesting, they have hard problems as well)

balmy rampart
balmy rampart
late ruin
balmy rampart
#

wait

#

thats craz

#

a fuctuon for all digits

#

aight thanks man

dusky owlBOT
#
Python help channel closed using Discord native close action

This help channel has been closed. Feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.