Source: Two Sum
Description:
Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
.You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Answer:
return [(i, nums[i+1:].index(target - nums[i]) + i + 1) for i in range(len(nums)) if target - nums[i] in nums[i+1:]][0]
Source: Roman to Integer
Description:
Roman numerals are represented by seven different symbols:
I
,V
,X
,L
,C
,D
andM
.Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example,
2
is written asII
in Roman numeral, just two ones added together.12
is written asXII
, which is simplyX + II
. The number27
is written asXXVII
, which isXX + V + II
.Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not
IIII
. Instead, the number four is written asIV
. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written asIX
. There are six instances where subtraction is used:
I
can be placed beforeV
(5) andX
(10) to make 4 and 9.X
can be placed beforeL
(50) andC
(100) to make 40 and 90.C
can be placed beforeD
(500) andM
(1000) to make 400 and 900.Given a roman numeral, convert it to an integer.
Answer:
return sum(starmap(lambda x, y: x if x >= y else -x , pairwise([p for p in map(lambda c: {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}[c], s)]))) + {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}[s[-1]]
Explanations:
- First convert all characters to numbers.
pairwise()
and check: if a digit smaller than the next, negative it's value, else keep it's value.sum()
the returned values.- Add the last digit.
Source: Binary Prefix Divisible By 5
Description:
You are given a binary array
nums
(0-indexed).We define
xi
as the number whose binary representation is the subarraynums[0..i]
(from most-significant-bit to least-significant-bit).
- For example, if
nums = [1,0,1]
, thenx0 = 1
,x1 = 2
, andx2 = 5
.Return an array of booleans
answer
whereanswer[i]
istrue
ifxi
is divisible by5
.
Answer:
return reduce(lambda p, n: [p[0] + str(n), p[1] + [int(p[0] + str(n), 2)%5 == 0]], [["", []]] + nums)[1]
Source: Minimum Add to Make Parentheses Valid
Description:
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, or- It can be written as
(A)
, whereA
is a valid string.You are given a parentheses string
s
. In one move, you can insert a parenthesis at any position of the string.
- For example, if
s = "()))"
, you can insert an opening parenthesis to be"(**(**)))"
or a closing parenthesis to be"())**)**)"
.Return the minimum number of moves required to make
s
valid.
Answer:
return len(functools.reduce(lambda c1, c2: c2 if not c1 else c1[:-1] if c2==")" and c1[-1] == "(" else c1 + c2, s)) if s else len(s)
Explanations:
Uses Python reduce()
on string s, whenever it has '()' in the result of reduce()
step then remove this from string.
- Can use
''.join((c1, c2)).replace("()", "")
but the performance is pretty bad. c2 if not c1 else ...
: prevent Exception onc1[:-1]
when c1 is empty.c1[:-1] if c2==")" and c1[-1] == "(" else c1 + c2
: ifc1 + c2
ends with()
, then takec1[:1]
only, else takec1 + c2
.
Source: Palindrome Number
Description:
Given an integer
x
, returntrue
ifx
is palindrome integer.An integer is a palindrome when it reads the same backward as forward.
- For example,
121
is a palindrome while123
is not.
Answer:
return str(x) == str(x)[::-1]
Source: Remove Palindromic Subsequences
Description:
You are given a string
s
consisting only of letters 'a
' and 'b
'. In a single step you can remove one palindromic subsequence froms
.Return the minimum number of steps to make the given string empty.
A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.
A string is called palindrome if is one that reads the same backward as well as forward.
Answer:
return 2 - (s == s[::-1]) - (s == "")
Explanations:
The problem is more of a brainteaser. Since, we can remove palindromic subsequence. Hence,
- If
s
is empty, answer would be 0 since we need 0 steps to make the given string empty. - If
s
is palindrome, answer would be 1 since we can remove the entire string, since entire string is palindromic subsequence. - If
s
isn't palindrome, we can take alla
's as a subsequence. This will be palindromic subsequence, remove it. At next step, we can take allb
's as a subesequecne, this will be a palindromic subsequence, remove it. Hence, answer would be 2
Thus, atmost we can have minimum as 2
, we can subtract 1
from it if s
is a palindrome, can subtract another 1
if s
is empty. Hence, the python one-liner!
Source: Plus One
Description:
You are given a large integer represented as an integer array
digits
, where eachdigits[i]
is theith
digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading0
's.Increment the large integer by one and return the resulting array of digits.
Answer:
return list(str(int(''.join(map(str, digits))) + 1))
Explanations:
-
Convert list of numbers to number by join()
-
+1 and returns the list of intergers.
Source: Valid Palindrome
Description:
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string
s
, returntrue
if it is a palindrome, orfalse
otherwise.
Answer:
return reduce(lambda p, c: p+c if c.isalpha() or c.isnumeric() else p, ' ' + s).lower().strip() == reduce(lambda p, c: p+c if c.isalpha() or c.isnumeric() else p, ' ' + s).lower()[::-1].strip()
Explanations:
- I don't know why it's not TLE lmao.
Source: Squares of a Sorted Array
Description:
Given an integer array
nums
sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Answer:
return sorted(map(lambda n: n*n, nums))
Source: Sqrt(x)
Description:
Given a non-negative integer
x
, compute and return the square root ofx
.Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
Note: You are not allowed to use any built-in exponent function or operator, such as
pow(x, 0.5)
orx ** 0.5
.
Answer:
return next((i for i in range(0, x) if i*i > x), 2) - 1 if x > 1 else x
Explanations:
Note that the requirement is: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5)
or x ** 0.5
. Without this, the solution could be as easy as: floor(sqrt(x))
Solution is to find the first number i that i*i > x, then minus with 1.
- If x = 2, then next() returns default value of 2, 2 - 1 = 1
- Other cases: input 0 returns 0, input 1 returns 1
Source: Single Number
Description:
Given a non-empty array of integers
nums
, every element appears twice except for one. Find that single one.You must implement a solution with a linear runtime complexity and use only constant extra space.
Answer 1:
return sum(set(nums)) * 2 - sum(nums)
Explanation: It's just simple mathematic approach.
Answer 2:
return reduce(lambda p, n: p ^ n, nums)
Explanation: Base on this genius solution from leetcode.
Answer 3:
return collections.Counter(nums).most_common()[-1][0]
Explanation: Simply find the least common number.
Source: Reverse Bits
Description:
Reverse bits of a given 32 bits unsigned integer.
Note:
- Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
- In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer
-3
and the output represents the signed integer-1073741825
.
Answer:
return int(bin(n)[2:][::-1].ljust(32, '0'), 2)
Source: Count Prefixes of a Given String
Description:
You are given a string array
words
and a strings
, wherewords[i]
ands
comprise only of lowercase English letters.Return the number of strings in
words
that are a prefix ofs
.A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.
Answer:
return len([w for w in words if w == s[:len(w)]])
Source: Add Two Integers
Description:
Given two integers
num1
andnum2
, return the sum of the two integers.
Answer:
return num1 + num2
Source: Find Closest Number to Zero
Description:
Given an integer array
nums
of sizen
, return the number with the value closest to0
innums
. If there are multiple answers, return the number with the largest value.
Answer:
return reduce(lambda a, n: a if abs(a) < abs(n) else max(a, n) if abs(a) == abs(n) else n, nums)
Source: Percentage of Letter in String
Description:
Given a string
s
and a characterletter
, return the percentage of characters ins
that equalletter
rounded down to the nearest whole percent.
Answer:
return s.count(letter) * 100 // len(s)
Source: Largest 3-Same-Digit Number in String
Description:
You are given a string
num
representing a large integer. An integer is good if it meets the following conditions:
- It is a substring of
num
with length3
.- It consists of only one unique digit.
Return the maximum good integer as a string or an empty string
""
if no such integer exists.Note:
- A substring is a contiguous sequence of characters within a string.
- There may be leading zeroes in
num
or a good integer.
Answer 1:
return [triple for triple in ['999','888','777','666','555','444','333','222','111','000',''] if triple in num][0]
Explanations:
- Check if each triple in inputted
num
. - The first triple that found is the largest, so get the [0]
- As
''
always in any string, if no triple found innum
,[''][0]
is returned.
Answer 2:
return next((triple for triple in ['999','888','777','666','555','444','333','222','111','000'] if triple in num), '')
Explanations:
-
Use
next()
to find the first triple. -
The triple list is in decreasing order, the first triple that found is the largest.
-
If no triple found,
next()
returns default value of''
Source: Thousand Separator
Description:
Given an integer
n
, add a dot (".") as the thousands separator and return it in string format.
Answer:
return '.'.join([str(n)[max(0, i-3):i] for i in range(len(str(n)), 0, -3)][::-1])
Source: Shuffle String
Description:
You are given a string
s
and an integer arrayindices
of the same length. The strings
will be shuffled such that the character at theith
position moves toindices[i]
in the shuffled string.Return the shuffled string.
Answer:
return ''.join([s[indices.index(i)] for i in range(len(s))])
Source: Concatenation of Array
Description:
Given an integer array
nums
of lengthn
, you want to create an arrayans
of length2n
whereans[i] == nums[i]
andans[i + n] == nums[i]
for0 <= i < n
(0-indexed).Specifically,
ans
is the concatenation of twonums
arrays.Return the array
ans
.
Answer:
return nums*2
Source: Build Array from Permutation
Description:
Given a zero-based permutation
nums
(0-indexed), build an arrayans
of the same length whereans[i] = nums[nums[i]]
for each0 <= i < nums.length
and return it.A zero-based permutation
nums
is an array of distinct integers from0
tonums.length - 1
(inclusive).
Answer:
return [nums[nums[i]] for i in range(0, len(nums))]
Source: Running Sum of 1d Array
Description:
Given an array
nums
. We define a running sum of an array asrunningSum[i] = sum(nums[0]…nums[i])
.Return the running sum of
nums
.
Answer:
return accumulate(nums)
# Using reduce
return reduce(lambda p, n: p + [p[-1] + n], [[0]] + nums)[1:]
# Using list comprehension with sum()
return [sum(nums[:i]) for i in range(1, len(nums) + 1)]
Bonus:
This answer is hilarious:
class Solution:
runningSum=accumulate
Source: Final Value of Variable After Performing Operations
Description:
There is a programming language with only four operations and one variable
X
:
++X
andX++
increments the value of the variableX
by1
.--X
andX--
decrements the value of the variableX
by1
.Initially, the value of
X
is0
.Given an array of strings
operations
containing a list of operations, return the final value ofX
after performing all the operations.
Answer:
return sum([-1 if "--" in op else 1 for op in operations])
Source: Richest Customer Wealth
Description:
You are given an
m x n
integer gridaccounts
whereaccounts[i][j]
is the amount of money theith
customer has in thejth
bank. Return the wealth that the richest customer has.A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.
Answer:
return max(map(sum, accounts))
Source: Defanging an IP Address
Description:
Given a valid (IPv4) IP
address
, return a defanged version of that IP address.A defanged IP address replaces every period
"."
with"[.]"
.
Answer:
return address.replace(".", "[.]")
Source: Maximum Number of Words Found in Sentences
Description:
A sentence is a list of words that are separated by a single space with no leading or trailing spaces.
You are given an array of strings
sentences
, where eachsentences[i]
represents a single sentence.Return the maximum number of words that appear in a single sentence.
Answer:
return max(map(len, map(lambda s: s.split(), sentences)))
Source: Shuffle the Array
Description:
Given the array
nums
consisting of2n
elements in the form[x1,x2,...,xn,y1,y2,...,yn]
.Return the array in the form
[x1,y1,x2,y2,...,xn,yn]
.
Answer:
return [n for a in zip(nums[:n], nums[n:]) for n in a]
# Using chain from itertools
return chain.from_iterable([a for a in zip(nums[:n], nums[n:])])
Source: Minimum Sum of Four Digit Number After Splitting Digits
Description:
You are given a positive integer
num
consisting of exactly four digits. Splitnum
into two new integersnew1
andnew2
by using the digits found innum
. Leading zeros are allowed innew1
andnew2
, and all the digits found innum
must be used.
- For example, given
num = 2932
, you have the following digits: two2
's, one9
and one3
. Some of the possible pairs[new1, new2]
are[22, 93]
,[23, 92]
,[223, 9]
and[2, 329]
.Return the minimum possible sum of
new1
andnew2
.
Answer:
return int(''.join(compress(sorted(str(num)), [1, 0, 1, 0]))) + int(''.join(compress(sorted(str(num)), [0, 1, 0, 1])))
Explanations:
You don't have to generate all possible combinations of 4 digits. Just sort the digits in decreasing order, the minimum sum always equal: digit_0 * 10 + digit_2 + digit_1 * 10 + digit_3
Source: Number of Good Pairs
Description:
Given an array of integers
nums
, return the number of good pairs.A pair
(i, j)
is called good ifnums[i] == nums[j]
andi
<j
.
1 <= nums.length <= 100
1 <= nums[i] <= 100
Answer 1:
return reduce(lambda c, n: [c[0] + c[1].count(n), c[1] + [n]], [[0, []]] + nums)[0]
Explanation:
-
Feed
[count, [appearances]]
tonums
as start of reduce. -
Each step of
reduce
:-
Check if number already appeared in previous steps. Count the appearances.
-
Remember the counted number.
-
Answer 2:
return sum(k * (k - 1) / 2 for k in collections.Counter(A).values())
Explanation:
Credit to lee215, please upvote him.
Source: Jewels and Stones
Description:
You're given strings
jewels
representing the types of stones that are jewels, andstones
representing the stones you have. Each character instones
is a type of stone you have. You want to know how many of the stones you have are also jewels.Letters are case sensitive, so
"a"
is considered a different type of stone from"A"
.
1 <= jewels.length, stones.length <= 50
jewels
andstones
consist of only English letters.- All the characters of
jewels
are unique.
Answer:
return sum([1 for s in stones if s in jewels])
Source: Kids With the Greatest Number of Candies
Description:
There are
n
kids with candies. You are given an integer arraycandies
, where eachcandies[i]
represents the number of candies theith
kid has, and an integerextraCandies
, denoting the number of extra candies that you have.Return a boolean array
result
of lengthn
, whereresult[i]
istrue
if, after giving theith
kid all theextraCandies
, they will have the greatest number of candies among all the kids**, orfalse
otherwise.Note that multiple kids can have the greatest number of candies.
n == candies.length
2 <= n <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50
Answer:
return [k + extraCandies >= max(candies) for k in candies]
Source: Third Maximum Number
Description:
Given an integer array
nums
, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
Answer:
return sorted(set(nums))[-3] if len(set(nums)) > 2 else max(nums)
Explanation:
Sort the list in increasing order then get the item with index -3.
As we does not count the number with same value, convert the list with set()
Source: Reverse Words in a String III
Description:
Given a string
s
, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Answer:
return ' '.join([w[::-1] for w in s.split()])
Source: Minimum Time Visiting All Points
Description:
On a 2D plane, there are
n
points with integer coordinatespoints[i] = [xi, yi]
. Return the minimum time in seconds to visit all the points in the order given bypoints
.You can move according to these rules:
- In
1
second, you can either:
- move vertically by one unit,
- move horizontally by one unit, or
- move diagonally
sqrt(2)
units (in other words, move one unit vertically then one unit horizontally in1
second).- You have to visit the points in the same order as they appear in the array.
- You are allowed to pass through points that appear later in the order, but these do not count as visits.
Answer:
return sum([max(abs(p[1][0] - p[0][0]), abs(p[1][1] - p[0][1])) for p in pairwise(points)])
Explanation:
-
Number of moves between
(x0, y0)
and(x1, y1)
equals number of moves between(0, 0)
and(abs(x1-x0), abs(y1-y0))
, call it(delta_x, delta_y)
.Assumes that
delta_y
>delta_x
, the best path is to start from(0, 0)
to(delta_x, delta_x)
, then move from(delta_x, delta_x)
to(delta_x, delta_y)
. The first path takesdelta_x
moves, second path takesdelta_y - delta_x
moves. The total number of moves isdelta_x + delta_y - delta_x = delta_y
Vice versa it takes
delta_x
moves ifdelta_x
>delta_y
Source: Maximum 69 Number
Description:
You are given a positive integer
num
consisting only of digits6
and9
.Return the maximum number you can get by changing at most one digit (
6
becomes9
, and9
becomes6
).
Answer:
return int(str(num).replace('6', '9', 1))
Source: Find First Palindromic String in the Array
Description:
Given an array of strings
words
, return the first palindromic string in the array. If there is no such string, return an empty string""
.A string is palindromic if it reads the same forward and backward.
Answer:
return next((w for w in words if w == w[::-1]), '')
Source: Number Of Rectangles That Can Form The Largest Square
Description:
You are given an array
rectangles
whererectangles[i] = [li, wi]
represents theith
rectangle of lengthli
and widthwi
.You can cut the
ith
rectangle to form a square with a side length ofk
if bothk <= li
andk <= wi
. For example, if you have a rectangle[4,6]
, you can cut it to get a square with a side length of at most4
.Let
maxLen
be the side length of the largest square you can obtain from any of the given rectangles.Return the number of rectangles that can make a square with a side length of
maxLen
.
Answer:
return [min(l) for l in rectangles].count(max([min(l) for l in rectangles]))
Notice: What a shame to write code like this. I'm sorry.
Answer 2:
return sorted(Counter([min(l) for l in rectangles]).most_common())[-1][1]
Explanation: Sort the return of most_common()
, get count value of largest rectangles.
Source: Find the Highest Altitude
Description:
There is a biker going on a road trip. The road trip consists of
n + 1
points at different altitudes. The biker starts his trip on point0
with altitude equal0
.You are given an integer array
gain
of lengthn
wheregain[i]
is the net gain in altitude between pointsi
andi + 1
for all (0 <= i < n)
. Return the highest altitude of a point.
Answer:
return max(accumulate([0] + gain))
Source: Implement strStr()
Description:
Implement strStr().
Given two strings
needle
andhaystack
, return the index of the first occurrence ofneedle
inhaystack
, or-1
ifneedle
is not part ofhaystack
.Clarification:
What should we return when
needle
is an empty string? This is a great question to ask during an interview.For the purpose of this problem, we will return 0 when
needle
is an empty string. This is consistent to C's strstr() and Java's indexOf().
Answer:
return haystack.find(needle)
Explanations: Edge cases already taken care of.
Source: Contains Duplicate
Description:
Given an integer array
nums
, returntrue
if any value appears at least twice in the array, and returnfalse
if every element is distinct.
Answer:
return len(set(nums)) != len(nums)
Explanations:
set()
deletes all duplicates. Therefore, if its length is different than the original list, at least 1 element is repeated.
Source: Number of 1 Bits
Description:
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer.
-3
.
Answer:
return n.bit_count()
Explanations:
Python 3.10 introduced int.bit_count()
.
Source: Valid Anagram
Description:
Given two strings
s
andt
, returntrue
ift
is an anagram ofs
, andfalse
otherwise.An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Answer:
return collections.Counter(s) == collections.Counter(t)
Explanations:
collections.Counter()
is a dict subclass for counting hashable objects. Simply checking if they are equal does the trick.
Source: Missing Number
Description:
Given an array
nums
containingn
distinct numbers in the range[0, n]
, return the only number in the range that is missing from the array.
Answer:
return sum(range(1, len(nums) + 1)) - sum(nums)
Explanations: Taking the difference between the sum of the numbers, and the whole range, will reveal the missing number.
Source: To Lower Case
Description:
Given a string
s
, return the string after replacing every uppercase letter with the same lowercase letter.
Answer(s):
return str.lower()
return "".join(chr(ord(c) + 32) if "A" <= c <= "Z" else c for c in str)
return "".join(chr(ord(c) + 32) if 65 <= ord(c) <= 90 else c for c in str)
return ''.join(chr(ord(c) + 32*('A' <= c <= 'Z')) for c in s)
Explanation: Python short 1 line ASCII & string method solutions
Source: X of a Kind in a Deck of Cards
Description:
In a deck of cards, each card has an integer written on it.
Return
true
if and only if you can chooseX >= 2
such that it is possible to split the entire deck into 1 or more groups of cards, where:
- Each group has exactly
X
cards.- All the cards in each group have the same integer.
Answer:
return reduce(gcd, Counter(deck).values()) > 1
Source: Number of Different Integers in a String
Description:
You are given a string
word
that consists of digits and lowercase English letters.You will replace every non-digit character with a space. For example,
"a123bc34d8ef34"
will become" 123 34 8 34"
. Notice that you are left with some integers that are separated by at least one space:"123"
,"34"
,"8"
, and"34"
.Return the number of different integers after performing the replacement operations on
word
.Two integers are considered different if their decimal representations without any leading zeros are different.
Answer:
return len(set([int(''.join(g[1])) for g in groupby(word, lambda c: c.isnumeric()) if g[0]]))
Source: Check If N and Its Double Exist
Description:
Given an array
arr
of integers, check if there exists two integersN
andM
such thatN
is the double ofM
( i.e.N = 2 * M
).More formally check if there exists two indices
i
andj
such that :
i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
Answer:
return next((True for i in arr if i*2 in arr and i), False) if arr.count(0) < 2 else True
Source: Search Insert Position
Description:
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with
O(log n)
runtime complexity.
Answer:
return next((e[0]+1 for e in enumerate(pairwise(nums)) if target >= e[1][0] and target <= e[1][1]), len(nums)) if target > nums[0] else 0
Answer 2:
return bisect.bisect_left(nums, target)
Explanation: [Python] 2 Solutions: Oneliner and Classical BS explained
Source: Length of Last Word
Description:
Given a string
s
consisting of words and spaces, return the length of the last word in the string.A word is a maximal substring consisting of non-space characters only.
Answer:
return len(s.split()[-1])
Source: Number of Segments in a String
Description:
Given a string
s
, return the number of segments in the string.A segment is defined to be a contiguous sequence of non-space characters.
Answer:
return len(s.split())
Source: Power of Four
Description:
Given an integer
n
, returntrue
if it is a power of four. Otherwise, returnfalse
.An integer
n
is a power of four, if there exists an integerx
such thatn == 4x
.
Answer:
return n in (1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824)
Answer 2:
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
Explanation:
Source: Power of Three
Description:
Given an integer
n
, returntrue
if it is a power of three. Otherwise, returnfalse
.An integer
n
is a power of three, if there exists an integerx
such thatn == 3x
.Constraints:
-2**31 <= n <= 2**31 - 1
Answer:
return n in (1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467)
Answer 2:
return n > 0 and pow(3, 19) % n == 0
Explanation:
- With constraints:
-2**31 <= n <= 2**31 - 1
thenpow(3, 19)
is enough.
Source: Find Smallest Letter Greater Than Target
Description:
Given a characters array
letters
that is sorted in non-decreasing order and a charactertarget
, return the smallest character in the array that is larger thantarget
.Note that the letters wrap around.
- For example, if
target == 'z'
andletters == ['a', 'b']
, the answer is'a'
.
Answer:
return next((c for c in letters if c > target), letters[0])
Source: Subtract the Product and Sum of Digits of an Integer
Description:
Given an integer number
n
, return the difference between the product of its digits and the sum of its digits.
Answer:
return reduce(lambda a, b: a - b, reduce(lambda p, n: [p[0]*n, p[1] + n], [[1, 0]] + list(map(int, str(n)))))
Explanation:
-
Seed the
reduce()
with[1, 0]
which is[mul, add]
results corresponding. -
The second
reduce()
is to substract two values.
Answer 2
return eval('*'.join(str(n))) - eval('+'.join(str(n)))
Explanation:
Please upvote the author if you like it: Python one-liner using eval function (28ms, 14MB)
Source: Fibonacci Number
Description:
The Fibonacci numbers, commonly denoted
F(n)
form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from0
and1
. That is,F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.
Given
n
, calculateF(n)
.
Answer:
return reduce(lambda p, _: [p[1], p[0] + p[1]], range(n), [0, 1])[0]
Source: Pascal's Triangle
Description:
Given an integer
numRows
, return the first numRows of Pascal's triangle.In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Answer:
return accumulate([[1]] * numRows, lambda n, _: list(map(sum, pairwise([0] + n + [0]))))
Source: Pascal's Triangle II
Description:
Given an integer
rowIndex
, return therowIndexth
(0-indexed) row of the Pascal's triangle.In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Answer:
return list(accumulate([[1]] * (rowIndex + 1), lambda n, _: list(map(sum, pairwise([0] + n + [0])))))[-1]
Source: Find Triangular Sum of an Array
Description:
You are given a 0-indexed integer array
nums
, wherenums[i]
is a digit between0
and9
(inclusive).The triangular sum of
nums
is the value of the only element present innums
after the following process terminates:
- Let
nums
comprise ofn
elements. Ifn == 1
, end the process. Otherwise, create a new 0-indexed integer arraynewNums
of lengthn - 1
.- For each index
i
, where0 <= i < n - 1
, assign the value ofnewNums[i]
as(nums[i] + nums[i+1]) % 10
, where%
denotes modulo operator.- Replace the array
nums
withnewNums
.- Repeat the entire process starting from step 1.
Return the triangular sum of
nums
.
Answer:
return reduce(lambda p, n: list(map(lambda x: sum(x) % 10, pairwise(p))), [1] * (len(nums) - 1), nums)[0]
Source: Convert Sorted Array to Binary Search Tree
Description:
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Answer: Cre: congbk92
return TreeNode(nums[len(nums)//2], self.sortedArrayToBST(nums[:len(nums)//2]), self.sortedArrayToBST(nums[len(nums)//2+1:])) if len(nums) > 0 else None
Source: Invert Binary Tree
Description:
Given the root of a binary tree, invert the tree, and return its root.
Answer: Cre: congbk92
return TreeNode(root.val, self.invertTree(root.right), self.invertTree(root.left)) if root else None
Source: First Unique Character in a String
Description:
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Answer:
return s.find(next((s for s, c in Counter(s).items() if c == 1), "#"))
Source: Unique Morse Code Words
Description:
International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows:
'a' maps to ".-", 'b' maps to "-...", 'c' maps to "-.-.", and so on. For convenience, the full table for the 26 letters of the English alphabet is given below:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Given an array of strings words where each word can be written as a concatenation of the Morse code of each letter.
For example, "cab" can be written as
"-.-..--..."
, which is the concatenation of"-.-."
,".-"
, and"-..."
. We will call such a concatenation the transformation of a > word. Return the number of different transformations among all words we have.
Answer:
return len(set([reduce(lambda p, c: p + [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."][ord(c)-97], w, "") for w in words]))
Source: Ransom Note
Description:
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.
Answer:
return not Counter(ransomNote) - Counter(magazine)
Source: Longest Common Prefix
Description:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string
""
.
Answer:
return "".join(map(lambda n: n.pop(), takewhile(lambda p: len(p) == 1, map(set, zip(*strs)))))
Source: Is Subsequence
Description:
Given two strings
s
andt
, returntrue
ifs
is a subsequence oft
, orfalse
otherwise.A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e.,
"ace"
is a subsequence of"abcde"
while"aec"
is not).
Answer:
return reduce(lambda p, n: p[1:] if p and p[0] == n else p, t, s) == ''
Source: Find Center of Star Graph
Description:
There is an undirected star graph consisting of
n
nodes labeled from1
ton
. A star graph is a graph where there is one center node and exactlyn - 1
edges that connect the center node with every other node.You are given a 2D integer array
edges
where eachedges[i] = [ui, vi]
indicates that there is an edge between the nodesui
andvi
. Return the center of the given star graph.
Answer:
return set.intersection(*map(set, edges)).pop()
Source: Sorting the Sentence
Description:
A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.
A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.
- For example, the sentence
"This is a sentence"
can be shuffled as"sentence4 a3 is2 This1"
or"is2 sentence4 This1 a3"
.Given a shuffled sentence
s
containing no more than9
words, reconstruct and return the original sentence.
Answer:
return " ".join(map(lambda w: w[:-1], sorted(s.split(), key=lambda w: w[-1])))
Source: Root Equals Sum of Children
Description:
You are given the
root
of a binary tree that consists of exactly3
nodes: the root, its left child, and its right child.Return
true
if the value of the root is equal to the sum of the values of its two children, orfalse
otherwise.
Answer:
return root.val == sum((root.left.val, root.right.val))
Source: Partitioning Into Minimum Number Of Deci-Binary Numbers
Description:
A decimal number is called deci-binary if each of its digits is either
0
or1
without any leading zeros. For example,101
and1100
are deci-binary, while112
and3001
are not.Given a string
n
that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up ton
.
Answer:
return int(max(n))
Source: How Many Numbers Are Smaller Than the Current Number
Description:
Given the array
nums
, for eachnums[i]
find out how many numbers in the array are smaller than it. That is, for eachnums[i]
you have to count the number of validj's
such thatj != i
andnums[j] < nums[i]
.Return the answer in an array.
Answer:
return [len(list(filter(lambda p: p < n, nums))) for n in nums]
Source: Goal Parser Interpretation
Description:
You own a Goal Parser that can interpret a string
command
. Thecommand
consists of an alphabet of"G"
,"()"
and/or"(al)"
in some order. The Goal Parser will interpret"G"
as the string"G"
,"()"
as the string"o"
, and"(al)"
as the string"al"
. The interpreted strings are then concatenated in the original order.Given the string
command
, return the Goal Parser's interpretation ofcommand
.
Answer:
return command.replace("(al)", "al").replace("()", "o")
Source: Check If Two String Arrays are Equivalent
Description:
Given two string arrays
word1
andword2
, returntrue
if the two arrays represent the same string, andfalse
otherwise.A string is represented by an array if the array elements concatenated in order forms the string.
Example:
Input: word1 = ["a", "cb"], word2 = ["ab", "c"] Output: false
Example:
Input: word1 = ["abc", "d", "defg"], word2 = ["abcddefg"] Output: true
Answer:
return "".join(word1) == "".join(word2)
Source: Truncate Sentence
Description:
A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).
- For example,
"Hello World"
,"HELLO"
, and"hello world hello world"
are all sentences.You are given a sentence
s
and an integerk
. You want to truncates
such that it contains only the firstk
words. Returns
after truncating it.Example 1:
Input: s = "Hello how are you Contestant", k = 4 Output: "Hello how are you" Explanation: The words in s are ["Hello", "how" "are", "you", "Contestant"]. The first 4 words are ["Hello", "how", "are", "you"]. Hence, you should return "Hello how are you".
Answer:
return " ".join(s.split()[:k])
Source: Flipping an Image
Description:
Given an
n x n
binary matriximage
, flip the image horizontally, then invert it, and return the resulting image.To flip an image horizontally means that each row of the image is reversed.
- For example, flipping
[1,1,0]
horizontally results in[0,1,1]
.To invert an image means that each
0
is replaced by1
, and each1
is replaced by0
.
- For example, inverting
[0,1,1]
results in[1,0,0]
.Example 1:
Input: image = [[1,1,0],[1,0,1],[0,0,0]] Output: [[1,0,0],[0,1,0],[1,1,1]] Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]]. Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
Answer:
return map(lambda r: list(map(lambda n: n^1, r))[::-1], image)
Source: First Letter to Appear Twice
Description:
Given a string s consisting of lowercase English letters, return the first letter to appear twice.
Note:
A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
s
will contain at least one letter that appears twice.
Answer:
return next((c[1] for c in enumerate(s) if c[1] in s[:c[0]]), "")
Source: Make Array Zero by Subtracting Equal Amounts
Description:
You are given a non-negative integer array nums. In one operation, you must:
Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums. Subtract x from every positive element in nums. Return the minimum number of operations to make every element in nums equal to 0.
Example 1:
Input: nums = [1,5,0,3,5] Output: 3 Explanation: In the first operation, choose x = 1. Now, nums = [0,4,0,2,4]. In the second operation, choose x = 2. Now, nums = [0,2,0,0,2]. In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].
Answer:
return len(set(nums) - {0})
Source: Merge Similar Items
Description:
You are given two 2D integer arrays,
items1
anditems2
, representing two sets of items. Each arrayitems
has the following properties:
items[i] = [valuei, weighti]
wherevaluei
represents the value andweighti
represents the weight of theith
item.- The value of each item in
items
is unique.Return a 2D integer array
ret
whereret[i] = [valuei, weighti]
, withweighti
being the sum of weights of all items with valuevaluei
.Note:
ret
should be returned in ascending order by value.Example:
Input: items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]] Output: [[1,6],[3,9],[4,5]] Explanation: The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 5, total weight = 1 + 5 = 6. The item with value = 3 occurs in items1 with weight = 8 and in items2 with weight = 1, total weight = 8 + 1 = 9. The item with value = 4 occurs in items1 with weight = 5, total weight = 5.
Therefore, we return [[1,6],[3,9],[4,5]].
Answer:
return sorted((Counter(dict(items1)) + Counter(dict(items2))).items())
Source: Number of Arithmetic Triplets
Description:
You are given a 0-indexed, strictly increasing integer array
nums
and a positive integerdiff
. A triplet(i, j, k)
is an arithmetic triplet if the following conditions are met:
i < j < k
,nums[j] - nums[i] == diff
, andnums[k] - nums[j] == diff
.Return the number of unique arithmetic triplets.
Answer:
return len([i for i in nums if i + diff in nums and i + 2*diff in nums])
Source: Check Distances Between Same Letters
Description:
You are given a 0-indexed string
s
consisting of only lowercase English letters, where each letter ins
appears exactly twice. You are also given a 0-indexed integer arraydistance
of length26
.Each letter in the alphabet is numbered from
0
to25
(i.e.'a' -> 0
,'b' -> 1
,'c' -> 2
, ... ,'z' -> 25
).In a well-spaced string, the number of letters between the two occurrences of the
ith
letter isdistance[i]
. If theith
letter does not appear ins
, thendistance[i]
can be ignored.Return
true
ifs
is a well-spaced string, otherwise returnfalse
.Example 1:
Input: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: true Explanation:
- 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1.
- 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3.
- 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0. Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored. Return true because s is a well-spaced string.
Answer:
return all((len(s) - s[::-1].index(c) - s.index(c) - 2 == distance[ord(c)-ord("a")]) for c in set(s))
Explanation:
- Index of second appearance of character, as
index()
only returns the first appearance, calculate the index of second appearance by reverse the string:len(s) - s[::-1].index(c) - 1
- Index of first appearance of character:
s.index(c)
- Distance between appearances:
second - first - 1
=len(s) - s[::-1].index(c) - 1 - s.index(c) - 1
=len(s) - s[::-1].index(c) - s.index(c) - 2
- Compare with provided distance
distance[ord(c)-ord("a")]
- Do it with all characters c in s.
for c in set(s)
Source: Find Subarrays With Equal Sum
Description:
Given a 0-indexed integer array
nums
, determine whether there exist two subarrays of length2
with equal sum. Note that the two subarrays must begin at different indices.Return
true
if these subarrays exist, andfalse
otherwise.A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [4,2,4] Output: true Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.
Answer:
return Counter(map(sum, pairwise(nums))).most_common(1)[0][1] >= 2
Explanation:
itertools.pairwise(nums)
returns all subarrays with length 2.pairwise('ABCDEFG') --> AB BC CD DE EF FG
- Use
map(sum, pairwise(nums))
to sum all the subarrays. - Use
Counter.most_common()
to find if there are subarrays with samesum()
.
Source: Find the Difference
Description:
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
Example 1: Input: s = "abcd", t = "abcde" Output: "e" Explanation: 'e' is the letter that was added.
Answer:
return (Counter(t) - Counter(s)).most_common()[0][0]
Source: Add Digits
Description:
Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.
Example 1: Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.
Answer:
return (num - 1) % 9 + 1 if num else 0
Source: Toeplitz Matrix
Description:
Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.
Answer:
return all(r1[:-1] == r2[1:] for r1, r2 in zip(matrix, matrix[1:]))
Source: Add Binary
Description:
Given two binary strings a and b, return their sum as a binary string.
Answer:
return bin(int(a, 2) + int(b, 2))[2:]
Source: Make The String Great
Description:
Given a string s of lower and upper case English letters. A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:
0 <= i <= s.length - 2
s[i]
is a lower-case letter ands[i + 1]
is the same letter but in upper-case or vice-versa. To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good. Return the string after making it good. The answer is guaranteed to be unique under the given constraints. Notice that an empty string is also good.
Answer: Cre: congbk92
return reduce(lambda acc, x: acc[:-1] if len(acc) != 0 and acc[-1] != x and acc[-1].upper() == x.upper() else acc + x, s)
# A little modification
return reduce(lambda p, n: p[:-1] if p and p[-1] != n and p[-1].upper() == n.upper() else p + n, s)
Source: Remove All Adjacent Duplicates In String
Description:
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Answer:
return reduce(lambda p, n: p[:-1] if p and p[-1] == n else p + n, s)
Source: Find the Array Concatenation Value
Description:
You are given a 0-indexed integer array nums. The concatenation of two numbers is the number formed by concatenating their numerals. For example, the concatenation of 15, 49 is 1549. The concatenation value of nums is initially equal to 0. Perform this operation until nums becomes empty:
If there exists more than one number in nums, pick the first element and last element in nums respectively and add the value of their concatenation to the concatenation value of nums, then delete the first and last element from nums. If one element exists, add its value to the concatenation value of nums, then delete it. Return the concatenation value of the nums.
Answer:
return sum(map(lambda n: int("".join(map(str, n))) if n[0] else n[1], zip_longest(nums[:len(nums)//2], nums[len(nums)//2:][::-1])))
Source: Add to Array-Form of Integer
Description:
The array-form of an integer num is an array representing its digits in left to right order. For example, for num = 1321, the array form is [1,3,2,1]. Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.
Answer:
return [int(o) for o in str(int("".join([str(i) for i in num])) + k)]
Source: Count the Digits That Divide a Number
Description:
Given an integer num, return the number of digits in num that divide num. An integer val divides nums if nums % val == 0.
Answer:
return [num%int(n) for n in str(num)].count(0)
Source: Delete Columns to Make Sorted
Description:
You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid.
For example, strs = ["abc", "bce", "cae"] can be arranged as follows: abc bce cae You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.
Return the number of columns that you will delete.
Answer:
return sum(list(filter(lambda s: list(c) != sorted(c), zip(*strs))
Source: Find the Index of the First Occurrence in a String
Description:
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Answer:
return haystack.find(needle)