countAndSay(1) = "1"
countAndSay(n)
is the way you would "say" the digit string from countAndSay(n1)
, which is then converted into a different digit string.To determine how you "say&
]]>countAndSay(1) = "1"
countAndSay(n)
is the way you would "say" the digit string from countAndSay(n1)
, which is then converted into a different digit string.To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
For example, the saying and conversion for digit string "3322251"
:
Given a positive integer n
, return the n^{th}
term of the countandsay sequence.
Example 1:
Input: n = 1
Output: "1"
Explanation: This is the base case.
Example 2:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
Constraints:
1 <= n <= 30
class Solution:
def countAndSay(self, n: int) > str:
num = "1"
for i in range(n1):
new_num = ""
for x, y in groupby(num):
new_num += str(sum(1 for _ in y))+x
num = new_num
return num
]]>s
.Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e"
]]>Write a function that reverses a string. The input string is given as an array of characters s
.
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
Constraints:
1 <= s.length <= 10^{5}
s[i]
is a printable ascii character.Follow up: Do not allocate extra space for another array. You must do this by modifying the input array inplace with O(1)
extra memory.
class Solution:
def reverseString(self, s: List[str]) > None:
s.reverse()
"""
Do not return anything, modify s inplace instead.
"""
]]>n
, return true
if it is a power of four. Otherwise, return false
.An integer n
is a power of four, if there exists an integer x
such that n == 4^{x}
.
Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example
]]>n
, return true
if it is a power of four. Otherwise, return false
.An integer n
is a power of four, if there exists an integer x
such that n == 4^{x}
.
Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
Constraints:
2^{31} <= n <= 2^{31}  1
Follow up: Could you solve it without loops/recursion?
class Solution:
def isPowerOfFour(self, n: int) > bool:
if n <= 0:
return False
return (math.log10(n) / math.log10(4))%1 == 0
]]>n
, return true
if it is a power of three. Otherwise, return false
.An integer n
is a power of three, if there exists an integer x
such that n == 3^{x}
.
Example 1:
Input: n = 27
Output: true
Example 2:
Input: n = 0
Output: false
Example
]]>n
, return true
if it is a power of three. Otherwise, return false
.An integer n
is a power of three, if there exists an integer x
such that n == 3^{x}
.
Example 1:
Input: n = 27
Output: true
Example 2:
Input: n = 0
Output: false
Example 3:
Input: n = 9
Output: true
Example 4:
Input: n = 45
Output: false
Constraints:
2^{31} <= n <= 2^{31}  1
Follow up: Could you solve it without loops/recursion?
class Solution:
def isPowerOfThree(self, n: int) > bool:
if n <= 0:
return False
return (math.log10(n) / math.log10(3))%1 == 0
]]>You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
Given the secret number secret
and your friend's guess guess
, return the hint for your friend's guess.
The hint should be formatted as "xAyB"
, where x
is the number of bulls and y
is the number of cows. Note that both secret
and guess
may contain duplicate digits.
Example 1:
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '' and cows are underlined:
"1807"

"7810"
Example 2:
Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '' and cows are underlined:
"1123" "1123"
 or 
"0111" "0111"
Note that only one of the two unmatched 1s is counted as a cow since the nonbull digits can only be rearranged to allow one 1 to be a bull.
Example 3:
Input: secret = "1", guess = "0"
Output: "0A0B"
Example 4:
Input: secret = "1", guess = "1"
Output: "1A0B"
Constraints:
1 <= secret.length, guess.length <= 1000
secret.length == guess.length
secret
and guess
consist of digits only.class Solution:
def getHint(self, secret: str, guess: str) > str:
wrong_position = Counter(secret) & Counter(guess)
bulls = sum(1 for x,y in zip(secret,guess) if x==y)
cows = sum(wrong_position.values())bulls
return f"{bulls}A{cows}B"
]]>pattern
and a string s
, find if s
follows the same pattern.Here follow means a full match, such that there is a bijection between a letter in pattern
and a nonempty word in s
.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog&
]]>pattern
and a string s
, find if s
follows the same pattern.Here follow means a full match, such that there is a bijection between a letter in pattern
and a nonempty word in s
.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Example 4:
Input: pattern = "abba", s = "dog dog dog dog"
Output: false
Constraints:
1 <= pattern.length <= 300
pattern
contains only lowercase English letters.1 <= s.length <= 3000
s
contains only lowercase English letters and spaces ' '
.s
does not contain any leading or trailing spaces.s
are separated by a single space.class Solution:
def wordPattern(self, pattern: str, s: str) > bool:
def recreate(s):
index = 0
word_map = {}
for i in s:
x = word_map.get(i,1)
if x!=1:
yield x
else:
yield index
word_map[i] = index
index+=1
s = s.split()
if len(s) != len(pattern):
return False
return all(x==y for x,y in zip(recreate(pattern),recreate(s)))
]]>push
, peek
, pop
, and empty
).Implement the MyQueue
class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes thepush
, peek
, pop
, and empty
).Implement the MyQueue
class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes the element from the front of the queue and returns it.int peek()
Returns the element at the front of the queue.boolean empty()
Returns true
if the queue is empty, false
otherwise.Notes:
push to top
, peek/pop from top
, size
, and is empty
operations are valid.Followup: Can you implement the queue such that each operation is amortized O(1)
time complexity? In other words, performing n
operations will take overall O(n)
time even if one of those operations may take longer.
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Constraints:
1 <= x <= 9
100
calls will be made to push
, pop
, peek
, and empty
.pop
and peek
are valid.class MyQueue:
def __init__(self):
self.queue = deque()
def push(self, x: int) > None:
self.queue.append(x)
def pop(self) > int:
return self.queue.popleft()
def peek(self) > int:
return self.queue[0]
def empty(self) > bool:
return False if self.queue else True
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
]]>push
, top
, pop
, and empty
).Implement the MyStack
class:
void push(int x)
Pushes element x to the top of the stack.int pop()
Removes thepush
, top
, pop
, and empty
).Implement the MyStack
class:
void push(int x)
Pushes element x to the top of the stack.int pop()
Removes the element on the top of the stack and returns it.int top()
Returns the element on the top of the stack.boolean empty()
Returns true
if the stack is empty, false
otherwise.Notes:
push to back
, peek/pop from front
, size
, and is empty
operations are valid.Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
Constraints:
1 <= x <= 9
100
calls will be made to push
, pop
, top
, and empty
.pop
and top
are valid.Followup: Can you implement the stack such that each operation is amortized O(1)
time complexity? In other words, performing n
operations will take overall O(n)
time even if one of those operations may take longer. You can use more than two queues.
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = deque()
def push(self, x: int) > None:
"""
Push element x onto stack.
"""
self.stack.append(x)
def pop(self) > int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.stack.pop()
def top(self) > int:
"""
Get the top element.
"""
return self.stack[1]
def empty(self) > bool:
"""
Returns whether the stack is empty.
"""
return False if self.stack else True
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
]]>nums
and an integer k
, return true
if there are two distinct indices i
and j
in the array such that nums[i] == nums[j]
and abs(i  j) <= k
.Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
]]>nums
and an integer k
, return true
if there are two distinct indices i
and j
in the array such that nums[i] == nums[j]
and abs(i  j) <= k
.Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Constraints:
1 <= nums.length <= 10^{5}
10^{9} <= nums[i] <= 10^{9}
0 <= k <= 10^{5}
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) > bool:
seen = {}
for index,val in enumerate(nums):
if seen.get(val,1)!=1 and indexseen[val] <= k:
return True
else:
seen[val] = index
return False
]]>nums
and a positive integer target
, return the minimal length of a contiguous subarray [nums_{l}, nums_{l+1}, ..., nums_{r1}, nums_{r}]
of which the sum is greater than or equal to target
. If there is no such subarray, return 0
instead.Example
]]>nums
and a positive integer target
, return the minimal length of a contiguous subarray [nums_{l}, nums_{l+1}, ..., nums_{r1}, nums_{r}]
of which the sum is greater than or equal to target
. If there is no such subarray, return 0
instead.Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 10^{9}
1 <= nums.length <= 10^{5}
1 <= nums[i] <= 10^{5}
Follow up: If you have figured out the O(n)
solution, try coding another solution of which the time complexity is O(n log(n))
.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) > int:
l = 0
r = 0
s = 0
m = float('inf')
while r<len(nums):
while s<target and r<len(nums):
s += nums[r]
r +=1
while s>=target and l<len(nums):
if s >= target:
m = min(m,rl)
s = nums[l]
l += 1
if m == float('inf'):
return 0
return m
]]>n
is happy.A happy number is a number defined by the following process:
n
is happy.A happy number is a number defined by the following process:
Return true
if n
is a happy number, and false
if not.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Constraints:
1 <= n <= 2^{31}  1
class Solution:
def isHappy(self, n: int) > bool:
def digitSum(n):
return sum(map(lambda x:x*x, map(int,list(str(n)))))
seen = set()
while not n in seen:
seen.add(n)
n = digitSum(n)
if n == 1:
return True
return False
]]>Implement the MinStack
class:
MinStack()
initializes the stack object.void push(val)
pushes the element val
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets theImplement the MinStack
class:
MinStack()
initializes the stack object.void push(val)
pushes the element val
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[2],[0],[3],[],[],[],[]]
Output
[null,null,null,null,3,null,0,2]
Explanation
MinStack minStack = new MinStack();
minStack.push(2);
minStack.push(0);
minStack.push(3);
minStack.getMin(); // return 3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return 2
Constraints:
2^{31} <= val <= 2^{31}  1
pop
, top
and getMin
operations will always be called on nonempty stacks.3 * 10^{4}
calls will be made to push
, pop
, top
, and getMin
.class Node:
def __init__(self, value):
self.value = value
self.min = None
class MinStack:
def __init__(self):
self.stack = []
self.min = float('inf')
def push(self, x: int) > None:
node = Node(x)
node.min = self.min
self.stack.append(node)
self.min = min(self.min,x)
def pop(self) > None:
node = self.stack.pop()
self.min = node.min
def top(self) > int:
return self.stack[1].value
def getMin(self) > int:
return self.min
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
]]>nums
, every element appears twice except for one. Find that single one.Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,
]]>nums
, every element appears twice except for one. Find that single one.Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
Constraints:
1 <= nums.length <= 3 * 10^{4}
3 * 10^{4} <= nums[i] <= 3 * 10^{4}
class Solution:
def singleNumber(self, nums: List[int]) > int:
return sum(set(nums))*2sum(nums)
]]>prices
where prices[i]
is the price of a given stock on the i^{th}
day.Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times)
]]>prices
where prices[i]
is the price of a given stock on the i^{th}
day.Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 51 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 63 = 3.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 51 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e., max profit = 0.
Constraints:
1 <= prices.length <= 3 * 10^{4}
0 <= prices[i] <= 10^{4}
class Solution:
def maxProfit(self, prices: List[int]) > int:
down = prices[0]
i = 0
profit = 0
while True:
while i<len(prices) and prices[i]>down:
profit += prices[i]down
down = prices[i]
i+=1
else:
if i==len(prices):
break
down = prices[i]
i += 1
return profit
]]>prices
where prices[i]
is the price of a given stock on the i^{th}
day.You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the
]]>prices
where prices[i]
is the price of a given stock on the i^{th}
day.You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0
.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 61 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 10^{5}
0 <= prices[i] <= 10^{4}
class Solution:
def maxProfit(self, prices: List[int]) > int:
min_price = prices[0]
max_profit = 0
for price in prices:
max_profit = max(price  min_price,max_profit)
min_price = min(price,min_price)
return max_profit
]]>