Skip to content
BranchesTags

Latest commit

History

7,417 Commits

Folders and files

NameName
Last commit message
Last commit date
binarysearch
binarysearch
leetcode
leetcode
.gitignore
.gitignore
README.md
README.md

Repository files navigation

Oneliners

Just FYI, this isn't just README.md, it's also more than a thousand solutions in the repository. There is also stats here:

Why Python

Python is almost always shorter than other languages (and has relevant libraries). There are, of course, exceptions.

Python (3.14):

return(k-1).bit_count()&1

Ruby or Scala can beat it sometimes because they don't need a return statement. Ruby 3.2.10 is longer here:

(k-1).to_s(2).count('1')&1

Ruby 3.3+ can be shorter when Leetcode updates the launcher, so it could win in character count for simple tasks:

(k-1).count_ones&1

Even C++ is sometimes shorter than Python (but mostly not). In this particular case it's shorter by one character:

return popcount(k-1u)&1;

Note that u and ; are mandatory here. If I find a shorter solution in other language I usually add it in comments.

  • If you find a shorter solution that passes online leetcode tests (no MLE, no TLE), post it to the issues section.

Leetcode-specific

Leetcode imports modules as wildcards, so you don't have to specify module names. There are some exceptions:

  • Single bisect() without a prefix triggers object is not callable, use bisect_left() or bisect_right().
  • You have to specify re.sub because sub without a prefix is operator.sub.
  • Default pow is __builtins__['pow'] (supports up to 3 arguments, including the modulus), not math.pow.

For example, Leetcode header has import * from math, so we use comb() instead of math.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, and sortedcontainers).

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 as ListNode('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 has serialize and deserialize functions for lists and trees:

classSolution:
defreverseList(self, h: Optional[ListNode]) ->Optional[ListNode]:
returnhandh.deserialize(str(eval(h.serialize(h))[::-1]))

There is also has_cycle 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 (see gist):

withopen(__file__, 'rt') asf: print(f.read())

The solution driver code writes all results to the user.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. (see gist):

importsubprocessprint(subprocess.run(["ls", "-la", "/"]))

You can also set your own execution time using atexit:

__import__('atexit').register(lambda: open("display_runtime.txt", "w").write("0")) # 0..2147483647

See LeetCode-Feedback/LeetCode-Feedback#25646 (we have decided not to allocate development resources to fixing it at this time.)

Minus-two-liners

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 omit self 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

Shortest

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

Considering type autconversion stopped working in 2024:

classSolution:
defstoneGame(self, piles: List[int]) ->bool:
return2>1

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 be pass, as function returns None. You can also do:

classSolution:isStrictlyPalindromic=not_

Lambdas

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 since PEP 3113, however, if your lambda is flat, there is an upgrade path:

  • lambda (x, y): x + y in Python 2 becomes lambda xy:(lambda x,y: x+y)(*xy) in Python 3.

You can also unpack multiple tuples as lambda 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]

Generators

Generator expressions (x for y in z) are memory efficient since they only require memory for the 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 using all(), any() or sum(), depending on the return values. You can also save a few chars using [*g] syntax instead of list(g) where g is a generator function. Generator length len(list(g)) can be calculated in constant memory as sum(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)

Iterators

Generators provide an easy, built-in way to create instances of Iterators. Iterators are objects that have an __iter__ and a __next__ method. The iter() 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 use iter() 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))

Dictionaries

Starting from Python 3.7 dictionary order is guaranteed to be insertion order.

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.

Counters

Counters (collections.Counter()) can be updated, similar to dict.update(), it's much faster than a sum of counters. E.g. c[i]+=1 is equivalent to c.update([i]), c[i]-=1 is c.update({i:-1}). To delete a key you can use the .pop method (same as del), it's shorter than popitem().

Note that c.update({i:x}) and setitem(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, see documentation):

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 use total() 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 replace Counter with set and count (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))

Unlike dict, python set does NOT maintain insertion order. There are modules that implements ordered set.

You can use SortedList 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))

Walrus operator

The controversial walrus operator (:=) added in Python 3.8 (PEP-572, when Guido 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. in map(f:=x,y) or next(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))

Setting values

You can use __setattr__ for dictionaries or __setitem__ for lists (both member functions return None). You can also use setattr or setitem functions from the operator module, e.g. c[x]=1 is the same as setitem(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 that setitem 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 than setitem.

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)

Classes

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 use types.new_class() it says TypeError: .__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])})

Bisect

Binary search can be replaced by the built-in bisect methods. Custom binary search can use either an item getter object or a key function (since Python 3.10). Stock bisect implementation is in bisect.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

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

While loops are not very oneliner-friendly. You can use next() function with an endless count() 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 use takewhile(), it's also a generator, so you need to expand it (e.g. with repeat(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 try any() or all() as a while loop instead of next(), it may be shorter. You can assure that expression never returns None, using [] ([None] evaluates to True).

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 with exec. Unlike eval, 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)

Swap

To swap values you can use either exec (inline version of a,b=b,a) or a temporary variable (t:=a,a:=b,b:=t).

Note that eval accepts only a single expression, and returns the value of the given expression, whereas exec ignores the return value from its code, and always returns None, its use has no effect on 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])))()

Map

You can use map 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 to True with !=0 instead of bool() (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)

BFS

DFS is usually shorter than BFS, but not always. The loop can be severely size-optimized. It's usually all(), any(), or the recursive function for unpacking the queue, but it can be a single comprehension. The trick is that queue is not getting reiterated each time, it continues from the last index.

classSolution:
defminScore(self, n: int, roads: List[List[int]]) ->int:
g,s,q,r=defaultdict(list),set(),[1],infforu,v,winroads:
g[u].append((v,w))
g[v].append((u,w))
whileq:
u=q.pop()
forv,wing[u]:
r=min(r,w)
ifvnotins:
q.append(v)
s.add(v)
returnrclassSolution:
defminScore(self, n: int, r: List[List[int]]) ->int:
g=defaultdict(list);[g[u].append((v,w))org[v].append((u,w))foru,v,winr];
q=[1];returnmin(q.append(v)orwforuinqforv,wing.pop(u,[]))

Unicode Find

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 at https://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

Cache decorator, @lru_cache or @cache (since Python 3.9) may be used as an inline function cache(lambda ...). Essentially, a built-in memoization. Brings computation complexity from exponential to quadratic or linear, depending of the problem. Decorator source code is in functools.py. You can also implement C++ 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 with cache_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 as f=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)

Cache decorator doesn't support list parameters, but you can unwrap lists without casting to tuple:

classSolution:
defpredictTheWinner(self, n: List[int]) ->bool:
return(f:=cache(lambda*t:tandmax(t[0]-f(*t[1:]),t[-1]-f(*t[:-1]))or0))(*n)>=0

Reduce

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]

Product

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]

Combinations

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)

Semicolons

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]

Math tricks

Many leetcode problems use Fibonacci sequence that can be calculated using a variety of different methods.

# generating functionclassSolution:
deffib(self, n: int) ->int:
p=[0]*(n+2)
p[1]=1foriinrange(n):
p[i+1]+=p[i]
p[i+2]+=p[i]
returnp[n]
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)
# polynomial expontiation, https://blog.paulhankin.net/fibonacci2/classSolution:
deffib(self, n: int) ->int:
x=1<< (n+2)
returnpow(x, n+1, x**2-x-1) %xclassSolution:
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# (a*X + b) % X = b implies that (a*X + b) // X = aclassSolution:
deffib(self, n: int) ->int:
returnpow(x:=2<<n,n,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

Factorial

Leetcode simply have a global math import that includes factorial(). You could do lambdas if you want.

f=lambdax:x<2orx*f(x-1)
prod(range(1,x+1))
factorial(x)

Regular expressions

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)

Accumulate

There are many uses for itertools.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)))

Kadane

For the Kadane-like problems you have to maintain a couple of counters. You can just use max 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)

Asterisk operator

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) means a=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))

Rotations

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 come up with the right aha! insight. Let's view it as transforming the array AB into the array BA, but let's also assume we have a subroutine that reverses the elements in a specified portion of 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 by five positions (Figure 1) is from Doug Mcllroy; try it. The reversal code is time- and space-efficient, and is so short and simple that it's pretty hard to get wrong.

It is exactly the code that Kernighan and Plauger use in the text editor in their book. Brian Kernighan reports that this code indeed ran correctly the first time it was executed, while their previous code for a similar task contained several bugs. This code is also used in several text editors, including the UNIX 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) space It 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 versions of 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

Itemgetter

Note that key=itemgetter(n) is the same length as key=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 skip key=itemgetter(0) in comparison operations by converting an argument to 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)

Pop

You could also use map(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)))

Zip

Using zip 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}

Comparison chaining

Python has comparison chaining. You can use expressions like 0<=i<n, m>j>=0<=i<n, m>j>-1<i<n and a!=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 an and 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 as x|y<0 or if both numbers are non-zero as x|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 of and,or where possible. You can use x&1 instead of x==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)

Bitwise inversion

~ reverts every bit. Therefore, ~x means -x-1. You can use it as reversed index, i.e. for i=0, a[~i] means a[-1], etc. or just replace -x-1 with ~x.

For integer n, you can write n+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]

If-Else

You can replace 0 if x==y else z with x-y and z, it's a little bit counterintuitive, but shorter.

Condition x if c else y can be written as c 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)

Boolean

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 use any() instead of bool() (1 character shorter):

classSolution:
defdoesAliceWin(self, s: str) ->bool:
returnbool({*s}&{*'aeiou'})
classSolution:
defdoesAliceWin(self, s: str) ->bool:
returnany({*s}&{*'aeiou'})

Cmp

Python 3 lacks cmp (3-way compare) and sign function (copysign(bool(x),x) is too long), but you can use (x>0)-(x<0) for sign(x) and (a>b)-(a<b) for cmp(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 replace cmp written as lambda x:(x>0)-(x<0) with 0..__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 replace x>0 predicate with 0..__lt___ function and replace x!=0 with operator.truth or just bool:

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))

Mode

Quite a few things become shorter with statistics.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)

Encode

You can use s.encode() instead of ord or map(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:])))

Count

You can use count() to replace enumerate in a map 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

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 (see itertools.starmap).

Applying a function to an iterable with starmap and pairwise may be done with map (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 replace zip with map, 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 replace starmap and enumerate with map and count() (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

Comb

You can write combination function (binomial) n*(n-1)//2 as comb(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())

Numpy

You can use numpy.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)

Ceil

You can replace ceil(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))

Prod

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

''.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))]

Tables

Operators

These operators are available in a global namespace (Leetcode includes "operator" module by default).

OperationSyntaxFunction
Unary
Negation (Arithmetic)- aneg(a)
Negation (Logical)not anot_(a)
Positive+ apos(a)
Truth Testobjtruth(obj)
Bitwise Inversion~ ainvert(a)
Binary
Additiona + badd(a, b)
Concatenationseq1 + seq2concat(seq1, seq2)
Containment Testobj in seqcontains(seq, obj)
Divisiona / btruediv(a, b)
Divisiona // bfloordiv(a, b)
Bitwise Anda & band_(a, b)
Bitwise Exclusive Ora ^ bxor(a, b)
Bitwise Ora | bor_(a, b)
Exponentiationa ** bpow(a, b)
Identitya is bis_(a, b)
Identitya is not bis_not(a, b)
Indexed Deletiondel obj[k]delitem(obj, k)
Indexingobj[k]getitem(obj, k)
Left Shifta << blshift(a, b)
Moduloa % bmod(a, b)
Multiplicationa * bmul(a, b)
Matrix Multiplicationa @ bmatmul(a, b)
Right Shifta >> brshift(a, b)
String Formattings % objmod(s, obj)
Subtractiona - bsub(a, b)
Ordering (Less Than)a < blt(a, b)
Ordering (Less or Equal)a <= ble(a, b)
Equalitya == beq(a, b)
Difference (Not Equal)a != bne(a, b)
Ordering (Greater or Equal)a >= bge(a, b)
Ordering (Greater Than)a > bgt(a, b)
Ternary
Indexed Assignmentobj[k] = vsetitem(obj, k, v)
Slice Assignmentseq[i:j] = valuessetitem(seq, slice(i, j), values)
Slice Deletiondel seq[i:j]delitem(seq, slice(i, j))
Slicingseq[i:j]getitem(seq, slice(i, j))

The same naming goes for the member functions, but with underscores, e.g. (1).__lt__.

Precedence

Knowing precedence helps to cut parens. For example, you can replace (n-1) with ~-n (binary negation).

PrecedenceOperatorsDescriptionAssociativity
1()ParenthesesLeft to right
2x[i], x[i:j]Subscription, slicingLeft to right
3await xAwait expressionN/A
4**ExponentiationRight to left
5+x, -x, ~xPositive, negative, bitwise NOTRight to left
6*, @, /, //, %Multiply (matrix), division, remainderLeft to right
7+, –Addition and subtractionLeft to right
8<<, >>ShiftsLeft to right
9&Bitwise ANDLeft to right
10^Bitwise XORLeft to right
11|Bitwise ORLeft to right
12in, not in, is, is not, <, <=, >, >=, !=, ==Comparisons, membership tests, identity testsLeft to Right
13not xBoolean NOTRight to left
14andBoolean ANDLeft to right
15orBoolean ORLeft to right
16if-elseConditional expressionRight to left
17lambdaLambda expressionN/A
18:=Assignment expression (walrus)Right to left

Itertools

See https://docs.python.org/3/library/itertools.html

Infinite operators

IteratorArgumentsResultsExample
count()[start[,step]]start, start+step, start+2*step, ...count(10) → 10 11 12 13 14 ...
cycle()pp0, 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 timesrepeat(10, 3) → 10 10 10

Iterators terminating on the shortest input sequence

IteratorArgumentsResultsExample
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()iterablep0, 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, seqseq[n], seq[n+1], starting when predicate failsdropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8
filterfalse()predicate, seqelements of seq where predicate(elem) failsfilterfalse(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, seqfunc(*seq[0]), func(*seq[1]), ...starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000
takewhile()predicate, seqseq[0], seq[1], until predicate failstakewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4
tee()it, nit1, 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-

Combinatoric iterators

FunctionArgumentsResults
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, rr-length tuples, in sorted order, no repeated elements
combinations_with_replacement()p, rr-length tuples, in sorted order, with repeated elements
ExamplesResults
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

Notes

  • An expression like x&(x-1)==0 is useful to check if unsigned x is power of 2 or 0 (Kernighan, rightmost bit).
  • You can use Kernighan to check for even values (x%2==0 or 1>1&x) as 1&~x (1 character shorter).
  • You can remove the space after a number in most cases. E.g. i==3 and j==4 becomes i==3and j==4.
  • You can use the * operator on a list, e.g. [1]*8 can replace range(8) (unless you really need the counter value).
  • Conditions like if i<len(r) may be replaced with if r[i:], it's 3 characters shorter.
  • You can replace set(n) with {*n} (2 characters shorter).
  • You can convert bool with ~~() instead of int() (as in js) or prepend with a single + (3 characters shorter).
  • You can subtract 1 or replace not operator with bitwise negation ~- to save on space (1-5 characters shorter).
  • You can check for set membership with {x}&s instead of x in s (1 character shorter).
  • Very often x==0 can be replaced with x<1 (1 character shorter).
  • A condition like 0<=i<h and 0<=j<w can be written as h>i>=0<=j<w or h>i>-1<j<w (7 characters shorter).
  • A condition like i>=0 and j>=0 can be written as i>-1<j or ~i&~j or i|j>0 (7 characters shorter).
  • A condition like i==0 and j==0 can be written as i==0==j or i+j<1 (7 characters shorter).
  • A condition like i<0 or j<0 can be written as min(i,j)<0 or i|j<0 (5 characters shorter).
  • You can replace q and q[-1]==c with q[-1:]==[c] (3 characters shorter).
  • Shift precedence can be used to write (a+b)//2 as a+b>>1 (2 characters shorter).
  • You can replace [...]==0 and [...]!=0 with [...]<() or [...]>() to cut space (1 character shorter).
  • You can replace i!=n-1 and j!=m-1 with i+j<n+m-2, and i<m and j<n with i-n<0>j-m (3 characters shorter).
  • You can replace x in s where s is set with {x}&s (1 character shorter).
  • You can replace x not in s where s is set with {x}-s (5 characters shorter).
  • Very often you can declare a set using {-1} or {0} instead of set() (1-2 characters shorter).
  • You can use len(bin(n))-2 instead of n.bit_length() (1 character shorter).

References

About

A brilliant repository of fantastic, killer one-liners

joric.github.io/leetcode/

Topics

leetcodeone-linerspython

Resources

Readme
Activity

Stars

77 stars

Watchers

3 watching

Forks

5 forks
Report repository

Releases

Packages

Contributors

Languages