- Notifications
You must be signed in to change notification settings - Fork4
A brilliant repository of fantastic, killer one-liners
joric/oneliners
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Just FYI, this isn't just README.md, it's also more than a thousand solutions in the repository.There's alsostats.
Leetcode imports modules as wildcards, so you don't have to specify module names. There are some exceptions:
- Single
bisect()without a prefix triggersobject is not callable, usebisect.bisect()orbisect_left(). - You have to specify
re.subbecausesubwithout a prefix isoperator.sub. - Default
powis__builtins__['pow'](supports up to 3 arguments, including the modulus), notmath.pow.
For example, Leetcode header hasimport * from math, so we usecomb() instead ofmath.comb():
classSolution:defuniquePaths(self,m:int,n:int)->int:returncomb(m+n-2,n-1)
You can also use__import__('module').func for unlisted modules (namely,numpy,scipy, andsortedcontainers).
classSolution:defcheckStraightLine(self,p):return__import__('numpy').linalg.matrix_rank([[1]+xforxinp])<3
Sometimes you can save on casting of the return type, e.g. Leetcode autoconverted keys and mixed types to lists.
classSolution:deftopKFrequent(self,nums:List[int],k:int)->List[int]:returndict(Counter(nums).most_common(k))
It also automatically evaluated generators (stopped worked in Aug 2023,expected return type integer[]):
classSolution:defcountBits(self,n:int)->List[int]:returnmap(int.bit_count,range(n+1))
You can also return linked list of values asListNode('a,b,...'). This one is really specific, but sometimes useful.
classSolution:defaddTwoNumbers(self,a:Optional[ListNode],b:Optional[ListNode])->Optional[ListNode]:f=lambdan:nandn.val+10*f(n.next)or0;returnListNode(','.join([*str(f(a)+f(b))][::-1]))
Leetcode also hasserialize anddeserialize functions for lists and trees:
classSolution:defreverseList(self,h:Optional[ListNode])->Optional[ListNode]:returnhandh.deserialize(str(eval(h.serialize(h))[::-1]))
There is alsohas_sycle function:
classSolution:defhasCycle (self,h:Optional[ListNode])->bool:returnListNode.has_cycle(h)
There are also_*_node_to_array and_array_to_*_node functions:
classSolution:defisPalindrome(self,h:ListNode)->bool:return(s:=type(h)._list_node_to_array(h))==s[::-1]
classSolution:defsortList(self,h:Optional[ListNode])->Optional[ListNode]:t=ListNode;returnt._array_to_list_node(sorted(t._list_node_to_array(h)))classSolution:defsortList(self,h:Optional[ListNode])->Optional[ListNode]:t=ListNode;returnt.deserialize(str(sorted(eval(t.serialize(h)))))
You can also dump the entire preprocessed solution file to check all the imports for yourself (seegist):
withopen(__file__,'rt')asf:print(f.read())
The solution driver code writes all results to theuser.out file, so we can use it like this:
classSolution:deftwoSum(self,nums:List[int],target:int)->List[int]:fromzlibimportdecompressfrombase64importb64decodeopen('user.out','wb').write(decompress(b64decode('eJzdkMEVwCAIQ++dggFyEKi2zuLr/mtItZb63KAc\kpfwuVAYFK6tCIjNPH1KncodJMuBTqWTYUGe89hNX1Kd/K2Nh1iM3mYbkMlpIaFrvvcCaVwCH+YB3FSHVu5xXDc='))),exit(0)
There is no approved method to get all the test cases for problems in LeetCode.You can, however, leverage the fact that LeetCode reveals the test case that causes your code to fail.The solution above is not very reliable, because tests and environment may change, but it's pretty fast.
You can explore the sandbox using shell commands, e.g. (seegist):
importsubprocessprint(subprocess.run(["ls","-la","/"]))
You can also set your own execution time usingatexit:
__import__('atexit').register(lambda:open("display_runtime.txt","w").write("0"))# 0..2147483647
SeeLeetCode-Feedback/LeetCode-Feedback#25646 (we have decided not to allocate development resources to fixing it at this time.)
Some leetcode problems may be solved at the function declaration level.
classSolution:searchInsert=bisect_left
classSolution:permute=permutations
classSolution:sortArray=sorted
classSolution:bulbSwitch=isqrt
classSolution:search=contains
classSolution:myPow=pow
Note that it only works for the built-in functions, they can omitself parameter.It's a built-in CPython feature:
You cannot use your own function like that, without skipping the first argument.
classSolution:reverseWords=lambda_,s:' '.join(w[::-1]forwins.split())
It's not necessarily shorter, because lambdas can't use semicolons.
In some cases you don't even have to write "class Solution:", e.g:
Codec=TreeNode
Let's consider function declaration is zero lines.
classSolution:defaccountBalanceAfterPurchase(self,x:int)->int:return(104-x)//10*10
classSolution:defmajorityElement(self,n:List[int])->int:returnmode(n)
classSolution:defflowerGame(self,n:int,m:int)->int:returnm*n//2
classSolution:defnumberOfMatches(self,n:int)->int:return~-n
classSolution:defstoneGame(self,piles:List[int])->bool:return1
You can also write:
classSolution:stoneGame=truth
classSolution:defisStrictlyPalindromic(self,n:int)->bool:0
This is 1-symbol solution. Notice no return operator here, can bepass, as function returns None. You can also do:
classSolution:isStrictlyPalindromic=not_
Fictitious (anonymous) lambdas may be nested. E.g. you can use lambdas as parameters:
(lambda a,b,c: code)(a,b,c)becomes(lambda a,b,c: code)(lambda a: code, lamda b: code, lambda c: code)
You can't unpack lambda tuples in Python 3 sincePEP 3113, however, if your lambda is flat, there is an upgrade path:
lambda (x, y): x + yin Python 2 becomeslambda xy:(lambda x,y: x+y)(*xy)in Python 3.
You can also unpack multiple tuples aslambda xy,ab:(lambda x,y,a,b: x+y+a+b)(*(xy+ab)).
classSolution:defcountVowelPermutation(self,n:int)->int:returnsum(reduce(lambdax,_:(lambdaa,e,i,o,u:(e+i+u,a+i,e+o,i,i+o))(*x),[0]*(n-1),[1]*5))%(10**9+7)
Sometimes you can unpack tuples with starmap:
classSolution:deflenLongestFibSubseq(self,n:List[int])->int:s={*n};return(0,t:=max(starmap(f:=lambdaa,b,c=2:s&{a+b}andf(b,a+b,c+1)orc,combinations(n,2))))[t>2]
Generator expressions(x for y in z) are memory efficient since they only require memory forthe one value they yield. If you don't care about memory you can use square brackets to make it a list comprehension that automatically runs the loop.You can also exhaust a generator usingall(),any() orsum(), depending on the return values.You can also save a few chars using[*g] syntax instead oflist(g) where g is a generator function.Generator lengthlen(list(g)) can be calculated in constant memory assum(1 for _ in g).
Generator expansion[*g] may use a traling comma*g, in the initialization section (1 character shorter).
classSolution:defmaxAbsoluteSum(self,a:List[int])->int:a=[*accumulate([0]+a)];returnmax(a)-min(a)classSolution:defmaxAbsoluteSum(self,a:List[int])->int:a=*accumulate([0]+a),;returnmax(a)-min(a)
Generators provide an easy, built-in way to create instances of Iterators.Iterators are objects that have an__iter__ and a__next__ method.Theiter() method returns an iterator for the given argument.Each access iterator advances one step.May be useful, e.g. this solution would not work without converting a string to an iterator:
classSolution:defappendCharacters(self,s:str,t:str)->int:s=iter(s);returnsum(cnotinsforcint)
You can also useiter() to split a list into chunks. The[iter(s)]*n trick breaks a list into pieces of size n:
classSolution:defminChanges(self,s:str)->int:returnsum(map(ne,s[::2],s[1::2]))classSolution:defminChanges(self,s:str)->int:returnsum(map(ne,s:=iter(s),s))classSolution:defminChanges(self,s:str)->int:returnsum(map(ne,*[iter(s)]*2))
Starting from Python 3.7 dictionary order is guaranteed to be insertion order.
- Implementation proposal:https://mail.python.org/pipermail/python-dev/2012-December/123028.html
A simple Hash Table consists of key-value pair arranged in pseudo random order based on the calculations from Hash Function.The traditional implementation of python dict used a sparse array which had lots of unused spaces in between.The new implementation uses a combination of dense array and sparse array,the dense array stores the key-value pair while the sparse array stores the indices to this dense array.
- Faster iteration (up to 2x faster,https://mail.python.org/pipermail/python-dev/2017-December/151283.html)
- Order is maintained on iterating and converting a dictionary to other data type.
- Less memory required for both usage and creation of dictionaries.
Counters (collections.Counter()) can be updated, similar todict.update(), it's much faster than a sum of counters.E.g.c[i]+=1 is equivalent toc.update([i]),c[i]-=1 isc.update({i:-1}).To delete a key you can use the.pop method (same asdel), it's shorter thanpopitem().
Note thatc.update({i:x}) andsetitem(c,i,c[i]+x) behaves differently. If x is negative and count becomes<=0, the key is removed.
You can also remove zero and negative values manually (there is an the official way, seedocumentation):
c=Counter({1:1,2:0,3:-1});print(c:=+c)#{1: 1}, same as c += Counter()
Since Python 3.7, as a dict subclass, Counter inherited the capability to remember insertion order.
classSolution:defreductionOperations(self,n:List[int])->int:returnsum(i*vfori,(_,v)inenumerate(sorted(Counter(n).items())))classSolution:defreductionOperations(self,n:List[int])->int:returnsum(i*vfori,vinenumerate(Counter(sorted(n)).values()))
Since Python 3.10 you can usetotal() to compute sum of the counts.
classSolution:defminSteps(self,s:str,t:str)->int:returnsum((Counter(s)-Counter(t)).values())classSolution:defminSteps(self,s:str,t:str)->int:return(Counter(s)-Counter(t)).total()
Sometimes you can replaceCounter withset andcount (and it's even faster):
classSolution:defcanConstruct(self,s:str,k:int)->bool:returnsum(x&1forxinCounter(s).values())<=k<=len(s)classSolution:defcanConstruct(self,s:str,k:int)->bool:returnsum(1&s.count(x)forxinset(s))<=k<=len(s)
classSolution:defminimumLength(self,s:str)->int:returnsum(2-x%2forxinCounter(s).values())classSolution:defminimumLength(self,s:str)->int:returnsum(2-s.count(x)%2forxinset(s))
Unlikedict, pythonset does NOT maintain insertion order. There are modules that implements ordered set.
- sortedcontainers -
SortedList,SortedDict,SortedSet(maintains sorted order). - sortedcollections -
ValueSortedDict,ItemSortedDict,OrderedDict,OrderedSet(maintains insertion order).
You can useSortedList in a bunch of problems instead of a heap.
classSolution:defminimumDeviation(self,nums:List[int])->int:r,q=inf,[]forainnums:heappush(q,a%2and-a*2or-a)m=-max(q)whilelen(q)==len(nums):a=-heappop(q)r=min(r,a-m)ifa%2==0:m=min(m,a//2)heappush(q,-a//2)returnrfromsortedcontainersimportSortedListclassSolution:defminimumDeviation(self,nums:List[int])->int:s,r=SortedList(i*2ifi&1elseiforiinnums),infwhileTrue:r=min(r,s[-1]-s[0])if1&s[-1]:breaks.add(s.pop()//2)returnrclassSolution:defminimumDeviation(self,a:List[int])->int:s,r=__import__('sortedcontainers').SortedList(i*(1+i%2)foriina),inf;returnnext(rfor_incount()if[r:=min(r,s[-1]-s[0])]and1&s[-1]ors.add(s.pop()//2))
The controversial walrus operator (:=) added in Python 3.8 (PEP-572,whenGuido van Rossum resigned),can be used to define or update a variable or a function (mostly used for recursive functions).
You can define and call a recursive function in a single line with Y-combinator, e.g.:
return (lambday,x:y(y,x))(lambdaf,x:1ifx==0elsex*f(f,x-1),5)
But the walrus operator syntax is much more concise:
return (f:=lambdax:1ifx==0elsex*f(x-1))(5)
Many oneliners would be impossible to do without it (or rather, very hard, with nested lambdas).Sometimes you don't even need extra brackets, e.g. inmap(f:=x,y) ornext(g,f:=x) so it may be shorter than operators separated by semicolons.
classSolution:defnumOfMinutes(self,n:int,h:int,m:List[int],t:List[int])->int:returnmax(map(f:=cache(lambdai:~iandt[i]+f(m[i])),m))
classSolution(object):defguessNumber(self,n:int)->int:l,r=1,nwhilel<=r:m= (l+r)//2res=guess(m)ifres==0:returnmelifres>0:l=m+1else:r=m-1return0classSolution:defguessNumber(self,n:int)->int:return (f:=lambdal,h:hifl+1==helsef(m,h)ifguess(m:=(l+h)//2)>0elsef(l,m))(0,n)
classSolution:defreverse(self,x:int)->int:r,x=0,abs(x)whilex:r=r*10+x%10x//=10return ((x>0)-(x<0))*min(2**31,r)classSolution:defreverse(self,x:int)->int:return ((x>0)-(x<0))*min(2**31,(f:=lambdar,x:f(r*10+x%10,x//10)ifxelser)(0,abs(x)))
classSolution:deftopKFrequent(self,words:List[str],k:int)->List[str]:returnnsmallest(k,(f:=Counter(words)).keys(),lambdax:(-f[x],x))
You can use__setattr__ for dictionaries or__setitem__ for lists (both member functions returnNone).You can also usesetattr orsetitem functions from theoperator module,e.g.c[x]=1 is the same assetitem(c,x,1).
classSolution:defaddOneRow(self,root:TreeNode,v:int,d:int,isLeft:bool=True)->TreeNode:ifd==1:returnTreeNode(v,rootifisLeftelseNone,rootifnotisLeftelseNone)ifnotroot:returnNoneroot.left=self.addOneRow(root.left,v,d-1,True)root.right=self.addOneRow(root.right,v,d-1,False)returnrootclassSolution:defaddOneRow(self,root:TreeNode,v:int,d:int,isLeft:bool=True)->TreeNode:returnTreeNode(v,rootifisLeftelseNone,rootifnotisLeftelseNone)ifd==1else \setattr(root,'left',self.addOneRow(root.left,v,d-1,True))or \setattr(root,'right',self.addOneRow(root.right,v,d-1,False))orrootifrootelseNone
classSolution(object):defdeleteMiddle(self,head):deff(a,b):ifnotb:returna.nexta.next=f(a.next,b.next.next)ifb.nextelsef(a.next,b.next)returnareturnf(head,head.next)classSolution(object):defdeleteMiddle(self,head):return (f:=lambdaa,b:setattr(a,'next',f(a.next,b.next.next)ifb.nextelsef(a.next,b.next))oraifbelsea.next)(head,head.next)
Note thatsetitem also supports slices:
# TLE, too slowclassSolution:defcountPrimes(self,n):g=range(2,n);returnlen(reduce(lambdar,x:r-set(range(x**2,n,x))ifxinrelser,g,set(g)))classSolution:defcountPrimes(self,n):a= [0,0]+[1]*(n-2)foriinrange(2,int(n**0.5)+1):ifa[i]:a[i*i:n:i]= [0]*len(a[i*i:n:i])returnsum(a)classSolution:defcountPrimes(self,n):returnsum(reduce(lambdaa,i:a[i]andsetitem(a,slice(i*i,n,i),[0]*len(a[i*i:n:i]))ora,range(2,int(n**0.5)+1), [0,0]+[1]*(n-2)))
You can also calculate primes like this:
classSolution:defprimeSubOperation(self,a:List[int])->bool:m,p=1,[0]+[iforiinrange(2,999)ifall(i%jforjinrange(2,i))];\returnall(m<(m:=x-p[bisect_right(p,x-m)-1]+1)forxina)
Note slices can extend the list implicitly, e.g.:
a= [0,1,2]a[3:4]= [3]# the result is [0,1,2,3]
Be careful though, slicing doesn't extend list beyond the slice size:
a= [0,1]a[3:4]= [3,4]# the result is [0,1,3,4], NOT [0,1,?,3,4] (!)
Examples:
classSolution:deflongestObstacleCourseAtEachPosition(self,o:List[int])->List[int]:d= []foreino:i=bisect_right(d,e)ifi==len(d):d.append(0)d[i]=eyieldi+1classSolution:deflongestObstacleCourseAtEachPosition(self,o:List[int])->List[int]:d= []foreino:i=bisect_right(d,e)d[i:i+1]= [e]yieldi+1classSolution:deflongestObstacleCourseAtEachPosition(self,o:List[int])->List[int]:d=[];return[setitem(d,slice(i:=bisect_right(d,e),i+1),[e])ori+1foreino]
Sometimes (very often)exec is shorter thansetitem.
ParkingSystem=type('',(),{'__init__':lambdas,a,b,c:setattr(s,'p',[0,a,b,c]),'addCar':lambdas,t:\setitem(s.p,t,s.p[t]-1)ors.p[t]>=0})ParkingSystem=type('',(),{'__init__':lambdas,a,b,c:setattr(s,'p',[0,a,b,c]),'addCar':lambdas,t:\exec('s.p[t]-=1')ors.p[t]>=0})
classSolution:defmaximumEnergy(self,e:List[int],k:int)->int: [setitem(e,i,e[i]+e[i+k])foriinrange(len(e)-k)[::-1]];returnmax(e)classSolution:defmaximumEnergy(self,e:List[int],k:int)->int:exec('for i in range(len(e)-k):e[~i-k]+=e[~i]');returnmax(e)
You can write a class or a subclass implementation in one line.
MyHashSet=type('',(set,),{'remove':set.discard,'contains':set.__contains__})
MyStack=type('',(list,),{'push':list.append,'top':lambdas:s[-1],'empty':lambdas:nots})
ProductOfNumbers=type('',(list,),{'__init__':lambdas:list.__init__(s,[1]),'add':lambdas,x:s.append(s[-1]*x)ifxelses.__init__(),'getProduct':lambdas,k:s[k:]ands[-1]//s[~k]or0})
Counter subclassing fails since Python 3.7,type() doesn't support MRO entry resolution; use types.new_class().
When you try to usetypes.new_class() it saysTypeError: .__init_subclass__() takes no keyword arguments').
This can be avoided by creating the class first, then adding the methods to it separately, e.g.:
с=Counter;с.insert=lambdas,x:s.update({x})ors[x]<2;с.remove=lambdas,x:s.pop(x,0);с.getRandom=lambdas:choice([*s]);RandomizedSet=с
Sometimes (not always) you can skip__init__ and use static attributes.
UndergroundSystem=type('',(),{'h':{},'m':{},'checkIn':lambdas,i,v,t:setitem(s.m,i,(v,t)),'checkOut':lambdas,i,d,w:(v:=s.m[i][0])andsetitem(s.h,(v,d),[*map(sum,zip(s.h.pop((v,d), (0,0)),(w-s.m[i][1],1)))]),'getAverageTime':lambdas,v,d:truediv(*s.h[v,d])})
Binary search can be replaced by the built-inbisect methods.Custom binary search can use either an item getter object or a key function (since Python 3.10).Stock bisect implementation is inbisect.py (you have to know it well).
classSolution:defguessNumber(self,n:int)->int:l,r=1,nwhilel<=r:m= (l+r)//2res=guess(m)ifres==0:returnmelifres>0:l=m+1else:r=m-1return0classSolution:defguessNumber(self,n:int)->int:returnbisect_left(type('',(),{'__getitem__':lambda_,i:-guess(i)})(),0,1,n)classSolution:defguessNumber(self,n:int)->int:returnbisect_left(range(n),0,key=lambdanum:-guess(num))
Note that built-in methods don't support negative left margin, so you have to subtract it from the result:
classSolution:defkthSmallestProduct(self,a:List[int],b:List[int],k:int)->int:f=lambdax:sum(bisect_right(b,x//y)ify>0elselen(b)-bisect_left(b,ceil(x/y))ify<0else (x>=0)*len(b)foryina)l,r=-10**10-1,10**10+1whilel<r:m= (l+r)//2iff(m)>=k:r=melse:l=m+1returnlclassSolution:defkthSmallestProduct(self,a:List[int],b:List[int],k:int)->int:f=lambdax:sum(bisect_right(b,x//y)ify>0elselen(b)-bisect_left(b,ceil(x/y))ify<0else (x>=0)*len(b)foryina)returnbisect_left(range(2*(r:=10**10)),k,key=lambdai:f(i-r))-r
Range in Python 3 supports random access, so you can save a few chars using a long hardcoded range.
classSolution:defrepairCars(self,r:List[int],c:int)->int:returnbisect_left(range(c*c*min(r)),c,key=lambdam:sum(isqrt(m//x)forxinr))classSolution:defrepairCars(self,r:List[int],c:int)->int:returnbisect_left(range(1<<47),c,key=lambdam:sum(isqrt(m//x)forxinr))
While loops are not very oneliner-friendly. You can usenext() function with an endlesscount() generator.Note that the default parameter runs first so you can use it for the startup code (it's not recalculated in the end).
classSolution:deftwoSum(self,nums:List[int],target:int)->List[int]:seen= {}fori,xinenumerate(nums):iftarget-xinseen:returnseen[target-x],iseen[x]=ireturnFalseclassSolution:deftwoSum(self,n:List[int],t:int)->List[int]:returnnext(((m[t-x],i)fori,xinenumerate(n)ift-xinmorsetitem(m,x,i)),m:={})
classSolution:defbreakPalindrome(self,s:str)->str:foriinrange(len(s)//2):ifs[i]!='a':returns[:i]+'a'+s[i+1:]returns[:-1]+'b'ifs[:-1]else''classSolution:defbreakPalindrome(self,s:str)->str:returnnext((s[:i]+'a'+s[i+1:]foriinrange(len(s)//2)ifs[i]!='a'),s[:-1]ands[:-1]+'b')
classSolution:defisPossible(self,target:List[int])->bool:s=sum(target)q= [-aforaintarget]heapify(q)whileTrue:x=-heappop(q)ifx==1:returnTrueifs==x:returnFalsed=1+ (x-1)% (s-x)ifx==d:returnFalses=s-x+dheappush(q,-d)classSolution:defisPossible(self,target:List[int])->bool:return (s:=sum(target),q:=[-aforaintarget],heapify(q))andnext((x==1for_incount()if (x:=-heappop(q))==1ors==xor (d:=1+(x-1)%(s-x))==xornot (s:=s-x+d,heappush(q,-d))),1)
You can also usetakewhile(), it's also a generator, so you need to expand it (e.g. withrepeat(0)).
classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:r,d= [],deque()fori,ninenumerate(nums):whiledandn>=nums[d[-1]]:d.pop()d.append(i)ifd[0]==i-k:d.popleft()r.append(nums[d[0]])returnr[k-1:]classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:return (d:=deque())orreduce(lambdar,p:(any(takewhile(lambda_:dandp[1]>=nums[d[-1]]andd.pop(),repeat(0))),d.append(p[0]),d[0]==p[0]-kandd.popleft(),r.append(nums[d[0]]))andr,enumerate(nums), [])[k-1:]
You could also tryany() orall() as a while loop instead ofnext(), it may be shorter.You can assure that expression never returnsNone, using[] ([None] evaluates toTrue).
classSolution:deflastStoneWeight(self,stones:List[int])->int:stones.sort()whilelen(stones)>1:insort(stones,stones.pop()-stones.pop())returnstones[0]classSolution:deflastStoneWeight(self,s:List[int])->int:returnnext((s[0]for_incount()ifnots[1:]orinsort(s,s.pop()-s.pop())),s.sort())classSolution:deflastStoneWeight(self,s:List[int])->int:return (s.sort(),all(s[1:]and [insort(s,s.pop()-s.pop())]for_incount()),s[0])[2]
You can also evalulate multiline code withexec. Unlikeeval, is not limited to a single string.
classSolution:defminimumOneBitOperations(self,n:int)->int:returnnext((rfor_incount()ifnot(nand(r:=r^n,n:=n//2))),r:=0)classSolution:defminimumOneBitOperations(self,n:int)->int:r=[0];exec('while n:\n r[0]^=n\n n//=2');returnr[0]classSolution:defminimumOneBitOperations(self,n:int)->int:return(f:=lambdan:nandn^f(n//2))(n)
To swap values you can use eitherexec (inline version ofa,b=b,a) or a temporary variable (t:=a,a:=b,b:=t).
Note thateval accepts only a single expression, and returns the value of the given expression,whereasexec ignores the return value from its code, and always returnsNone, its use has no effecton the compiled bytecode of the function where it is used. It does however affect existing variables.
Example:
classSolution:defsortColors(self,nums:List[int])->None:deffn(t,b):red,white,blue=treturn (swap:=lambdaa,x,y:exec('a[x],a[y]=a[y],a[x]'),(swap(nums,red,white), (red+1,white+1,blue))[1]ifnums[white]==0else ((red,white+1,blue)ifnums[white]==1else (swap(nums,white,blue),(red,white,blue-1))[1]))[1]reduce(fn,nums, [0,0,len(nums)-1])classSolution:defsortColors(self,nums:List[int])->None: (s:=lambdaa,x,y:(t:=a[x],setitem(a,x,a[y]),setitem(a,y,t),a)[3],f:=lambdaa,i,j,k:(f(s(a,i,j),i+1,j+1,k)ifa[j]==0elsef(a,i,j+1,k)ifa[j]==1elsef(s(a,j,k),i,j,k-1))ifi<=j<=kelseNone)[1](nums,0,0,len(nums)-1)
Also you can try a swap function here (but it's pretty long, I don't use it):
swap=lambdaa,x,y:(lambdaf=a.__setitem__:(f(x,(a[x],a[y])),f(y,a[x][0]),f(x,a[x][1])))()
You can usemap for a lot of things, for example to traverse through adjacent cells.
classSolution:defmaxAreaOfIsland(self,grid:List[List[int]])->int:defdfs(i,j):if0<=i<len(grid)and0<=j<len(grid[0])andgrid[i][j]:grid[i][j]=0return1+sum(map(dfs,(i+1,i,i-1,i),(j,j+1,j,j-1)))return0returnmax(dfs(i,j)foriinrange(len(grid))forjinrange(len(grid[0])))classSolution:defmaxAreaOfIsland(self,g:List[List[int]])->int:returnmax((f:=lambdai,j:setitem(g[i],j,0)or1+sum(map(f,(i+1,i,i-1,i),(j,j+1,j,j-1)))if0<=i<len(g)and0<=j<len(g[0])andg[i][j]else0)(i,j)foriinrange(len(g))forjinrange(len(g[0])))
Though it's shorter to use complex numbers for 2d maps (introduced by Stephan Pochmann):
classSolution:defmaxAreaOfIsland(self,grid):grid= {i+j*1j:valfori,rowinenumerate(grid)forj,valinenumerate(row)}defarea(z):returngrid.pop(z,0)and1+sum(area(z+1j**k)forkinrange(4))returnmax(map(area,set(grid)))classSolution:defmaxAreaOfIsland(self,grid):returnmax(map(a:=lambdaz:g.pop(z,0)and1+sum(a(z+1j**k)forkinrange(4)),set(g:= {i+j*1j:valfori,rowinenumerate(grid)forj,valinenumerate(row)})))
Complex numbers in general are very useful as 2d coordinates:
classSolution:defisPathCrossing(self,p:str)->bool:z=0;returnlen(p)>=len({0,*{z:=z+1j**'NESW'.find(c)forcinp}})
You can convert lists or tuples toTrue with!=0 instead ofbool() (3 chars shorter), or>[] (cuts extra space).
classSolution:defnumIslands(self,grid:List[List[str]])->int:grid= {i+j*1j:int(val)fori,rowinenumerate(grid)forj,valinenumerate(row)}deff(z):returngrid.pop(z,0)andbool([f(z+1j**k)forkinrange(4)])returnsum(map(f,set(grid)))classSolution:defnumIslands(self,grid:List[List[str]])->int:returnsum(map(f:=lambdaz:g.pop(z,0)and [f(z+1j**k)forkinrange(4)]!=0,set(g:={i+j*1j:int(x)fori,rowinenumerate(grid)forj,xinenumerate(row)})))
classSolution:defclosedIsland(self,grid:List[List[str]])->int:g= {i+j*1j:1-xfori,rinenumerate(grid)forj,xinenumerate(r)}f=lambdaz:g.pop(z,0)and [f(z+1j**k)forkinrange(4)]!=0sum(f(z)forzinset(g)ifnot(0<z.real<len(grid)-1and0<z.imag<len(grid[0])-1))returnsum(map(f,set(g)))classSolution:defclosedIsland(self,grid:List[List[str]])->int:return (g:={i+j*1j:1-xfori,rinenumerate(grid)forj,xinenumerate(r)},f:=lambdaz:g.pop(z,0)and [f(z+1j**k)forkinrange(4)]!=0,[f(z)forzinset(g)ifnot(0<z.real<len(grid)-1and0<z.imag<len(grid[0])-1)])andsum(map(f,set(g)))
classSolution:defuniquePathsIII(self,grid:List[List[int]])->int:deff(z,r):ifx:=g.pop(z,0):ifx==3andnotg:r=r+1forkinrange(4):r=f(z+1j**k,r)g.update({z:x})returnrg= {i+j*1j:x+1fori,rowinenumerate(grid)forj,xinenumerate(row)ifx!=-1}returnf(next(zforz,xing.items()ifx==2),0)classSolution:defuniquePathsIII(self,grid:List[List[int]])->int:return (g:={i+j*1j:x+1fori,rowinenumerate(grid)forj,xinenumerate(row)ifx!=-1})and (f:=lambdaz,r:[(x:=g.pop(z,0))and (x==3andnotgand (r:=r+1), [r:=f(z+1j**k,r)forkinrange(4)],g.update({z:x}))]andr) (next(zforz,xing.items()ifx==2),0)
Unicode find (NOT Union Find) is the greatest trick of all time to solve graph problems.The idea is to use string replace in a Unicode space. Introduced by Stephan Pochmann.
classSolution:deffindRedundantConnection(self,edges:List[List[int]])->List[int]:t=''.join(map(chr,range(1001)))foru,vinedges:ift[u]==t[v]:return [u,v]t=t.replace(t[u],t[v])classSolution:deffindRedundantConnection(self,e:List[List[int]])->List[int]:t=''.join(map(chr,range(1001)));returnnext([u,v]foru,vineift[u]==(t:=t.replace(t[u],t[v]))[u])
Another example:
classSolution:defswimInWater(self,g:List[List[int]])->int:n=len(g)t,r=''.join(map(chr,range(n*n))),range(n)forw,i,jinsorted((g[i][j],i,j)fori,jinproduct(r,r)):forx,yin ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):ifn>y>=0<=x<nandg[x][y]<=w:t=t.replace(t[i*n+j],t[x*n+y])ift[0]==t[-1]:returnwreturn0classSolution:defswimInWater(self,g:List[List[int]])->int:n=len(g);t,r=''.join(map(chr,range(n*n))),range(n);returnnext((wforw,i,jinsorted((g[i][j],i,j)fori,jinproduct(r,r))if[t:=t.replace(t[i*n+j],t[x*n+y])forx,yin((i+1,j),(i-1,j),(i,j+1),(i,j-1))ifn>y>=0<=x<nandg[x][y]<=w]andt[0]==t[-1]),0)
Another example (Q4 athttps://leetcode.com/contest/weekly-contest-392):
classSolution:defminimumCost(self,n:int,edges:List[List[int]],query:List[List[int]])->List[int]:t,c=''.join(map(chr,range(n))),{}foru,v,winedges:t=t.replace(t[u],t[v])foru,v,winedges:c[t[u]]=c.get(t[u],w)&wreturn [0ifu==velsec[t[u]]ift[u]==t[v]else-1foru,vinquery]classSolution:defminimumCost(self,n:int,e:List[List[int]],q:List[List[int]])->List[int]:t,c=''.join(map(chr,range(n))),{};all(t:=t.replace(t[u],t[v])foru,v,_ine); [setitem(c,t[u],c.get(t[u],w)&w)foru,v,wine];return[u!=vandt[u]!=t[v]and-1orc[t[u]]foru,vinq]
Cache decorator,@lru_cache or@cache (since Python 3.9) may be used as an inline functioncache(lambda ...).Essentially, a built-in memoization. Brings computation complexity from exponential to quadratic or linear, depending of the problem.Decorator source code is infunctools.py.You can also implementC++ version of a cache decorator.
classSolution:defmaxProfit(self,k:int,prices:List[int])->int:@cachedefdfs(i,k,sell):return0ifk==0ori==len(prices) \elsemax(dfs(i+1,k-1,0)+prices[i],dfs(i+1,k,1))ifsell \elsemax(dfs(i+1,k,1)-prices[i],dfs(i+1,k,sell))returndfs(0,k,0)classSolution:defmaxProfit(self,k:int,prices:List[int])->int:return (f:=cache(lambdai,k,s:0ifk==0ori==len(prices)elsemax(f(i+1,k-s,1-s)+prices[i]*(2*s-1),f(i+1,k,s))))(0,k,0)
classSolution:defcoinChange(self,coins:List[int],amount:int)->int:@cachedeff(n):returnmin([1+f(n-c)forcincoins])ifn>0else0ifn==0elseinfx=f(amount)returnxifx!=infelse-1classSolution:defcoinChange(self,coins:List[int],amount:int)->int:return (lambdax:xifx!=infelse-1)((f:=cache(lambdan:min([1+f(n-c)forcincoins])ifn>0else0ifn==0elseinf))(amount))
It is sometimes necessary to reset cache withcache_clear between tests to avoid Memory Limit Exceeded error.
classSolution:deflengthOfLongestSubsequence(self,a:List[int],t:int)->int:return(a.sort(),r:=(f:=cache(lambdai,b:band-infifb<0ori<0elsemax(1+f(i-1,b-a[i]),f(i-1,b))))(len(a)-1,t),f.cache_clear())and(-1,r)[r>0]
You can also specify maxsize option asf=lru_cache(maxsize)(lambda ...) in case of memory issues:
classSolution:defshortestCommonSupersequence(self,a:str,b:str)->str:return(f:=lru_cache(9**5)(lambdai,j:a[i:]andb[j:]and(a[i]==b[j]anda[i]+f(i+1,j+1)ormin(a[i]+f(i+1,j),b[j]+f(i,j+1),key=len))ora[i:]orb[j:]))(0,0)
Use it to flatten a loop.
classSolution:deflengthOfLongestSubstring(self,s):start,res,h=0,0, {}fori,cinenumerate(s):start=max(start,h.get(c,0))res=max(res,i-start+1)h[c]=i+1returnresclassSolution:deflengthOfLongestSubstring(self,s):deffn(a,b):start,res,h=ai,c=bstart=max(start,h.get(c,0))res=max(res,i-start+1)h[c]=i+1returnstart,res,hreturnreduce(fn,enumerate(s),[0,0,{}])[1]classSolution:deflengthOfLongestSubstring(self,s):returnreduce(lambdaa,b:(s:=max(a[0],a[2].get(b[1],0)),max(a[1],b[0]-s+1), {**a[2],b[1]:b[0]+1}),enumerate(s),(0,0,{}))[1]classSolution:deflengthOfLongestSubstring(self,s):returnreduce(lambdaa,b:(lambdat,r,h,i,c:(s:=max(t,h.get(c,0)),max(r,i-s+1), {**h,c:i+1}))(*a,*b),enumerate(s),(0,0,{}))[1]
Another example:
classSolution:deflongestValidParentheses(self,s:str)->int:deffn(a,b):r,s=ai,p=breturn (max(r,i-s[-2][0]),s[:-1])ifp==')'ands[-1][1]=='('else (r,s+[(i,p)])returnreduce(fn,enumerate(s), (0,[(-1,')')]))[0]classSolution:deflongestValidParentheses(self,s:str)->int:returnreduce(lambdaa,b:(max(a[0],b[0]-a[1][-2][0]),a[1][:-1])ifb[1]==')'anda[1][-1][1]=='('else (a[0],a[1]+[b]),enumerate(s),(0,[(-1,')')]))[0]
The product function from itertools is sometimes handy.
classSolution:defnthUglyNumber(self,n:int)->int:returnsorted(2**a*3**b*5**cforainrange(32)forbinrange(20)forcinrange(14))[n-1]classSolution:defnthUglyNumber(self,n:int)->int:returnsorted(2**a*3**b*5**cfora,b,cinproduct(*map(range,(32,20,14))))[n-1]classSolution:defnthUglyNumber(self,n:int)->int:returnsorted(2**a*3**b*5**cfora,b,cinproduct(*[range(32)]*3))[n-1]
Can be used anywhere in place of nested loops. Example:
classSolution:defcountPrefixSuffixPairs(self,w:List[str])->int:r=range(len(w))returnsum(i<jandw[j].startswith(w[i])andw[j].endswith(w[i])foriinrforjinr)classSolution:defcountPrefixSuffixPairs(self,w:List[str])->int:returnsum(b.startswith(a)andb.endswith(a)fora,bincombinations(w,2))classSolution:defcountPrefixSuffixPairs(self,w:List[str])->int:returnsum(a==b[:len(a)]==b[-len(a):]fora,bincombinations(w,2))
In case if you need an assignment between the loops, you still can rewrite nested loops into a single aggregation:
classSolution:deflongestBalanced(self,a:list[int])->int:returnmax(max((o,e)[x&1].add(x)or-~j*(len(o)==len(e))forj,xinenumerate(a[i:]))foriinrange(len(a))if(o:={*()},e:={*()}))classSolution:deflongestBalanced(self,a:list[int])->int:returnmax((o,e)[x&1].add(x)or-~j*(len(o)==len(e))foriinrange(len(a))if(o:={*()},e:={*()})forj,xinenumerate(a[i:]))
classSolution:deflongestBalanced(self,s:str)->int:returnmax(max(j+1forj,xinenumerate(s[i:])ifc.update([x])orlen({*c.values()})<2)foriinrange(len(s))if[c:=Counter()])classSolution:deflongestBalanced(self,s:str)->int:returnmax(j+1foriinrange(len(s))if[c:=Counter()]forj,xinenumerate(s[i:])ifc.update([x])orlen({*c.values()})<2)
Nobody will stop you from using semicolons, but you'd still have to convert while and for loops.
Example:
classSolution:defswapNodes(self,h:Optional[ListNode],k:int)->Optional[ListNode]:q=hi=1d= {}whileq:d[i]=qq=q.nexti+=1d[k].val,d[i-k].val=d[i-k].val,d[k].valreturnhclassSolution:defswapNodes(self,h:Optional[ListNode],k:int)->Optional[ListNode]:q=h;i=1;d={};all(qand(setitem(d,i,q),q:=q.next,i:=i+1)for_incount());d[k].val,d[i-k].val=d[i-k].val,d[k].val;returnhclassSolution:defswapNodes(self,h:Optional[ListNode],k:int)->Optional[ListNode]:l=[h]+[h:=h.nextfor_in[1]*10**5ifh];a,b=l[k-1],l[~k];a.val,b.val=b.val,a.val;returnl[0]
Many leetcode problems use Fibonacci sequence that can be calculated using a variety of different methods.
classSolution:deffib(self,n:int)->int:a,b=0,1for_inrange(n):a,b=b,a+breturna# classic Binet, https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.htmlclassSolution:deffib(self,n:int)->int:phi= (1+sqrt(5))/2returnround(pow(phi,n)/sqrt(5))classSolution:deffib(self,n:int)->int:n-=1;r=5**.5;returnround(((1+r)/2)**-~n/r)classSolution:deffib(self,n:int)->int:r=5**.5;returnround(((1+r)/2)**n/r)# generating function, https://en.wikipedia.org/wiki/Generating_functionclassSolution:deffib(self,n:int)->int:x=1<<32;returnx**~-n*x*x//(x*x+~x)%xclassSolution:deffib(self,n:int)->int:x=9**n;returnx**-~n//(x*x+~x)%xclassSolution:deffib(self,n:int)->int:returnpow(x:=2<<n,n+1,x*x+~x)%x
classSolution:defclimbStairs(self,n:int)->int:a=b=1for_inrange(n):a,b=b,a+breturnaclassSolution:defclimbStairs(self,n):returnpow(x:=2<<n,n+2,x*x+~x)%x
classSolution:deftribonacci(self,n):a,b,c=1,0,0for_inrange(n):a,b,c=b,c,a+b+creturnc# https://mathworld.wolfram.com/TribonacciNumber.htmlclassSolution:deftribonacci(self,n:int)->int:returnround((599510/325947)**n*39065/116186)classSolution:deftribonacci(self,n:int)->int:returnpow(x:=2<<n,n+2,~-x*x*x+~x)%x
Many problems can be solved with a single regex:
classSolution:defsortVowels(self,s:str)->str:returnre.sub(t:='(?i)[aeiou]',lambdam,v=sorted(findall(t,s)):heappop(v),s)
classSolution:defisValid(self,w:str)->bool:returnmatch('^(?=.*[aeiou])(?=.*[^0-9aeiou])[a-z0-9]{3,}$',w,I)
classSolution:defmakeGood(self,s:str)->str: [s:=re.sub(r'(.)(?!\1)(?i:\1)','',s)for_ins];returns
classSolution:defclearDigits(self,s:str)->str: [s:=re.sub('\D\d','',s)for_ins];returns
classSolution:defisCircularSentence(self,s:str)->bool:returnnotre.search('(.) (?!\\1)',s+' '+s)
There are many uses foritertools.accumulate, remember that it supports any function besides the default "sum".
classSolution():defstalinSort(self,a:List[int])->List[int]:return [xfori,xinenumerate(a)ifx>=max(a[:i+1])]classSolution():defstalinSort(self,a:List[int])->List[int]:returncompress(a,map(ge,a,accumulate(a,max)))
For the Kadane-like problems you have to maintain a couple of counters. You can just usemax on a comprehension.
classSolution:defmaxSubArray(self,nums:List[int])->int:cur_max,max_till_now=0,-infforcinnums:cur_max=max(c,cur_max+c)max_till_now=max(max_till_now,cur_max)returnmax_till_nowclassSolution:defmaxSubArray(self,n:List[int])->int:returnmax(accumulate(n,lambdac,x:max(c+x,x)))classSolution:defmaxSubArray(self,n:List[int])->int:c=0;returnmax(c:=max(c+x,x)forxinn)
If there are more counters, you can combine intermediary counter and target counter calculation using a walrus operator.
classSolution:defmaxAscendingSum(self,n:List[int])->int:p=c=0;returnmax((c:=x+c*(x>p),p:=x)[0]forxinn)classSolution:defmaxAscendingSum(self,n:List[int])->int:p=c=0;returnmax(c:=x+c*(x>p)+0*(p:=x)forxinn)classSolution:defmaxAscendingSum(self,n:List[int])->int:p=c=0;returnmax(c:=x+c*(p<(p:=x))forxinn)
You can save a few characters using asterisk operator*.One* means "expand this as a list", two** means "expand this as a dictionary".Note with** you can only expand dictionaries, e.g.{'a':1, **dict}.
classSolution:defcheckStraightLine(self,p): (a,b),(c,d)=p[:2];returnall((x-a)*(d-b)==(c-a)*(y-b)forx,yinp)classSolution:defcheckStraightLine(self,p): (a,b),(c,d),*_=p;returnall((x-a)*(d-b)==(c-a)*(y-b)forx,yinp)
There's a nice way to convert an iterable to list, e.g.x=[*g] equals*x,=g (1 char shorter). Or expand lists:
classSolution:deffindMaxAverage(self,n:List[int],k:int)->float:s=[0]+[*accumulate(n)];returnmax(map(sub,s[k:],s))/kclassSolution:deffindMaxAverage(self,n:List[int],k:int)->float:s=[0,*accumulate(n)];returnmax(map(sub,s[k:],s))/k
You can also use this syntax to unpack iterables, e.g.a,*b,c=range(5) meansa=1;b=[2,3,4];c=5.
classSolution:defwaysToSplitArray(self,a:list[int])->int:returnsum(map((sum(a)/2).__le__,accumulate(a[:-1])))classSolution:defwaysToSplitArray(self,a:list[int])->int:*p,s=accumulate(a);returnsum(map((s/2).__le__,p))
Rotate array problem was published in Programming Pearls (pages 624-625 of a September 1983 edition).
The problem continues to look hard until you finally comeup with the right aha! insight. Let's view it as transformingthe array AB into the array BA, but let's also assume we havea subroutine that reverses the elements in a specified portionof the array.
Rotating string "ABCDEFGH" by i=3 characters left (n is string length, indexes start from 1):
reverse(1,i)/* CBADEFGH */reverse(i+1,n)/* CBAHGFED */reverse(1,n)/* DEFGHABC */
This implementation of rotating a ten-element array up byfive positions (Figure 1) is from Doug Mcllroy; try it.The reversal code is time- and space-efficient, and is soshort and simple that it's pretty hard to get wrong.
It is exactly the code that Kernighan and Plauger use in the texteditor in their book. Brian Kernighan reports that this codeindeed ran correctly the first time it was executed, whiletheir previous code for a similar task contained several bugs.This code is also used in several text editors, including theUNIX editor ed.
# rotate array AKA Doug Mcllroy, Programming Pearls# reverse parts at split point then reverse whole array# you can do it in a reverse order to change directionclassSolution:defrotate(self,nums:List[int],k:int)->None:defreverse(i,j):whilei<j:nums[i],nums[j]=nums[j],nums[i]i,j=i+1,j-1n=len(nums)k=k%nreverse(0,n-1)reverse(0,k-1)reverse(k,n-1)returnnums
It's pretty suboptimal though. Reversing three times is simplest but moves every element exactly twice, takes O(N) time and O(1) spaceIt is possible to circle shift an array moving each element exactly once also in O(N) time and O(1) space(https://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position).
# GCD solution, true O(n)classSolution:defrotate(self,nums:List[int],k:int)->None:n=len(nums)shift=n- (k%n)foriinrange(gcd(n,shift)):j=iwhile (k:= (j+shift)%n)!=i:nums[j],nums[k]=nums[k],nums[j]j=k
Other ways:
# using built-in reverse functionclassSolution:defrotate(self,nums:List[int],k:int)->None:k=k%len(nums)nums[:k]=reversed(nums[:k])nums[k:]=reversed(nums[k:])nums.reverse()# not inplaceclassSolution:defrotate(self,nums:List[int],k:int)->None: [nums.insert(0,nums.pop())for_inrange(k)]# deque built-in rotate methodclassSolution:defrotate(self,nums:List[int],k:int)->None:nums[:]=(q:=deque(nums)).rotate(k)orq# minifiedclassSolution:defrotate(self,a:List[int],k:int)->None:k%=len(a);a[:]=a[-k:]+a[:-k]
There also problems where you have to determine if string was rotated. The trick is to search in a string concatenated with its copy.
If s consists of repeating parts then at some point it should be equal to the rotated version of itself.Checking If s is a sub-string of (s+s)[1:-1] basicaly does all the job of checking for all rotated versionsof s except s+s just in a single operation (which is usually SIMD-accelerated).
classSolution:defrepeatedSubstringPattern(self,s:str)->bool:returnsin (s+s)[1:-1]
classSolution:defcheck(self,a:List[int])->bool:returnsum(map(gt,a,a[1:]+a))<2
Note thatkey=itemgetter(n) is the same length askey=lambda x:x[n] but a little bit clearer to read.The performance of itemgetter is also better than lambda (up to 2x, because of the creation of the lambda).
Sometimes you can skipkey=itemgetter(0) in comparison operations by converting an argumentto a tuple (15 characters shorter).
classSolution:defjobScheduling(self,s:List[int],e:List[int],p:List[int])->int:a=sorted(zip(s,e,p));return(f:=cache(lambdai:i-len(a)andmax(f(bisect_left(a,a[i][1],key=itemgetter(0)))+a[i][2],f(i+1))))(0)classSolution:defjobScheduling(self,s:List[int],e:List[int],p:List[int])->int:a=sorted(zip(s,e,p));return(f:=cache(lambdai:i-len(a)andmax(f(bisect_left(a,(a[i][1],)))+a[i][2],f(i+1))))(0)
You could also usemap(list.pop, v) instead of[x[-1] for x in v] to collect the last elements of the list.
classSolution:deffindDiagonalOrder(self,n:List[List[int]])->List[int]:returnmap(list.pop,sorted([i+j,j,t]fori,rinenumerate(n)forj,tinenumerate(r)))
Usingzip to get elements from the list of tuples is usually shorter, but not always:
classSolution:deffindSmallestSetOfVertices(self,n:int,edges:List[List[int]])->List[int]:return {*range(n)}-{*[*zip(*edges)][1]}classSolution:deffindSmallestSetOfVertices(self,n:int,edges:List[List[int]])->List[int]:return {*range(n)}-{jfor_,jinedges}
Python has comparison chaining. You can use expressions like0<=i<n,m>j>=0<=i<n,m>j>-1<i<n anda!=b!=c in a single condition.
classSolution:defexpressiveWords(self,s:str,words:List[str])->int:deff(v,w,j=0):foriinrange(len(v)):ifj<len(w)andv[i]==w[j]:j+=1elifv[i-1:i+2]!=v[i]*3!=v[i-2:i+1]:returnFalsereturnj==len(w)returnsum(f(s,w)forwinwords)classSolution:defexpressiveWords(self,s:str,words:List[str])->int:returnsum((f:=lambdav,w,j=0:next((0foriinrange(len(v))ifnot(j<len(w)andv[i]==w[j]and (j:=j+1))andv[i-1:i+2]!=v[i]*3!=v[i-2:i+1]),1)andj==len(w))(s,w)forwinwords)
Python handles multi-argument comparisons in the same order as anand operator, so you can use a shorter form:
classSolution:defisPowerOfFour(self,n:int)->bool:returnn>0andlog(n,4)%1==0classSolution:defisPowerOfFour(self,n:int)->bool:returnn>0==log(n,4)%1
You can check if any of the numbers is negative asx|y<0 or if both numbers are non-zero asx|y.
classSolution:defminPathSum(self,grid:List[List[int]])->int:return (f:=cache(lambdai,j:i|j<0andinforgrid[i][j]+(i|jandmin(f(i,j-1),f(i-1,j))))) (len(grid)-1,len(grid[0])-1)
You can use bitwise&,| instead ofand,or where possible. You can usex&1 instead ofx==1, if 0<=x<=2.
classSolution:defisScramble(self,s1:str,s2:str)->bool:return (f:=cache(lambdaa,b:a==borany((f(a[:i],b[:i])andf(a[i:],b[i:]))or (f(a[i:],b[:-i])andf(a[:i],b[-i:]))foriinrange(1,len(a)))))(s1,s2)classSolution:defisScramble(self,s1:str,s2:str)->bool:return (f:=cache(lambdaa,b:a==borany((f(a[:i],b[:i])&f(a[i:],b[i:]))|(f(a[i:],b[:-i])&f(a[:i],b[-i:]))foriinrange(1,len(a)))))(s1,s2)
~ reverts every bit. Therefore,~x means-x-1. You can use it as reversed index, i.e. fori=0,a[~i] meansa[-1], etc. or just replace-x-1 with~x.
For integer n, you can writen+1 as-~n,n-1 as~-n. This uses the same number of characters, but can indirectly cut spaces or parens for operator precedence.
classSolution:defgenerateMatrix(self,n:int)->List[List[int]]:r=range(n);return[[4*(n-(a:=min(min(i,n-i-1),min(j,n-j-1))))*a+(i+j-2*a+1,4*(n-2*a-1)-(i+j-2*a)+1)[i>j]forjinr]foriinr]classSolution:defgenerateMatrix(self,n:int)->List[List[int]]:r=range(n);return[[4*(n-(a:=min(i,j,~i+n,~j+n)))*a+(i+j-2*a+1,4*n-6*a-i-j-3)[i>j]forjinr]foriinr]
You can replace0 if x==y else z withx-y and z, it's a little bit counterintuitive, but shorter.
Conditionx if c else y can be written asc and x or y, it's shorter but depends on x (x should not be 0).
classSolution:defsnakesAndLadders(self,board:List[List[int]])->int:n,v,q=len(board),{1:0},[1]deff(i):x= (i-1)%ny= (i-1)//nc=board[~y][~xify%2elsex]returncifc>0elseiforiinq:forjinrange(i+1,i+7):k=f(j)ifk==n*n:returnv[i]+1ifknotinv:v[k]=v[i]+1q.append(k)return-1classSolution:defsnakesAndLadders(self,board:List[List[int]])->int:return (n:=len(board),v:={1:0},q:=[1])andnext((v[i]+1foriinqforjinrange(i+1,i+7)if (k:=(x:=(j-1)%n,y:=(j-1)//n)and ((c:=board[~y][y%2and~xorx])>0andcorj))==n*nor (knotinvand (v.update({k:v[i]+1})orq.append(k)))),-1)
You can use booleans as indices in lists, even nested:(a,(b,c)[u==w])[x==y], or you can multiply by a boolean.
classSolution:defremoveStars(self,s:str)->str:returnreduce(lambdar,c:(r[:-1],r+c)[c>'*'],s)
classSolution:defsimplifyPath(self,path:str)->str:return'/'+'/'.join(reduce(lambdar,p:(r+[p]*('.'!=p!=''),r[:-1])[p=='..'],path.split('/'),[]))
Sometimes you can useany() instead ofbool() (1 character shorter):
classSolution:defdoesAliceWin(self,s:str)->bool:returnbool({*s}&{*'aeiou'})classSolution:defdoesAliceWin(self,s:str)->bool:returnany({*s}&{*'aeiou'})
Python 3 lackscmp (3-way compare) and sign function (copysign(bool(x),x) is too long), but you can use(x>0)-(x<0) forsign(x)and(a>b)-(a<b) forcmp(a,b). Note you can use-1,0,1 indexes for Python lists natively.
classSolution:defstoneGameIII(self,v:List[int])->str:f=cache(lambdai:i<len(v)andmax(sum(v[i:i+k])-f(i+k)forkin(1,2,3)));x=f(0);return('Tie','Alice','Bob')[(x>0)-(x<0)]# return(('Tie','Bob')[x<0],'Alice')[x>0] # or like this (1 char shorter)
You can replacecmp written aslambda x:(x>0)-(x<0) with0..__le__ or.0.__le__ (11 characters shorter).
classSolution:defrearrangeArray(self,n:List[int])->List[int]:n.sort(key=lambdax:(x>0)-(x<0));returnchain(*zip(n[len(n)//2:],n))classSolution:defrearrangeArray(self,n:List[int])->List[int]:n.sort(key=0..__le__);returnchain(*zip(n[len(n)//2:],n))
You can replacex>0 predicate with0..__lt___ function and replacex!=0 withoperator.truth or justbool:
classSolution:defmergeNodes(self,h:Optional[ListNode])->Optional[ListNode]:returnh.deserialize(str([sum(v)fork,vingroupby(eval(h.serialize(h)),bool)ifk]))
Cmp as a sorting key may be reduced further to a tuple(x>p,x==p).
classSolution:defpivotArray(self,a:List[int],p:int)->List[int]:returnsorted(a,key=lambdax:(x>p,x==p))
Quite a few things become shorter withstatistics.mode (most common value of discrete or nominal data).
classSolution:deffindMissingAndRepeatedValues(self,g:List[List[int]])->List[int]:returnsum(a:=sum(g,[]))-sum({*a}),(n:=len(a))*(n+1)//2-sum({*a})classSolution:deffindMissingAndRepeatedValues(self,g:List[List[int]])->List[int]:returnmode(a:=sum(g,[])),comb(len(a)+1,2)-sum({*a})
classSolution:deffindErrorNums(self,nums:List[int])->List[int]:t=sum({*nums});returnsum(nums)-t,comb(len(nums)+1,2)-tclassSolution:deffindErrorNums(self,nums:List[int])->List[int]:returnmode(nums),comb(len(nums)+1,2)-sum({*nums})
classSolution:defmajorityElement(self,nums:List[int])->int:returnsorted(nums)[len(nums)//2]classSolution:defmajorityElement(self,nums:List[int])->int:returnmode(nums)
# https://youtu.be/pKO9UjSeLew (Joma Tech: If Programming Was An Anime)classSolution:deffindDuplicate(self,nums:List[int])->int:tortoise=hare=nums[0]whileTrue:tortoise=nums[tortoise]hare=nums[nums[hare]]iftortoise==hare:breaktortoise=nums[0]whiletortoise!=hare:tortoise=nums[tortoise]hare=nums[hare]returnhareclassSolution:deffindDuplicate(self,nums:List[int])->int:returnmode(nums)
In most cases,mode() can replace (the underlying)Counter.most_common() function:
classSolution:defrepeatedNTimes(self,a:List[int])->int:returnCounter(a).most_common(1)[0][0]classSolution:defrepeatedNTimes(self,a:List[int])->int:returnmode(a)
You can uses.encode() instead oford ormap(ord,s) It's the same length but doesn't need generation evaluation.
classSolution:defscoreOfString(self,s:str)->int:returnsum(abs(x-y)forx,yinpairwise(map(ord,s)))classSolution:defscoreOfString(self,s:str)->int:returnsum(map(abs,map(sub,s:=s.encode(),s[1:])))
You can usecount() to replaceenumerate in amap expression (4-7 characters shorter):
classSolution:defmaximumImportance(self,n:int,r:List[List[int]])->int:returnsum(v*(n-i)fori,(_,v)inenumerate(Counter(chain(*r)).most_common()))classSolution:defmaximumImportance(self,n:int,r:List[List[int]])->int:return-sum(map(mul,count(-n),sorted(Counter(chain(*r)).values())[::-1]))
classSolution:defmaximizeSquareHoleArea(self,n:int,m:int,h:List[int],v:List[int])->int:returnmin(1+max(Counter(starmap(sub,enumerate(sorted(w)))).values())forwin(h,v))**2classSolution:defmaximizeSquareHoleArea(self,n:int,m:int,h:List[int],v:List[int])->int:returnmin(1+max(Counter(map(sub,sorted(w),count())).values())forwin(h,v))**2
Starmap makes an iterator that computes the function using arguments obtained from the iterable.Used instead of map() when argument parameters have already been "pre-zipped" into tuples (seeitertools.starmap).
Applying a function to an iterable withstarmap andpairwise may be done withmap (12 chars shorter):
classSolution:deffindArray(self,p:List[int])->List[int]:returnstarmap(xor,pairwise([0]+p))classSolution:deffindArray(self,p:List[int])->List[int]:returnmap(xor,p,[0]+p)
Very often you can replacezip withmap, it evaluates iterables the same way:
classSolution:defminMovesToSeat(self,s:List[int],t:List[int])->int:returnsum(abs(a-b)fora,binzip(*map(sorted,(s,t))))classSolution:defminMovesToSeat(self,s:List[int],t:List[int])->int:returnsum(map(abs,map(sub,*map(sorted,(s,t)))))
You can also replacestarmap andenumerate withmap andcount() (7 characters shorter).
classSolution:defcountBadPairs(self,a:List[int])->int:returnsum(x*(len(a)-x)forxinCounter(starmap(sub,enumerate(a))).values())//2classSolution:defcountBadPairs(self,a:List[int])->int:returnsum(x*(len(a)-x)forxinCounter(map(sub,a,count())).values())//2
You can write combination function (binomial)n*(n-1)//2 ascomb(n,2), or replace(n-1) with~-n to cut parens.
classSolution:deftupleSameProduct(self,a)->int:returnsum(8*comb(n,2)forninCounter(starmap(mul,combinations(a,2))).values())classSolution:deftupleSameProduct(self,a)->int:returnsum(4*n*(n-1)forninCounter(starmap(mul,combinations(a,2))).values())classSolution:deftupleSameProduct(self,a)->int:returnsum(~-n*n*4forninCounter(starmap(mul,combinations(a,2))).values())
You can usenumpy.convolve for sliding windows, it's usually shorter than reduce or list comprehension:
classSolution:defmaxSatisfied(self,c:List[int],g:List[int],m:int)->int:t,a=0,[*map(mul,c,g)];[t:=(t,w:=sum(a[i:i+m]))[w>t]foriinrange(len(c)-m+1)]returnt+sum(c)-sum(a)classSolution:defmaxSatisfied(self,c:List[int],g:List[int],m:int)->int:returnmax(__import__('numpy').convolve(a:=[*map(mul,c,g)],[1]*m))+sum(c)-sum(a)
You can replaceceil(x/k) with-(-x//k) (1 character shorter):
classSolution:defmaxKelements(self,a:List[int],k:int)->int:a.sort();returnsum((x:=a.pop(),insort(a,ceil(x/3)))[0]for_inrange(k))classSolution:defmaxKelements(self,a:List[int],k:int)->int:a.sort();returnsum((x:=a.pop(),insort(a,-(-x//3)))[0]for_inrange(k))
In Python, the prod() function, available in the math module (from Python 3.8 onwards), calculates the product of all elements in an iterable.Unfortunately, you cannot represent the indices 0, 1, -1 as a single slice with step.
classSolution:defmaximumProduct(self,nums:List[int])->int:returnmax((v:=sorted(nums))[-1]*v[-2]*v[-3],v[0]*v[1]*v[-1])classSolution:defmaximumProduct(self,nums:List[int])->int:returnmax(prod((v:=sorted(nums))[-3:]),v[0]*v[1]*v[-1])
''.join(map(str,a)) can be replaced by format string multiplication and unpacking'%d'*len(a)%(*a,) (2 characters shorter):
classSolution:defnumMagicSquaresInside(self,g:List[List[int]])->int:returnsum(r[j+1]==5>q[j]%2+4!="".join(map(str,q[j:j+3]+[r[j+2],*s[j:j+3][::-1],r[j]]))in (t:='43816729'*2)+t[::-1]forq,r,sinzip(g,g[1:],g[2:])forjinrange(len(q)-2))classSolution:defnumMagicSquaresInside(self,g:List[List[int]])->int:returnsum(r[j+1]==5>q[j]%2+4!='%d'*8%(*q[j:j+3],r[j+2],*s[j:j+3][::-1],r[j])in (t:='43816729'*2)+t[::-1]forq,r,sinzip(g,g[1:],g[2:])forjinrange(len(q)-2))
classSolution:defplusOne(self,d:List[int])->List[int]:return[*map(int,str(int(''.join(map(str,d)))+1))]classSolution:defplusOne(self,d:List[int])->List[int]:return[*map(int,str(int('%d'*len(d)%(*d,))+1))]
These operators are available in a global namespace (Leetcode includes "operator" module by default).
| Operation | Syntax | Function |
|---|---|---|
| Unary | ||
| Negation (Arithmetic) | - a | neg(a) |
| Negation (Logical) | not a | not_(a) |
| Positive | + a | pos(a) |
| Truth Test | obj | truth(obj) |
| Bitwise Inversion | ~ a | invert(a) |
| Binary | ||
| Addition | a + b | add(a, b) |
| Concatenation | seq1 + seq2 | concat(seq1, seq2) |
| Containment Test | obj in seq | contains(seq, obj) |
| Division | a / b | truediv(a, b) |
| Division | a // b | floordiv(a, b) |
| Bitwise And | a & b | and_(a, b) |
| Bitwise Exclusive Or | a ^ b | xor(a, b) |
| Bitwise Or | a | b | or_(a, b) |
| Exponentiation | a ** b | pow(a, b) |
| Identity | a is b | is_(a, b) |
| Identity | a is not b | is_not(a, b) |
| Indexed Deletion | del obj[k] | delitem(obj, k) |
| Indexing | obj[k] | getitem(obj, k) |
| Left Shift | a << b | lshift(a, b) |
| Modulo | a % b | mod(a, b) |
| Multiplication | a * b | mul(a, b) |
| Matrix Multiplication | a @ b | matmul(a, b) |
| Right Shift | a >> b | rshift(a, b) |
| String Formatting | s % obj | mod(s, obj) |
| Subtraction | a - b | sub(a, b) |
| Ordering (Less Than) | a < b | lt(a, b) |
| Ordering (Less or Equal) | a <= b | le(a, b) |
| Equality | a == b | eq(a, b) |
| Difference (Not Equal) | a != b | ne(a, b) |
| Ordering (Greater or Equal) | a >= b | ge(a, b) |
| Ordering (Greater Than) | a > b | gt(a, b) |
| Ternary | ||
| Indexed Assignment | obj[k] = v | setitem(obj, k, v) |
| Slice Assignment | seq[i:j] = values | setitem(seq, slice(i, j), values) |
| Slice Deletion | del seq[i:j] | delitem(seq, slice(i, j)) |
| Slicing | seq[i:j] | getitem(seq, slice(i, j)) |
The same naming goes for the member functions, but with underscores, e.g.(1).__lt__.
Knowing precedence helps to cut parens. For example, you can replace(n-1) with~-n (binary negation).
| Precedence | Operators | Description | Associativity |
|---|---|---|---|
| 1 | () | Parentheses | Left to right |
| 2 | x[i], x[i:j] | Subscription, slicing | Left to right |
| 3 | await x | Await expression | N/A |
| 4 | ** | Exponentiation | Right to left |
| 5 | +x, -x, ~x | Positive, negative, bitwise NOT | Right to left |
| 6 | *, @, /, //, % | Multiply (matrix), division, remainder | Left to right |
| 7 | +, – | Addition and subtraction | Left to right |
| 8 | <<, >> | Shifts | Left to right |
| 9 | & | Bitwise AND | Left to right |
| 10 | ^ | Bitwise XOR | Left to right |
| 11 | | | Bitwise OR | Left to right |
| 12 | in, not in, is, is not, <, <=, >, >=, !=, == | Comparisons, membership tests, identity tests | Left to Right |
| 13 | not x | Boolean NOT | Right to left |
| 14 | and | Boolean AND | Left to right |
| 15 | or | Boolean OR | Left to right |
| 16 | if-else | Conditional expression | Right to left |
| 17 | lambda | Lambda expression | N/A |
| 18 | := | Assignment expression (walrus) | Right to left |
Seehttps://docs.python.org/3/library/itertools.html
| Iterator | Arguments | Results | Example |
|---|---|---|---|
count() | [start[,step]] | start, start+step, start+2*step, ... | count(10) → 10 11 12 13 14 ... |
cycle() | p | p0, p1, … plast, p0, p1, ... | cycle('ABCD') → A B C D A B C D ... |
repeat() | elem [,n] | elem, elem, elem, ... endlessly or up to n times | repeat(10, 3) → 10 10 10 |
| Iterator | Arguments | Results | Example |
|---|---|---|---|
accumulate() | p [,func] | p0, p0+p1, p0+p1+p2, ... | accumulate([1,2,3,4,5]) → 1 3 6 10 15 |
batched() (>=3.12) | p, n | (p0, p1, ..., p_n-1), ... | batched('ABCDEFG', n=3) → ABC DEF G |
chain() | p, q, ... | p0, p1, ... plast, q0, q1, ... | chain('ABC', 'DEF') → A B C D E F |
chain.from_iterable() | iterable | p0, p1, ... plast, q0, q1, ... | chain.from_iterable(['ABC', 'DEF']) → A B C D E F |
compress() | data, selectors | (d[0] if s[0]), (d[1] if s[1]), ... | compress('ABCDEF', [1,0,1,0,1,1]) → A C E F |
dropwhile() | predicate, seq | seq[n], seq[n+1], starting when predicate fails | dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8 |
filterfalse() | predicate, seq | elements of seq where predicate(elem) fails | filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8 |
groupby() | iterable[, key] | sub-iterators grouped by value of key(v) | groupby(['A','B','DEF'], len) → (1, A B) (3, DEF) |
islice() | seq, [start,] stop [, step] | elements from seq[start:stop:step] | islice('ABCDEFG', 2, None) → C D E F G |
pairwise() | iterable | (p[0], p[1]), (p[1], p[2]) | pairwise('ABCDEFG') → AB BC CD DE EF FG |
starmap() | func, seq | func(*seq[0]), func(*seq[1]), ... | starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000 |
takewhile() | predicate, seq | seq[0], seq[1], until predicate fails | takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4 |
tee() | it, n | it1, it2, ... itn splits one iterator into n | |
zip_longest() | p, q, ... | (p[0], q[0]), (p[1], q[1]), ... | zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D- |
| Function | Arguments | Results |
|---|---|---|
product() | p, q, ... [repeat=1] | cartesian product, equivalent to a nested for-loop |
permutations() | p[, r] | r-length tuples, all possible orderings, no repeated elements |
combinations() | p, r | r-length tuples, in sorted order, no repeated elements |
combinations_with_replacement() | p, r | r-length tuples, in sorted order, with repeated elements |
| Examples | Results |
|---|---|
product('ABCD', repeat=2) | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD |
permutations('ABCD', 2) | AB AC AD BA BC BD CA CB CD DA DB DC |
combinations('ABCD', 2) | AB AC AD BC BD CD |
combinations_with_replacement('ABCD', 2) | AA AB AC AD BB BC BD CC CD DD |
- An expression like
x&(x-1)==0is useful to check if unsignedxis power of 2 or 0 (Kernighan, rightmost bit). - You can use Kernighan to check for even values (
x%2==0or1>1&x) as1&~x(1 character shorter). - You can remove the space after a number in most cases. E.g.
i==3 and j==4becomesi==3and j==4. - You can use the * operator on a list, e.g.
[1]*8can replacerange(8)(unless you really need the counter value). - Conditions like
if i<len(r)may be replaced withif r[i:], it's 3 characters shorter. - You can replace
set(n)with{*n}(2 characters shorter). - You can convert bool with
~~()instead ofint()(as in js) or prepend with a single+(5 characters shorter). - You can subtract 1 or replace
notoperator with bitwise negation~-to save on space (1-5 characters shorter). - You can check for set membership with
{x}&sinstead ofx in s(1 character shorter). - Very often
x==0can be replaced withx<1(1 character shorter). - A condition like
h>i>=0<=j<wcan be written ash>i>-1<j<w(1 character shorter). - A condition like
i>-1<jcan be written as~i&~j(1 character shorter). - You can replace
q and q[-1]==cwithq[-1:]==[c](3 characters shorter). - Shift precedence can be used to write
(a+b)//2asa+b>>1(2 characters shorter). - You can replace
==0and!=0with<()or>()to cut space (1 character shorter).
- Don't Piss down my back and tell me it's raining: Notebook for Sarcastic, Witty, and Sharp Tongued One Liners
- Designed a one line solution for the Gmail API issue that caused hundreds of thousands $ losses to clients
- They're not characters at all, they're just brilliant repositories of fantastic, killer one-liners (Stephen Fry)
- Python One-Liners: Write Concise, Eloquent Python Like a Professional
- Python One-Liners - Concise Python Code
- One-line coder makes me depressed
- Tips for Golfing in Python
- Leetcode Daily Analysis
- King of One-Liners
About
A brilliant repository of fantastic, killer one-liners
Topics
Resources
Uh oh!
There was an error while loading.Please reload this page.