LeetCode Submissions 2
LeetCode Submissions 2
Download PDF Follow @TheShubham99 on GitHub Star on GitHub View Source Code
Description
Given the root of a binary tree, return all root-to-leaf paths in any order.
Example 1:
Example 2:
Constraints:
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
path = []
ans = []
def func(root):
if not root:
return
path.append(str(root.val))
if not root.left and not root.right:
ans.append("->".join(path))
else:
func(root.left)
func(root.right)
path.pop()
func(root)
return ans
181 Employees Earning More Than Their Managers (link)
Description
Table: Employee
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| id | int |
| name | varchar |
| salary | int |
| managerId | int |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table indicates the ID of an employee, their name, salary, and the ID of their manager.
Write a solution to find the employees who earn more than their managers.
Example 1:
Input:
Employee table:
+----+-------+--------+-----------+
| id | name | salary | managerId |
+----+-------+--------+-----------+
| 1 | Joe | 70000 | 3 |
| 2 | Henry | 80000 | 4 |
| 3 | Sam | 60000 | Null |
| 4 | Max | 90000 | Null |
+----+-------+--------+-----------+
Output:
+----------+
| Employee |
+----------+
| Joe |
+----------+
Explanation: Joe is the only employee who earns more than his manager.
import pandas as pd
return result_df
2704 Maximum Difference by Remapping a Digit (link)
Description
You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.
Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.
Notes:
When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of d1 in num with d2.
Bob can remap a digit to itself, in which case num does not change.
Bob can remap different digits for obtaining minimum and maximum values respectively.
The resulting number after remapping can contain leading zeroes.
Example 1:
Example 2:
Input: num = 90
Output: 99
Explanation:
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by t
Thus, we return 99.
Constraints:
class Solution:
def minMaxDifference(self, num: int) -> int:
s = str(num)
ch = next((c for c in s if c!='9'), None)
mx = ''.join(('9' if c==ch else c for c in s) if ch else s)
ch0 = s[0]
mn = ''.join('0' if c==ch0 else c for c in s)
return int(mx) - int(mn)
146 LRU Cache (link)
Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the
number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
Description
Given a circular array nums, find the maximum absolute difference between adjacent elements.
Note: In a circular array, the first and last elements are adjacent.
Example 1:
Output: 3
Explanation:
Because nums is circular, nums[0] and nums[2] are adjacent. They have the maximum absolute difference of |4 - 1| = 3.
Example 2:
Output: 5
Explanation:
The adjacent elements nums[0] and nums[1] have the maximum absolute difference of |-5 - (-10)| = 5.
Constraints:
class Solution:
def maxAdjacentDistance(self, nums: List[int]) -> int:
N = len(nums)
nums.append(nums[0])
return max(abs(nums[i] - nums[i+1]) for i in range(N))
303 Range Sum Query - Immutable (link)
Description
Given an integer array nums, handle multiple queries of the following type:
1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e.
nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
class NumArray:
Description
You are given a string s consisting of lowercase English letters.
Your task is to find the maximum difference diff = freq(a1) - freq(a2) between the frequency of characters a1 and a2 in the string
such that:
Example 1:
Input: s = "aaaaabbc"
Output: 3
Explanation:
The character 'a' has an odd frequency of 5, and 'b' has an even frequency of 2.
The maximum difference is 5 - 2 = 3.
Example 2:
Input: s = "abcabcab"
Output: 1
Explanation:
The character 'a' has an odd frequency of 3, and 'c' has an even frequency of 2.
The maximum difference is 3 - 2 = 1.
Constraints:
class Solution {
public int maxDifference(String s) {
int odd = 0;
int even = s.length();
for(int i: freq){
if((i & 1) == 1){
odd = Math.max(odd, i);
}else if(i != 0){
even = Math.min(even, i);
}
}
return odd - even;
}
}
386 Lexicographical Numbers (link)
Description
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2
Output: [1,2]
Constraints:
class Solution:
def lexicalOrder(self, n: int) -> list[int]:
res = []
curr = 1
for _ in range(n):
res.append(curr)
if curr * 10 <= n:
curr *= 10
else:
# backtrack
if curr >= n:
curr //= 10
curr += 1
while curr % 10 == 0:
curr //= 10
return res
171 Excel Sheet Column Number (link)
Description
Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
ans=0
n=len(columnTitle)
for x in columnTitle:
ans=ans+(ord(x)-ord("A")+1)*26**(n-1)
n-=1
return ans
# # 26*26^1+25*26^0=701
# # AAA
# return 1*26**3+1*26**2+1*26**1+1*26**0
1058 Lexicographically Smallest Equivalent String (link)
Description
You are given two strings of the same length s1 and s2 and a string baseStr.
For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.
For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr =
"eed", and "aab" is the lexicographically smallest equivalent string of baseStr.
Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def dfs(self, node, adj, visited, group):
visited[node] = True
group.append(node)
for nei in adj[node]:
if not visited[nei]:
self.dfs(nei, adj, visited, group)
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
adj = [[] for _ in range(26)]
visited = [False] * 26
rep = [None] * 26
Description
You are given a string word, and an integer numFriends.
Alice is organizing a game for her numFriends friends. There are multiple rounds in the game, where in each round:
word is split into numFriends non-empty strings, such that no previous round has had the exact same split.
All the split words are put into a box.
Find the lexicographically largest string from the box after all the rounds are finished.
Example 1:
Output: "dbc"
Explanation:
Example 2:
Output: "g"
Explanation:
The only possible split is: "g", "g", "g", and "g".
Constraints:
class Solution:
def lastSubstring(self, s: str) -> str:
i, j, n = 0, 1, len(s)
while j < n:
k = 0
while j + k < n and s[i + k] == s[j + k]:
k += 1
if j + k < n and s[i + k] < s[j + k]:
i, j = j, max(j + 1, i + k + 1)
else:
j = j + k + 1
return s[i:]
Description
The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.
For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.
Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:
Return the minimized maximum pair sum after optimally pairing up the elements.
Example 1:
Example 2:
Constraints:
n == nums.length
2 <= n <= 105
n is even.
1 <= nums[i] <= 105
class Solution:
def minPairSum(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
maxx = 0
l, r = 0, n-1
return maxx
2271 Rearrange Array Elements by Sign (link)
Description
You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.
You should return the array of nums such that the the array follows the given conditions:
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.
Example 1:
Example 2:
Constraints:
class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
pre, post = 0, 1
for i in range(n):
if nums[i] > 0:
ans[pre] = nums[i]
pre += 2
else:
ans[post] = nums[i]
post += 2
return ans
2265 Partition Array According to Given Pivot (link)
Description
You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:
Every element less than pivot appears before every element greater than pivot.
Every element equal to pivot appears in between the elements less than and greater than pivot.
The relative order of the elements less than pivot and the elements greater than pivot is maintained.
More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth
element. If i < j and both elements are smaller (or larger) than pivot, then pi < pj.
Example 1:
Example 2:
Constraints:
class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
left = []
right = []
mid = []
for i in nums:
if i < pivot:
left.append(i)
elif i > pivot:
right.append(i)
else:
mid.append(i)
Description
An integer n is strictly palindromic if, for every base b between 2 and n - 2 (inclusive), the string representation of the integer n in
base b is palindromic.
Example 1:
Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.
Example 2:
Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.
Constraints:
class Solution:
def isStrictlyPalindromic(self, n: int) -> bool:
Description
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8,
and -2.7335 would be truncated to -2.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 −
1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231,
then return -231.
Example 1:
Example 2:
Constraints:
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
# Handle overflow
if dividend == -2**31 and divisor == -1:
return 2**31 - 1
a, b = abs(dividend), abs(divisor)
result = 0
while a >= b:
temp = b
multiple = 1
a -= temp
result += multiple
# Apply sign
if (dividend > 0) != (divisor > 0):
result = -result
return result
175 Combine Two Tables (link)
Description
Table: Person
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| personId | int |
| lastName | varchar |
| firstName | varchar |
+-------------+---------+
personId is the primary key (column with unique values) for this table.
This table contains information about the ID of some persons and their first and last names.
Table: Address
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| addressId | int |
| personId | int |
| city | varchar |
| state | varchar |
+-------------+---------+
addressId is the primary key (column with unique values) for this table.
Each row of this table contains information about the city and state of one person with ID = PersonId.
Write a solution to report the first name, last name, city, and state of each person in the Person table. If the address of a personId is not
present in the Address table, report null instead.
Example 1:
Input:
Person table:
+----------+----------+-----------+
| personId | lastName | firstName |
+----------+----------+-----------+
| 1 | Wang | Allen |
| 2 | Alice | Bob |
+----------+----------+-----------+
Address table:
+-----------+----------+---------------+------------+
| addressId | personId | city | state |
+-----------+----------+---------------+------------+
| 1 | 2 | New York City | New York |
| 2 | 3 | Leetcode | California |
+-----------+----------+---------------+------------+
Output:
+-----------+----------+---------------+----------+
| firstName | lastName | city | state |
+-----------+----------+---------------+----------+
| Allen | Wang | Null | Null |
| Bob | Alice | New York City | New York |
+-----------+----------+---------------+----------+
Explanation:
There is no address in the address table for the personId = 1 so we return null in their city and state.
addressId = 1 contains information about the address of personId = 2.
Description
You are given positive integers n and m.
num1: The sum of all integers in the range [1, n] (both inclusive) that are not divisible by m.
num2: The sum of all integers in the range [1, n] (both inclusive) that are divisible by m.
Example 1:
Input: n = 10, m = 3
Output: 19
Explanation: In the given example:
- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18.
We return 37 - 18 = 19 as the answer.
Example 2:
Input: n = 5, m = 6
Output: 15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.
We return 15 - 0 = 15 as the answer.
Example 3:
Input: n = 5, m = 1
Output: -15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.
- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.
We return 0 - 15 = -15 as the answer.
Constraints:
class Solution:
def differenceOfSums(self, n: int, m: int) -> int:
num1 = 0
num2 = 0
Description
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Example 2:
Example 3:
Constraints:
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is
more subtle.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
total = 0
for n in nums:
if total < 0:
total = 0
total += n
res = max(res, total)
return res
92 Reverse Linked List II (link)
Description
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position
left to position right, and return the reversed list.
Example 1:
Example 2:
Constraints:
dummy = ListNode(0)
dummy.next = head
prev = dummy
return dummy.next
148 Sort List (link)
Description
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Example 2:
Example 3:
Input: head = []
Output: []
Constraints:
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return dummyNode.next
def findMiddle(head):
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def sortLL(head):
if not head or not head.next:
return head
middle = findMiddle(head)
right = middle.next
middle.next = None
left = sortLL(head)
right = sortLL(right)
return sortLL(head)
226 Invert Binary Tree (link)
Description
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Example 2:
Example 3:
Input: root = []
Output: []
Constraints:
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return root
168 Excel Sheet Column Title (link)
Description
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example 1:
Input: columnNumber = 1
Output: "A"
Example 2:
Input: columnNumber = 28
Output: "AB"
Example 3:
Constraints:
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
res = ""
return res
73 Set Matrix Zeroes (link)
Description
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
Example 1:
Example 2:
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
Follow up:
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n, m=len(matrix), len(matrix[0])
col0, row0=0, 0
for i, row in enumerate(matrix):
for j, x in enumerate(row):
if x==0:
row0|=(1<<i)
col0|=(1<<j)
for i in range(n):
if (row0>>i) &1:
for j in range(m):
matrix[i][j]=0
for j in range(m):
if (col0>>j) &1:
for i in range(n):
matrix[i][j]=0
34 Find First and Last Position of Element in Sorted Array (link)
Description
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
return idx
Description
You are given a 0-indexed integer array nums of size 3 which can form the sides of a triangle.
Return a string representing the type of triangle that can be formed or "none" if it cannot form a triangle.
Example 1:
Example 2:
Constraints:
nums.length == 3
1 <= nums[i] <= 100
class Solution:
def triangleType(self, nums: List[int]) -> str:
if not (nums[0] + nums[1] > nums[2] and
nums[0] + nums[2] > nums[1] and
nums[1] + nums[2] > nums[0]):
return "none"
return "scalene"
2061 Painting a Grid With Three Different Colors (link)
Description
You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or
blue. All cells must be painted.
Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large,
return it modulo 109 + 7.
Example 1:
Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.
Example 2:
Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.
Example 3:
Input: m = 5, n = 5
Output: 580986
Constraints:
1 <= m <= 5
1 <= n <= 1000
class Solution:
def colorTheGrid(self, m: int, n: int) -> int:
g = cache(lambda prev:(gg:=lambda i,cur:i==m and [cur] or sum((gg(i+1,cur+cand)
for cand in 'rgb' if prev[i]!=cand and (i==0 or cur[-1]!=cand)),[]))(0,''))
Description
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with
the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.
Example 1:
Example 2:
Constraints:
n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, mid = 0;
int high = nums.size() - 1;
int temp;
low++;
mid++;
}
else if(nums[mid] == 1){
mid++;
}
else{
temp = nums[mid];
nums[mid] = nums[high];
nums[high] = temp;
high--;
}
}
}
};
39 Combination Sum (link)
Description
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where
the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at
least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the
given input.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
for c in candidates:
for s in range(c, target+1):
for combo in dp[s-c]:
dp[s].append(combo + [c])
return dp[target]
3143 Longest Unequal Adjacent Groups Subsequence I (link)
Description
You are given a string array words and a binary array groups both of length n.
A subsequence of words is alternating if for any two consecutive strings in the sequence, their corresponding elements at the same
indices in groups are different (that is, there cannot be consecutive 0 or 1).
Return the selected subsequence. If there are multiple answers, return any of them.
Example 1:
Output: ["e","b"]
Explanation: A subsequence that can be selected is ["e","b"] because groups[0] != groups[2]. Another subsequence that can be selected is
["a","b"] because groups[1] != groups[2]. It can be demonstrated that the length of the longest subsequence of indices that satisfies the
condition is 2.
Example 2:
Output: ["a","b","c"]
Explanation: A subsequence that can be selected is ["a","b","c"] because groups[0] != groups[1] and groups[1] != groups[2]. Another
subsequence that can be selected is ["a","b","d"] because groups[0] != groups[1] and groups[1] != groups[3]. It can be shown that the
length of the longest subsequence of indices that satisfies the condition is 3.
Constraints:
class Solution:
def getLongestSubsequence(self, words, groups):
result = []
last = -1
for i in range(len(words)):
if groups[i] != last:
result.append(words[i])
last = groups[i]
return result
1072 Next Greater Node In Linked List (link)
Description
You are given the head of a linked list with n nodes.
For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to
it and has a strictly larger value than it.
Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does
not have a next greater node, set answer[i] = 0.
Example 1:
Example 2:
Constraints:
Description
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
Example 2:
Output: [[""]]
Example 3:
Output: [["a"]]
Constraints:
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = defaultdict(list)
for s in strs:
key = "".join(sorted(s))
ans[key].append(s)
return list(ans.values())
1421 Find Numbers with Even Number of Digits (link)
Description
Given an array nums of integers, return how many of them contain an even number of digits.
Example 1:
Example 2:
Constraints:
class Solution:
def findNumbers(self, nums: List[int]) -> int:
count = 0
for i in nums:
if (len(str(i)) & 1 == 0):
count += 1
return count
2215 Finding 3-Digit Even Numbers (link)
Description
You are given an integer array digits, where each element is a digit. The array may contain duplicates.
You need to find all the unique integers that follow the given requirements:
The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.
For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def findEvenNumbers(self, digits):
from collections import Counter
freq = Counter(digits)
res = []
for num in range(100, 1000, 2):
parts = [num // 100, (num // 10) % 10, num % 10]
count = Counter(parts)
if all(freq[d] >= count[d] for d in count):
res.append(num)
return res
897 Prime Palindrome (link)
Description
Given an integer n, return the smallest prime palindrome greater than or equal to n.
An integer is prime if it has exactly two divisors: 1 and itself. Note that 1 is not a prime number.
An integer is a palindrome if it reads the same from left to right as it does from right to left.
The test cases are generated so that the answer always exists and is in the range [2, 2 * 108].
Example 1:
Input: n = 6
Output: 7
Example 2:
Input: n = 8
Output: 11
Example 3:
Input: n = 13
Output: 101
Constraints:
class Solution:
def primePalindrome(self, n: int) -> int:
def is_palindrome(x: int) -> bool:
return str(x) == str(x)[::-1]
while True:
if is_palindrome(n) and is_prime(n):
return n
n += 1
Description
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:
Example 2:
Constraints:
dummy = ListNode(0)
dummy.next = head
prev = dummy
while head:
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
prev.next = head.next
else:
prev = prev.next
head = head.next
return dummy.next
24 Swap Nodes in Pairs (link)
Description
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the
list's nodes (i.e., only nodes themselves may be changed.)
Example 1:
Output: [2,1,4,3]
Explanation:
Example 2:
Input: head = []
Output: []
Example 3:
Output: [1]
Example 4:
Output: [2,1,3]
Constraints:
first = head
second = head.next
while first and second:
first.val, second.val = second.val, first.val
first = second.next
second = first.next if first else None
return head
23 Merge k Sorted Lists (link)
Description
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Example 2:
Input: lists = []
Output: []
Example 3:
Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
dummy = ListNode(0)
curr = dummy
return dummy.next
2236 Maximum Twin Sum of a Linked List (link)
Description
In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i
<= (n / 2) - 1.
For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for
n = 4.
The twin sum is defined as the sum of a node and its twin.
Given the head of a linked list with even length, return the maximum twin sum of the linked list.
Example 1:
Example 2:
Example 3:
Constraints:
The number of nodes in the list is an even integer in the range [2, 105].
1 <= Node.val <= 105
slowpntr = head
fastpntr = head
while fastpntr:
slowpntr = slowpntr.next
fastpntr = fastpntr.next.next
prev = None
curr = slowpntr
foll = slowpntr
while curr:
foll = curr.next
curr.next = prev
prev = curr
curr = foll
curr = head
maxx = float("-inf")
while curr and prev:
summ = curr.val + prev.val
maxx = max(summ, maxx)
curr = curr.next
prev = prev.next
return maxx
948 Sort an Array (link)
Description
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space
complexity possible.
Example 1:
Example 2:
Constraints:
return new_arr
}
return arr
}
2743 Debounce (link)
Description
Given a function fn and a time in milliseconds t, return a debounced version of that function.
A debounced function is a function whose execution is delayed by t milliseconds and whose execution is cancelled if it is called again
within that window of time. The debounced function should also receive the passed parameters.
For example, let's say t = 50ms, and the function was called at 30ms, 60ms, and 100ms.
The first 2 function calls would be cancelled, and the 3rd function call would be executed at 150ms.
If instead t = 35ms, The 1st call would be cancelled, the 2nd would be executed at 95ms, and the 3rd would be executed at 135ms.
The above diagram shows how debounce will transform events. Each rectangle represents 100ms and the debounce time is 400ms.
Each color represents a different set of inputs.
Example 1:
Input:
t = 50
calls = [
{"t": 50, inputs: [1]},
{"t": 75, inputs: [2]}
]
Output: [{"t": 125, inputs: [2]}]
Explanation:
let start = Date.now();
function log(...inputs) {
console.log([Date.now() - start, inputs ])
}
const dlog = debounce(log, 50);
setTimeout(() => dlog(1), 50);
setTimeout(() => dlog(2), 75);
The 1st call is cancelled by the 2nd call because the 2nd call occurred before 100ms
The 2nd call is delayed by 50ms and executed at 125ms. The inputs were (2).
Example 2:
Input:
t = 20
calls = [
{"t": 50, inputs: [1]},
{"t": 100, inputs: [2]}
]
Output: [{"t": 70, inputs: [1]}, {"t": 120, inputs: [2]}]
Explanation:
The 1st call is delayed until 70ms. The inputs were (1).
The 2nd call is delayed until 120ms. The inputs were (2).
Example 3:
Input:
t = 150
calls = [
{"t": 50, inputs: [1, 2]},
{"t": 300, inputs: [3, 4]},
{"t": 300, inputs: [5, 6]}
]
Output: [{"t": 200, inputs: [1,2]}, {"t": 450, inputs: [5, 6]}]
Explanation:
The 1st call is delayed by 150ms and ran at 200ms. The inputs were (1, 2).
The 2nd call is cancelled by the 3rd call
The 3rd call is delayed by 150ms and ran at 450ms. The inputs were (5, 6).
Constraints:
/**
* @param {Function} fn
* @param {number} t milliseconds
* @return {Function}
*/
var debounce = function(fn, t) {
let timeoutId;
return function(...args) {
clearTimeout(timeoutId);
timeoutId = setTimeout(() => {
fn(...args);
}, t);
}
};
/**
* const log = debounce(console.log, 100);
* log('Hello'); // cancelled
* log('Hello'); // cancelled
* log('Hello'); // Logged at t=100ms
*/
2048 Build Array from Permutation (link)
Description
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <=
i < nums.length and return it.
Example 1:
Example 2:
Constraints:
Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0]*n
for i in range(n):
res[i] = nums[nums[i]]
return res
102 Binary Tree Level Order Traversal (link)
Description
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Example 1:
Example 2:
Example 3:
Input: root = []
Output: []
Constraints:
Description
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in
nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example 1:
Example 2:
Constraints:
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack = []
next_greater = {}
for n in nums2:
while stack and stack[-1] < n:
next_greater[stack.pop()] = n
stack.append(n)
for n in stack:
next_greater[n] = -1
Description
You are given the head of a linked list.
Remove every node which has a node with a greater value anywhere to the right side of it.
Example 1:
Example 2:
Constraints:
The number of the nodes in the given list is in the range [1, 105].
1 <= Node.val <= 105
stack = []
curr = head
while curr:
while stack and stack[-1].val < curr.val:
stack.pop()
else:
stack.append(curr)
curr = curr.next
Description
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list
holds the binary representation of a number.
Example 1:
Example 2:
Constraints:
curr = head
res = ""
while curr:
res += str(curr.val)
curr = curr.next
def binary_to_decimal(binary_str):
decimal_value = 0
power = 0
for digit in reversed(binary_str):
if digit == '1':
decimal_value += 2**power
power += 1
return decimal_value
return binary_to_decimal(res)
868 Push Dominoes (link)
Description
There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the
dominoes either to the left or to the right.
After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the
right push their adjacent dominoes standing on the right.
When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.
For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen
domino.
You are given a string dominoes representing the initial state where:
dominoes[i] = 'L', if the ith domino has been pushed to the left,
dominoes[i] = 'R', if the ith domino has been pushed to the right, and
dominoes[i] = '.', if the ith domino has not been pushed.
Example 1:
Example 2:
Constraints:
n == dominoes.length
1 <= n <= 105
dominoes[i] is either 'L', 'R', or '.'.
class Solution:
def pushDominoes(self, dominoes: str) -> str:
n=len(dominoes)
L=[0]*n
F=0
for i in range(n-1, -1, -1):
c=dominoes[i]
if c=='L': F=n
elif c=='R': F=0
else: F-=(F>0)
L[i]=F
F=0
D=list(dominoes)
for i, c in enumerate(D):
if c=='L': F=0
elif c=='R': F=n
else:
F-=(F>0)
if F>L[i]: D[i]='R'
elif F<L[i]: D[i]='L'
else: D[i]='.'
return "".join(D)
17 Letter Combinations of a Phone Number (link)
Description
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the
answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
def dfs(i: int):
if i >= len(digits):
ans.append("".join(t))
return
for c in d[int(digits[i]) - 2]:
t.append(c)
dfs(i + 1)
t.pop()
if not digits:
return []
d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
ans = []
t = []
dfs(0)
return ans
1993 Sum of All Subset XOR Totals (link)
Description
The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.
For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.
Given an array nums, return the sum of all XOR totals for every subset of nums.
Note: Subsets with the same elements should be counted multiple times.
An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def subsetXORSum(self, nums):
total = 0
for num in nums:
total |= num # Step 1: Compute bitwise OR of all numbers
return total * (1 << (len(nums) - 1)) # Step 2: Multiply by 2^(n-1)
2231 Find First Palindromic String in the Array (link)
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 "".
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def firstPalindrome(self, words: List[str]) -> str:
for i in words:
if i==i[::-1]:
return i
return ""
1742 Widest Vertical Area Between Two Points Containing No Points
(link)
Description
Given n points on a 2D plane where points[i] = [xi, yi], Return the widest vertical area between two points such that no points are
inside the area.
A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one
with the maximum width.
Note that points on the edge of a vertical area are not considered included in the area.
Example 1:
Example 2:
Constraints:
n == points.length
2 <= n <= 105
points[i].length == 2
0 <= xi, yi <= 109
class Solution:
def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[0])
max_width = 0
return max_width
2610 Closest Prime Numbers in Range (link)
Description
Given two positive integers left and right, find the two integers num1 and num2 such that:
Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the
smallest num1 value. If no such numbers exist, return [-1, -1].
Example 1:
Example 2:
Constraints:
class Solution {
public int[] closestPrimes(int left, int right) {
boolean[] sieve = new boolean[right + 1];
Arrays.fill(sieve, true);
sieve[0] = sieve[1] = false;
if (primes.size() < 2) {
return new int[]{-1, -1};
}
return result;
}
}
905 Length of Longest Fibonacci Subsequence (link)
Description
A sequence x1, x2, ..., xn is Fibonacci-like if:
n >= 3
xi + xi+1 == xi+2 for all i + 2 <= n
Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like
subsequence of arr. If one does not exist, return 0.
A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without
changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].
Example 1:
Example 2:
Constraints:
class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
n = len(arr)
max_len = 0
# dp[prev][curr] stores length of Fibonacci sequence ending at indexes prev,curr
dp = [[0] * n for _ in range(n)]
# Fill dp array
for curr in range(n):
for prev in range(curr):
# Find if there exists a previous number to form Fibonacci sequence
diff = arr[curr] - arr[prev]
prev_idx = val_to_idx.get(diff, -1)
Description
Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not
appear in nums. If there are multiple answers, you may return any of them.
Example 1:
Example 2:
Example 3:
Constraints:
n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] is either '0' or '1'.
All the strings of nums are unique.
class Solution:
def findDifferentBinaryString(self, nums):
result = []
for i in range(len(nums)):
if nums[i][i] == '0':
result.append('1')
else:
result.append('0')
return ''.join(result)
1516 The k-th Lexicographical String of All Happy Strings of Length n
(link)
Description
A happy string is a string that:
For example, strings "abc", "ac", "b" and "abcbabcbcb" are all happy strings and strings "aa", "baa" and "ababbc" are not happy
strings.
Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.
Return the kth string of this list or return an empty string if there are less than k happy strings of length n.
Example 1:
Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".
Example 2:
Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.
Example 3:
Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac",
Constraints:
1 <= n <= 10
1 <= k <= 100
class Solution:
def getHappyString(self, n: int, k: int) -> str:
def dfs(prefix, n, k):
if n == 0:
return prefix
for c in 'abc':
if prefix and c == prefix[-1]:
continue
cnt = 2 ** (n2 - len(prefix) - 1)
if cnt >= k:
return dfs(prefix + c, n - 1, k)
else:
k -= cnt
return ""
n2 = n
return dfs("", n, k)
2473 Max Sum of a Pair With Equal Sum of Digits (link)
Description
You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the
sum of digits of the number nums[i] is equal to that of nums[j].
Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions. If no
such pair of indices exists, return -1.
Example 1:
Example 2:
Constraints:
class Solution:
def maximumSum(self, nums: List[int]) -> int:
def digitSum(n):
summ = 0
while n:
summ += n % 10
n //= 10
return summ
hashMap = {}
maxx = -1
return maxx
500 Keyboard Row (link)
Description
Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard
like the image below.
Note that the strings are case-insensitive, both lowercased and uppercased of the same letter are treated as if they are at the same
row.
Example 1:
Output: ["Alaska","Dad"]
Explanation:
Both "a" and "A" are in the 2nd row of the American keyboard due to case insensitivity.
Example 2:
Output: []
Example 3:
Output: ["adsdf","sfd"]
Constraints:
class Solution:
def findWords(self, words: List[str]) -> List[str]:
# Define keyboard rows
row1 = set("qwertyuiop")
row2 = set("asdfghjkl")
row3 = set("zxcvbnm")
return result
1364 Tuple with Same Product (link)
Description
Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d
are elements of nums, and a != b != c != d.
Example 1:
Example 2:
Constraints:
class Solution:
def tupleSameProduct(self, nums: list[int]) -> int:
ans = 0
count = collections.Counter()
for i in range(len(nums)):
for j in range(i):
prod = nums[i] * nums[j]
ans += count[prod] * 8
count[prod] += 1
return ans
541 Reverse String II (link)
Description
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.
If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then
reverse the first k characters and leave the other as original.
Example 1:
Input: s = "abcdefg", k = 2
Output: "bacdfeg"
Example 2:
Input: s = "abcd", k = 2
Output: "bacd"
Constraints:
class Solution:
def reverseStr(self, s: str, k: int) -> str:
c = 0
while c*k < len(s):
s = s[:c*k] + s[c*k:c*k+k][::-1] + s[c*k+k:]
c+=2
return s
3226 Minimum Number Game (link)
Description
You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a
game where in every round Alice and Bob will do one move. The rules of the game are as follows:
Every round, first Alice will remove the minimum element from nums, and then Bob does the same.
Now, first Bob will append the removed element in the array arr, and then Alice does the same.
The game continues until nums becomes empty.
Example 1:
Example 2:
Constraints:
/**
* @param {number[]} nums
* @return {number[]}
*/
var numberGame = function(nums) {
let res = new Array();
nums.sort((a,b) => b-a)
while(nums.length != 0){
let alice = nums.pop();
let bob = nums.pop();
res.push(bob, alice)
}
return res;
};
2813 To Be Or Not To Be (link)
Description
Write a function expect that helps developers test their code. It should take in any value val and return an object with the following two
functions.
toBe(val) accepts another value and returns true if the two values === each other. If they are not equal, it should throw an
error "Not Equal".
notToBe(val) accepts another value and returns true if the two values !== each other. If they are equal, it should throw an
error "Equal".
Example 1:
Example 2:
Example 3:
/**
* @param {string} val
* @return {Object}
*/
var expect = function (val) {
return {
toBe: (x) => {
if (x !== val) {
throw new Error("Not Equal")
} else return true;
},
notToBe: (x) => {
if (x === val) {
throw new Error("Equal")
} else return true;
}
}
};
/**
* expect(5).toBe(5); // true
* expect(5).notToBe(5); // throws "Equal"
*/
2917 Count Pairs Whose Sum is Less than Target (link)
Description
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and
nums[i] + nums[j] < target.
Example 1:
Example 2:
Constraints:
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
res = 0
n = len(nums)
for i in range(n):
for j in range(n):
if 0 <= i < j < n:
if nums[i] + nums[j] < target:
res += 1
return res
933 Increasing Order Search Tree (link)
Description
Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree,
and every node has no left child and only one right child.
Example 1:
Example 2:
Constraints:
The number of nodes in the given tree will be in the range [1, 100].
0 <= Node.val <= 1000
#Python3 Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
ptr = TreeNode()
res = ptr
def inorder(node):
nonlocal ptr
if not node:
return
inorder(node.left)
ptr.right = TreeNode(node.val)
ptr = ptr.right
inorder(node.right)
inorder(root)
return res.right
1078 Remove Outermost Parentheses (link)
Description
A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents
string concatenation.
For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.
A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty
valid parentheses strings.
Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid
parentheses strings.
Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.
Example 1:
Input: s = "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Example 2:
Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
Input: s = "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".
Constraints:
class Solution:
def removeOuterParentheses(self, S: str) -> str:
res, opened = [], 0
for c in S:
if c == '(' and opened > 0: res.append(c)
if c == ')' and opened > 1: res.append(c)
opened += 1 if c == '(' else -1
return "".join(res)
742 To Lower Case (link)
Description
Given a string s, return the string after replacing every uppercase letter with the same lowercase letter.
Example 1:
Input: s = "Hello"
Output: "hello"
Example 2:
Input: s = "here"
Output: "here"
Example 3:
Input: s = "LOVELY"
Output: "lovely"
Constraints:
class Solution:
def toLowerCase(self, s: str) -> str:
return s.lower()
1651 Shuffle String (link)
Description
You are given a string s and an integer array indices of the same length. The string s will be shuffled such that the character at the ith
position moves to indices[i] in the shuffled string.
Example 1:
Example 2:
Constraints:
s.length == indices.length == n
1 <= n <= 100
s consists of only lowercase English letters.
0 <= indices[i] < n
All values of indices are unique.
class Solution:
def restoreString(self, s: str, indices: List[int]) -> str:
n = len(s)
res = [""] * n
for i in range(n):
res[indices[i]] = s[i]
return "".join(res)
2116 Count Number of Pairs With Absolute Difference K (link)
Description
Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.
x if x >= 0.
-x if x < 0.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
res = 0
for i in range(len(nums)):
for j in range(len(nums)):
if i < j:
x = abs(nums[i] - nums[j])
if x == k:
res += 1
return res
1775 Design an Ordered Stream (link)
Description
There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a
string. No two pairs have the same id.
Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The
concatenation of all the chunks should result in a list of the sorted values.
Example:
Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"].
OrderedStream os = new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
// Concatentating all the chunks returned:
// [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]
// The resulting order is the same as the order above.
Constraints:
class OrderedStream:
Description
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to
count the number of valid j's such that j != i and nums[j] < nums[i].
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
temp = sorted(nums)
mapping = {}
result = []
for i in range(len(temp)):
if temp[i] not in mapping:
mapping[temp[i]] = i
for i in range(len(nums)):
result.append(mapping[nums[i]])
return result
3206 Find Common Elements Between Two Arrays (link)
Description
You are given two integer arrays nums1 and nums2 of sizes n and m, respectively. Calculate the following values:
Return [answer1,answer2].
Example 1:
Output: [2,1]
Explanation:
Example 2:
Output: [3,4]
Explanation:
Example 3:
Output: [0,0]
Explanation:
Constraints:
n == nums1.length
m == nums2.length
1 <= n, m <= 100
1 <= nums1[i], nums2[i] <= 100
class Solution:
def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
hash1 = set(nums1)
hash2 = set(nums2)
ans1, ans2 = 0, 0
for i in nums1:
if i in hash2:
ans1 += 1
for j in nums2:
if j in hash1:
ans2 += 1
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.
Example 1:
Input: s = "abccbaacz"
Output: "c"
Explanation:
The letter 'a' appears on the indexes 0, 5 and 6.
The letter 'b' appears on the indexes 1 and 4.
The letter 'c' appears on the indexes 2, 3 and 7.
The letter 'z' appears on the index 8.
The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smalles
Example 2:
Input: s = "abcdd"
Output: "d"
Explanation:
The only letter that appears twice is 'd' so we return 'd'.
Constraints:
class Solution:
def repeatedCharacter(self, s: str) -> str:
twice = set()
for i in s:
if i in twice:
return i
else:
twice.add(i)
387 First Unique Character in a String (link)
Description
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1:
Input: s = "leetcode"
Output: 0
Explanation:
The character 'l' at index 0 is the first character that does not occur at any other index.
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
class Solution:
def firstUniqChar(self, s: str) -> int:
counter = Counter(s)
for i in range(len(s)):
if counter[s[i]] == 1:
return i
return -1
2406 Decode the Message (link)
Description
You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode
message are as follows:
1. Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
2. Align the substitution table with the regular English alphabet.
3. Each letter in message is then substituted using the table.
4. Spaces ' ' are transformed to themselves.
For example, given key = "happy boy" (actual key would have at least one instance of each letter in the alphabet), we have the
partial substitution table of ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f').
Example 1:
Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: "this is a secret"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".
Example 2:
Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: "the five boxing wizards jump quickly"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".
Constraints:
class Solution:
def decodeMessage(self, key: str, message: str) -> str:
alphabet={}
k = 0
for c in key:
if c != ' ' and c not in alphabet:
alphabet[c] = chr(k + ord('a'))
k += 1
decode = []
for c in message:
if c != ' ':
decode.append(alphabet[c])
else:
decode.append(' ')
return ''.join(decode)
1895 Minimum Number of Operations to Move All Balls to Each Box (link)
Description
You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains
one ball.
In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after
doing so, there may be more than one ball in some boxes.
Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.
Example 1:
Example 2:
Constraints:
n == boxes.length
1 <= n <= 2000
boxes[i] is either '0' or '1'.
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
distances = [0] * n
prefixCount = 0
prefixSum = 0
for i in range(n):
distances[i] = prefixCount * i - prefixSum
if boxes[i] == '1':
prefixCount += 1
prefixSum += i
suffixCount = 0
suffixSum = 0
return distances
543 Diameter of Binary Tree (link)
Description
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass
through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Example 2:
Constraints:
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# Define a recursive function to calculate the diameter
def diameter(node, res):
# Base case: if the node is None, return 0
if not node:
return 0
Description
You are given the root of a binary tree that consists of exactly 3 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, or false otherwise.
Example 1:
Example 2:
Constraints:
The tree consists only of the root, its left child, and its right child.
-100 <= Node.val <= 100
stack = [root]
while stack:
curr = stack.pop()
if curr.left and curr.right:
right = curr.right.val
left = curr.left.val
if right + left == curr.val:
return True
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return False
975 Range Sum of BST (link)
Description
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the
inclusive range [low, high].
Example 1:
Example 2:
Constraints:
Description
Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.
A string is represented by an array if the array elements concatenated in order forms the string.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
word1 = "".join(word1)
word2 = "".join(word2)
Description
You are given a 0-indexed integer array nums of size n.
leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.
Example 1:
Example 2:
Constraints:
class Solution:
def leftRightDifference(self, nums: List[int]) -> List[int]:
ans = []
left = 0
right = sum(nums)
for n in nums:
ans.append(abs(left - (right-n)))
left += n
right -= n
return ans
3309 Count Prefix and Suffix Pairs I (link)
Description
You are given a 0-indexed string array words.
Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:
isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.
For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but
isPrefixAndSuffix("abc", "abcd") is false.
Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
n = len(words)
count = 0
for i in range(n):
for j in range(i+1, n):
if words[j].startswith(words[i]) and words[j].endswith(words[i]):
count += 1
return count
1524 String Matching in an Array (link)
Description
Given an array of string words, return all strings in words that are a substring of another word. You can return the answer in any order.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def stringMatching(self, words: List[str]) -> List[str]:
n = len(words)
ans = []
for i in range(n):
for j in range(n):
if i != j and words[j].find(words[i]) != -1:
ans.append(words[i])
break
return ans
3331 Minimum Operations to Exceed Threshold Value I (link)
Description
You are given a 0-indexed integer array nums, and an integer k.
In one operation, you can remove one occurrence of the smallest element of nums.
Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
count = 0
for i in nums:
if i < k:
count += 1
return count
2876 Number of Employees Who Met the Target (link)
Description
There are n employees in a company, numbered from 0 to n - 1. Each employee i has worked for hours[i] hours in the company.
The company requires each employee to work for at least target hours.
You are given a 0-indexed array of non-negative integers hours of length n and a non-negative integer target.
Return the integer denoting the number of employees who worked at least target hours.
Example 1:
Example 2:
Constraints:
class Solution:
def numberOfEmployeesWhoMetTarget(self, hours: List[int], target: int) -> int:
count = 0
for i in hours:
if i >= target:
count += 1
return count
1528 Kids With the Greatest Number of Candies (link)
Description
There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith
kid has, and an integer extraCandies, denoting the number of extra candies that you have.
Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the
greatest number of candies among all the kids, or false otherwise.
Note that multiple kids can have the greatest number of candies.
Example 1:
Example 2:
Example 3:
Constraints:
n == candies.length
2 <= n <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50
class Solution:
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
maxCandies = max(candies)
return [(candy + extraCandies) >= maxCandies for candy in candies]
3582 Find Indices of Stable Mountains (link)
Description
There are n mountains in a row, and each mountain has a height. You are given an integer array height where height[i] represents the
height of mountain i, and an integer threshold.
A mountain is called stable if the mountain just before it (if it exists) has a height strictly greater than threshold. Note that mountain
0 is not stable.
Return an array containing the indices of all stable mountains in any order.
Example 1:
Output: [3,4]
Explanation:
Example 2:
Output: [1,3]
Example 3:
Output: []
Constraints:
class Solution:
def stableMountains(self, height: List[int], threshold: int) -> List[int]:
res = []
for i in range(1, len(height)):
if height[i-1] > threshold:
res.append(i)
return res
2543 Most Popular Video Creator (link)
Description
You are given two string arrays creators and ids, and an integer array views, all of length n. The ith video on a platform was created by
creators[i], has an id of ids[i], and has views[i] views.
The popularity of a creator is the sum of the number of views on all of the creator's videos. Find the creator with the highest
popularity and the id of their most viewed video.
Note: It is possible for different videos to have the same id, meaning that ids do not uniquely identify a video. For example, two videos
with the same ID are considered as distinct videos with their own viewcount.
Return a 2D array of strings answer where answer[i] = [creatorsi, idi] means that creatorsi has the highest popularity and idi is the
id of their most popular video. The answer can be returned in any order.
Example 1:
Output: [["alice","one"],["bob","two"]]
Explanation:
Example 2:
Output: [["alice","b"]]
Explanation:
The videos with id "b" and "c" have the highest view count.
Since "b" is lexicographically smaller than "c", it is included in the answer.
Constraints:
class Solution:
def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
# Dictionaries to track total views and most popular video for each creator
viewscount: Dict[str, int] = {}
creatorMaxId: Dict[str, (int, str)] = {}
# Build the result: most popular creators and their most popular video ID
res = [[creator, creatorMaxId[creator][1]] for creator in most_popular_creators]
return res
724 Find Pivot Index (link)
Description
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers
strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the
right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total_sum = sum(nums) # Total sum of the array
for i in range(len(nums)):
# Right sum is total sum minus left sum minus current element
right_sum = total_sum - left_sum - nums[i]
return -1
2358 Number of Ways to Split Array (link)
Description
You are given a 0-indexed integer array nums of length n.
The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
There is at least one element to the right of i. That is, 0 <= i < n - 1.
Example 1:
Example 2:
Constraints:
class Solution:
def waysToSplitArray(self, nums: List[int]) -> int:
n = len(nums)
res = 0
return res
2691 Count Vowel Strings in Ranges (link)
Description
You are given a 0-indexed array of strings words and a 2D array of integers queries.
Each query queries[i] = [li, ri] asks us to find the number of strings present at the indices ranging from li to ri (both inclusive) of
words that start and end with a vowel.
Return an array ans of size queries.length, where ans[i] is the answer to the ith query.
Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.
Example 1:
Example 2:
Constraints:
class Solution:
def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
n = len(words)
Prefix = [0] * (n + 1)
vowels = {'a', 'e', 'i', 'o', 'u'}
for i in range(n):
Prefix[i + 1] = Prefix[i]
if words[i][0] in vowels and words[i][-1] in vowels:
Prefix[i + 1] += 1
ANS = []
for query in queries:
ANS.append(Prefix[query[1] + 1] - Prefix[query[0]])
return ANS
1537 Maximum Score After Splitting a String (link)
Description
Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left
substring and right substring).
The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.
Example 1:
Input: s = "011101"
Output: 5
Explanation:
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5
left = "01" and right = "1101", score = 1 + 3 = 4
left = "011" and right = "101", score = 1 + 2 = 3
left = "0111" and right = "01", score = 1 + 1 = 2
left = "01110" and right = "1", score = 2 + 1 = 3
Example 2:
Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5
Example 3:
Input: s = "1111"
Output: 3
Constraints:
class Solution:
def maxScore(self, s: str) -> int:
total_ones = s.count("1") # Total count of '1's in the string
max_score = 0
left_zeros = 0
right_ones = total_ones
return max_score
2128 Reverse Prefix of Word (link)
Description
Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first
occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.
For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive).
The resulting string will be "dcbaefd".
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def reversePrefix(self, word: str, ch: str) -> str:
temp = ""
index = 0
if ch not in set(word):
return word
for i in word:
index += 1
temp += i
if i == ch:
break
Description
Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the
same frequency, sort them in decreasing order.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
freq = Counter(nums)
return sorted(nums, key=lambda x: (freq[x], -x))
2502 Sort the People (link)
Description
You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.
For each index i, names[i] and heights[i] denote the name and height of the ith person.
Example 1:
Example 2:
Constraints:
n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.
class Solution:
def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
hashmap = {}
sorted_height = sorted(hashmap.keys())[::-1]
return res
1944 Truncate Sentence (link)
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 sand an integer k. You want to truncate ssuch that it contains only the first kwords. Return safter
truncating it.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def truncateSentence(self, s: str, k: int) -> str:
res = ""
for i in words[:k]:
res += i
res += " "
return res[:-1]
1765 Merge In Between Linked Lists (link)
Description
You are given two linked lists: list1 and list2 of sizes n and m respectively.
Remove list1's nodes from the ath node to the bth node, and put list2 in their place.
The blue edges and nodes in the following figure indicate the result:
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
// p1 = list1
// for i in range(a-1):
// p1 = p1.next
// p2 = p1
// for i in range(b-a+2):
// p2 = p2.next
// p1.next = list2
// while list2.next:
// list2 = list2.next
// list2.next = p2
// return list1
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode p1 = list1;
for(int i=0;i<a-1;i++){
p1 = p1.next;
}
ListNode p2 = p1;
for(int i=0; i < b-a+2; i++){
p2 = p2.next;
}
p1.next = list2;
while(list2.next != null){
list2 = list2.next;
}
list2.next = p2;
return list1;
}
}
3501 Delete Nodes From Linked List Present in Array (link)
Description
You are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes
from the linked list that have a value that exists in nums.
Example 1:
Output: [4,5]
Explanation:
Example 2:
Output: [2,2,2]
Explanation:
Example 3:
Output: [1,2,3,4]
Explanation:
Constraints:
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.stream.Collectors;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
// Convert the nums array into a HashSet for fast lookup
Set<Integer> numsSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());
return dummy.next;
}
}
237 Delete Node in a Linked List (link)
Description
There is a singly-linked list head and we want to delete a node node in it.
You are given the node to be deleted node. You will not be given access to the first node of head.
All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.
Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:
The value of the given node should not exist in the linked list.
The number of nodes in the linked list should decrease by one.
All the values before node should be in the same order.
All the values after node should be in the same order.
Custom testing:
For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the
list and should be an actual node in the list.
We will build the linked list and pass the node to your function.
The output will be the entire list after calling your function.
Example 1:
Example 2:
Constraints:
The number of the nodes in the given list is in the range [2, 1000].
-1000 <= Node.val <= 1000
The value of each node in the list is unique.
The node to be deleted is in the list and is not a tail node.
(scroll down for solution)
Solution
Language: java
Status: Accepted
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
}
prev.next = null;
}
}
2299 Merge Nodes in Between Zeros (link)
Description
You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list
will have Node.val == 0.
For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged
nodes. The modified list should not contain any 0's.
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode node = head.next;
ListNode temp = node;
while (temp != null) {
int sum = 0;
while (temp.val != 0) {
sum += temp.val;
temp = temp.next;
}
node.val = sum;
temp = temp.next;
node.next = temp;
node = temp;
}
head = head.next;
return head;
}
}
1570 Final Prices With a Special Discount in a Shop (link)
Description
You are given an integer array prices where prices[i] is the price of the ith item in a shop.
There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where
j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.
Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special
discount.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
n = len(prices)
result = prices[:] # Copy of prices to store final results
for i in range(n):
for j in range(i + 1, n):
if prices[j] <= prices[i]:
result[i] = prices[i] - prices[j]
break # Stop at the first valid discount
return result
2887 Sort Vowels in a String (link)
Description
Given a 0-indexed string s, permute s to get a new string t such that:
All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a
consonant, then t[i] = s[i].
The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i
< j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are
not vowels.
Example 1:
Input: s = "lEetcOde"
Output: "lEOtcede"
Explanation: 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to th
Example 2:
Input: s = "lYmpH"
Output: "lYmpH"
Explanation: There are no vowels in s (all characters in s are consonants), so we return "lYmpH".
Constraints:
class Solution:
def sortVowels(self, s: str) -> str:
vowels = set('aeiouAEIOU')
return ''.join(result)
3543 Count Substrings That Satisfy K-Constraint I (link)
Description
You are given a binary string s and an integer k.
A binary string satisfies the k-constraint if either of the following conditions holds:
Return an integer denoting the number of substrings of s that satisfy the k-constraint.
Example 1:
Input: s = "10101", k = 1
Output: 12
Explanation:
Every substring of s except the substrings "1010", "10101", and "0101" satisfies the k-constraint.
Example 2:
Input: s = "1010101", k = 2
Output: 25
Explanation:
Every substring of s except the substrings with a length greater than 5 satisfies the k-constraint.
Example 3:
Input: s = "11111", k = 1
Output: 15
Explanation:
Constraints:
class Solution:
def countKConstraintSubstrings(self, s: str, t: int) -> int:
n = len(s)
ans = 0
for i in range(n):
zero_count, one_count = 0, 0
for j in range(i, n):
if s[j] == '0':
zero_count += 1
else:
one_count += 1
return ans
1611 Making File Names Unique (link)
Description
Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a
folder with the name names[i].
Since two files cannot have the same name, if you enter a folder name that was previously used, the system will have a suffix
addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.
Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def getFolderNames(self, names: List[str]) -> List[str]:
folder_map = set()
result = []
k = 1
while f"{name}({k})" in folder_map:
k += 1
new_name = f"{name}({k})"
folder_map.add((new_name))
result.append(new_name)
return result
1797 Goal Parser Interpretation (link)
Description
You own a Goal Parser that can interpret a string command. The command 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 of command.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def interpret(self, command: str) -> str:
res = ""
for i in range(len(command)):
if command[i].isalpha():
res += command[i]
continue
if command[i] == "(" and command[i+1] == ")":
res += "o"
return res
520 Detect Capital (link)
Description
We define the usage of capitals in a word to be right when one of the following cases holds:
Example 1:
Example 2:
Constraints:
class Solution:
def detectCapitalUse(self, word: str) -> bool:
Description
You are given a string word. A letter is called special if it appears both in lowercase and uppercase in word.
Example 1:
Output: 3
Explanation:
Example 2:
Output: 0
Explanation:
Example 3:
Output: 1
Explanation:
Constraints:
class Solution:
def numberOfSpecialChars(self, word: str) -> int:
res = 0
for i in set(word):
if i.isupper() and i.lower() in set(word):
res += 1
return res
1363 Greatest English Letter in Upper and Lower Case (link)
Description
Given a string of English letters s, return the greatest English letter which occurs as both a lowercase and uppercase letter in s. The
returned letter should be in uppercase. If no such letter exists, return an empty string.
An English letter b is greater than another letter a if b appears after a in the English alphabet.
Example 1:
Input: s = "lEeTcOdE"
Output: "E"
Explanation:
The letter 'E' is the only letter to appear in both lower and upper case.
Example 2:
Input: s = "arRAzFif"
Output: "R"
Explanation:
The letter 'R' is the greatest letter to appear in both lower and upper case.
Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.
Example 3:
Input: s = "AbCdEfGhIjK"
Output: ""
Explanation:
There is no letter that appears in both lower and upper case.
Constraints:
class Solution:
def greatestLetter(self, s: str) -> str:
maxx = 0
for i in set(s):
if i.isupper() and i.lower() in s:
maxx = max(ord(i.upper()), maxx)
if maxx:
return chr(maxx)
else:
return ""
2173 Number of Valid Words in a Sentence (link)
Description
A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and
spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.
Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!".
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def countValidWords(self, sentence: str) -> int:
pattern = re.compile(r'(^[a-z]+(-[a-z]+)?)?[,.!]?$')
return sum(bool(pattern.match(word)) for word in sentence.split())
2219 Maximum Number of Words Found in Sentences (link)
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 each sentences[i] represents a single sentence.
Example 1:
Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation:
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.
Example 2:
Constraints:
class Solution:
def mostWordsFound(self, sentences: List[str]) -> int:
maxx = 0
for i in sentences:
word_length = len(i.split(" "))
if word_length > maxx:
maxx = word_length
return maxx
51 N-Queens (link)
Description
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an
empty space, respectively.
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
1 <= n <= 9
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
col = set()
posDiag = set()
negDiag = set()
res = []
board = [["."] * n for i in range(n)]
def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if c in col or (r+c) in posDiag or (r-c) in negDiag:
continue
col.add(c)
posDiag.add(r+c)
negDiag.add(r-c)
board[r][c] = "Q"
backtrack(r+1)
col.remove(c)
posDiag.remove(r+c)
negDiag.remove(r-c)
board[r][c] = "."
backtrack(0)
return res
3412 Permutation Difference between Two Strings (link)
Description
You are given two strings s and t such that every character occurs at most once in s and t is a permutation of s.
The permutation difference between s and t is defined as the sum of the absolute difference between the index of the occurrence of
each character in s and the index of the occurrence of the same character in t.
Example 1:
Output: 2
Explanation:
For s = "abc" and t = "bac", the permutation difference of s and t is equal to the sum of:
The absolute difference between the index of the occurrence of "a" in s and the index of the occurrence of "a" in t.
The absolute difference between the index of the occurrence of "b" in s and the index of the occurrence of "b" in t.
The absolute difference between the index of the occurrence of "c" in s and the index of the occurrence of "c" in t.
Example 2:
Output: 12
Constraints:
class Solution:
def findPermutationDifference(self, s: str, t: str) -> int:
res = 0
for i in range(len(s)):
res += abs(i - t.index(s[i]))
return res
1381 Maximum Score Words Formed by Letters (link)
Description
Given a list of words, list of single letters (might be repeating) and score of every character.
Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).
It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given
by score[0], score[1], ... , score[25] respectively.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
def count(s):
letter_count = {}
for letter in s:
if not letter in letter_count:
letter_count[letter] = 0
letter_count[letter] += 1
return letter_count
letter_count = count("".join(letters))
counts = []
words_scores = []
word_score = 0
for char in word:
word_score += score[ord(char) - ord('a')]
words_scores.append(word_score)
if i == len(words):
return 0
# skip
result = dfs(i + 1, letters)
remaining_letters = letters.copy()
word_letters = counts[i]
Description
You are given an array nums consisting of positive integers.
Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
Add the value of the chosen integer to score.
Mark the chosen element and its two adjacent elements if they exist.
Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
Example 1:
Example 2:
Constraints:
class Solution:
def findScore(self, nums: List[int]) -> int:
score = 0
n = len(nums)
q = deque()
return score
448 Find All Numbers Disappeared in an Array (link)
Description
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not
appear in nums.
Example 1:
Example 2:
Constraints:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
set_nums = set(nums)
missing = []
for i in range(1,len(nums)+1):
if i not in set_nums:
missing.append(i)
return missing
# Do upvote if you like it
442 Find All Duplicates in an Array (link)
Description
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice,
return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the
output
Example 1:
Example 2:
Example 3:
Constraints:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Each element in nums appears once or twice.
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = set()
hash_set = set()
for i in range(len(nums)):
if nums[i] in hash_set:
res.add(nums[i])
else:
hash_set.add(nums[i])
return list(res)
3581 The Two Sneaky Numbers of Digitville (link)
Description
In the town of Digitville, there was a list of numbers called nums containing integers from 0 to n - 1. Each number was supposed to
appear exactly once in the list, however, two mischievous numbers sneaked in an additional time, making the list longer than usual.
As the town detective, your task is to find these two sneaky numbers. Return an array of size two containing the two numbers (in any
order), so peace can return to Digitville.
Example 1:
Output: [0,1]
Explanation:
Example 2:
Output: [2,3]
Explanation:
Example 3:
Output: [4,5]
Explanation:
Constraints:
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
res = set()
hash_set = set()
for i in range(len(nums)):
if nums[i] in hash_set:
res.add(nums[i])
else:
hash_set.add(nums[i])
return list(res)
3194 Find Words Containing Character (link)
Description
You are given a 0-indexed array of strings words and a character x.
Return an array of indices representing the words that contain the character x.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def findWordsContaining(self, words: List[str], x: str) -> List[int]:
res = []
for index, word in enumerate(words):
word = set(word)
if x in word:
res.append(index)
return res
782 Jewels and Stones (link)
Description
You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each
character in stones 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".
Example 1:
Example 2:
Constraints:
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
res = 0
jewels = set(jewels)
for i in stones:
if i in jewels:
res += 1
return res
1205 Defanging an IP Address (link)
Description
Given a valid (IPv4) IP address, return a defanged version of that IP address.
Example 1:
Example 2:
Constraints:
class Solution:
def defangIPaddr(self, address: str) -> str:
res = ""
for i in address:
if i == ".":
res += "[.]"
else:
res += i
return res
195 Tenth Line (link)
Description
Given a text file file.txt, print just the 10th line of the file.
Example:
Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10
Line 10
Note:
1. If the file contains less than 10 lines, what should you output?
2. There's at least three different solutions. Try to explore all possibilities.
# Read from the file file.txt and output the tenth line to stdout.
sed '10q;d' file.txt
1580 Shuffle the Array (link)
Description
Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
l = nums[:n]
r = nums[n:]
res = []
for i,j in zip(l,r):
res.append(i)
res.append(j)
return res
2454 Largest Local Values in a Matrix (link)
Description
You are given an n x n integer matrix grid.
maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.
In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.
Example 1:
Example 2:
Constraints:
n == grid.length == grid[i].length
3 <= n <= 100
1 <= grid[i][j] <= 100
class Solution:
def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
res = []
return res
2244 Number of Laser Beams in a Bank (link)
Description
Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of
the bank, which is an m x n 2D matrix. bank[i] represents the ith row, consisting of '0's and '1's. '0' means the cell is empty, while'1'
means the cell has a security device.
There is one laser beam between any two security devices if both conditions are met:
The two devices are located on two different rows: r1 and r2, where r1 < r2.
For each row i where r1 < i < r2, there are no security devices in the ith row.
Laser beams are independent, i.e., one beam does not interfere nor join with another.
Example 1:
Example 2:
m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] is either '0' or '1'.
import java.util.ArrayList;
import java.util.List;
class Solution {
public int numberOfBeams(String[] bank) {
List<Integer> rowCounts = new ArrayList<>();
// Count the number of '1's in each row and skip rows with no devices
for (String row : bank) {
int count = 0;
for (char c : row.toCharArray()) {
if (c == '1') {
count++;
}
}
if (count > 0) {
rowCounts.add(count);
}
}
return result;
}
}
47 Permutations II (link)
Description
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Example 2:
Constraints:
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
n = len(nums)
visited = [False] * n
def dfs(path, i):
if i == n:
res.append(path[:])
return
for j in range(n):
if visited[j]: continue
if j > 0 and nums[j] == nums[j-1] and not visited[j-1]:
continue
path.append(nums[j])
visited[j] = True
dfs(path, i+1)
path.pop()
visited[j] = False
dfs([], 0)
return res
1572 Subrectangle Queries (link)
Description
Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports
two methods:
1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is
(row2,col2).
Returns the current value of the coordinate (row,col) from the rectangle.
Example 1:
Input
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
Output
[null,1,null,5,5,null,10,5]
Explanation
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);
// The initial rectangle (4x3) looks like:
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // return 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// After this update the rectangle looks like:
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5
subrectangleQueries.getValue(0, 2); // return 5
subrectangleQueries.getValue(3, 1); // return 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// After this update the rectangle looks like:
// 5 5 5
// 5 5 5
// 5 5 5
// 10 10 10
subrectangleQueries.getValue(3, 1); // return 10
subrectangleQueries.getValue(0, 2); // return 5
Example 2:
Input
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
Output
[null,1,null,100,100,null,20]
Explanation
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
subrectangleQueries.getValue(0, 0); // return 1
subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
subrectangleQueries.getValue(0, 0); // return 100
subrectangleQueries.getValue(2, 2); // return 100
subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
subrectangleQueries.getValue(2, 2); // return 20
Constraints:
There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols
class SubrectangleQueries:
def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
for i in range(row1,row2+1):
self.rectangle[i][col1: col2+1] = [newValue] * (col2+1 - col1)
Description
There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.
You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1]
= 3, then person 1 must be in a group of size 3.
Return a list of groups such that each person i is in a group of size groupSizes[i].
Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of
them. It is guaranteed that there will be at least one valid solution for the given input.
Example 1:
Example 2:
Constraints:
groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n
class Solution {
public List<List<Integer>> groupThePeople(final int[] groupSizes) {
final int n = groupSizes.length;
final List<Integer>[] buckets = new List[n + 1];
final List<List<Integer>> result = new ArrayList<>();
if(buckets[size] == null)
buckets[size] = new ArrayList<>();
buckets[size].add(id);
if(buckets[size].size() == size) {
result.add(buckets[size]);
buckets[size] = new ArrayList<>();
}
}
return result;
}
}
459 Repeated Substring Pattern (link)
Description
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
Example 2:
Input: s = "aba"
Output: false
Example 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Constraints:
class Solution:
def repeatedSubstringPattern(self, s):
"""
:type str: str
:rtype: bool
"""
if not s:
return False
ss = (s + s)[1:-1]
return ss.find(s) != -1
22 Generate Parentheses (link)
Description
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(left, right, s):
if len(s) == n * 2:
res.append(s)
return
if left < n:
dfs(left + 1, right, s + '(')
res = []
dfs(0, 0, '')
return res
3291 Find if Array Can Be Sorted (link)
Description
You are given a 0-indexed array of positive integers nums.
In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this
operation any number of times (including zero).
Return true if you can sort the array in ascending order, else return false.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
pmax = cmin = cmax = pcnt = 0
for v in nums:
ccnt = v.bit_count()
if pcnt == ccnt:
cmin = min(cmin, v)
cmax = max(cmax, v)
elif cmin < pmax:
return False
else:
pmax = cmax
cmin = cmax = v
pcnt = ccnt
return cmin >= pmax
3174 Minimum Number of Changes to Make Binary String Beautiful (link)
Description
You are given a 0-indexed binary string s having an even length.
A string is beautiful if it's possible to partition it into one or more substrings such that:
Return the minimum number of changes required to make the string s beautiful.
Example 1:
Input: s = "1001"
Output: 2
Explanation: We change s[1] to 1 and s[3] to 0 to get string "1100".
It can be seen that the string "1100" is beautiful because we can partition it into "11|00".
It can be proven that 2 is the minimum number of changes needed to make the string beautiful.
Example 2:
Input: s = "10"
Output: 1
Explanation: We change s[1] to 1 to get string "11".
It can be seen that the string "11" is beautiful because we can partition it into "11".
It can be proven that 1 is the minimum number of changes needed to make the string beautiful.
Example 3:
Input: s = "0000"
Output: 0
Explanation: We don't need to make any changes as the string "0000" is beautiful already.
Constraints:
class Solution:
def minChanges(self, s):
count = 0
i = 0
while i < len(s) - 1:
if s[i] != s[i + 1]:
count += 1
i += 2
return count
3451 String Compression III (link)
Description
Given a string word, compress it using the following algorithm:
Begin with an empty string comp. While word is not empty, use the following operation:
Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
Append the length of the prefix followed by c to comp.
Example 1:
Output: "1a1b1c1d1e"
Explanation:
Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.
Example 2:
Output: "9a5a2b"
Explanation:
Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.
Constraints:
class Solution:
def compressedString(self, word: str) -> str:
comp = ""
cnt, n = 1, len(word)
ch = word[0]
for i in range(1, n):
if word[i] == ch and cnt < 9:
cnt += 1
else:
comp += str(cnt) + ch
ch = word[i]
cnt = 1
comp += str(cnt) + ch
return comp
2159 Two Out of Three (link)
Description
Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out
of the three arrays. You may return the values in any order.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
res = []
for num1 in nums1:
if num1 in nums2 or num1 in nums3:
if num1 not in res:
res.append(num1)
for num2 in nums2:
if num2 in nums1 or num2 in nums3:
if num2 not in res:
res.append(num2)
return res
812 Rotate String (link)
Description
Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.
Example 1:
Example 2:
Constraints:
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
# Check if the lengths are the same
if len(s) != len(goal):
return False
Description
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array nums, return the minimum number of elements to remove to make numsa mountain array.
Example 1:
Example 2:
Constraints:
class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
LIS = [1] * n
LDS = [1] * n
maxMountainLength = 0
return n - maxMountainLength
776 N-ary Tree Postorder Traversal (link)
Description
Given the root of an n-ary tree, return the postorder traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See
examples)
Example 1:
Example 2:
Constraints:
"""
# Definition for a Node.
class Node:
def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: "Node") -> List[int]:
result = []
# If the root is None, return the empty list
if root is None:
return result
while node_stack:
current_node, is_visited = node_stack.pop()
if is_visited:
# If the node has been visited, add its value to the result
result.append(current_node.val)
else:
# Mark the current node as visited and push it back to the stack
node_stack.append((current_node, True))
return result
932 Monotonic Array (link)
Description
An array is monotonic if it is either monotone increasing or monotone decreasing.
An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= j, nums[i]
>= nums[j].
Given an integer array nums, return true if the given array is monotonic, or false otherwise.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def isMonotonic(self, nums: List[int]) -> bool:
if len(nums) == 1:
return True
check = []
for i in range(1, len(nums)):
check.append(nums[i]-nums[i-1])
if min(check) < 0 and max(check) > 0:
return False
return True
3379 Score of a String (link)
Description
You are given a string s. The score of a string is defined as the sum of the absolute difference between the ASCII values of adjacent
characters.
Example 1:
Input: s = "hello"
Output: 13
Explanation:
The ASCII values of the characters in s are: 'h' = 104, 'e' = 101, 'l' = 108, 'o' = 111. So, the score of s would be |104 - 101| + |101 -
108| + |108 - 108| + |108 - 111| = 3 + 7 + 0 + 3 = 13.
Example 2:
Input: s = "zaz"
Output: 50
Explanation:
The ASCII values of the characters in s are: 'z' = 122, 'a' = 97. So, the score of s would be |122 - 97| + |97 - 122| = 25 + 25 = 50.
Constraints:
class Solution:
def scoreOfString(self, s: str) -> int:
score = 0
return score
111 Minimum Depth of Binary Tree (link)
Description
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Example 1:
Example 2:
Constraints:
Description
Given a binary tree, determine if it is height-balanced.
Example 1:
Example 2:
Example 3:
Input: root = []
Output: true
Constraints:
Description
You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and
reverse it. You are allowed to make any number of steps.
Return true if you can make arr equal to target or false otherwise.
Example 1:
Example 2:
Example 3:
Constraints:
target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000
class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
Description
You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.
You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the
following:
An integer x.
Record a new score of x.
'+'.
Record a new score that is the sum of the previous two scores.
'D'.
Record a new score that is the double of the previous score.
'C'.
Invalidate the previous score, removing it from the record.
Return the sum of all the scores on the record after applying all the operations.
The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are
valid.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def calPoints(self, operations: List[str]) -> int:
score_list = []
for i in operations:
if i.lstrip("-").isdigit():
score_list.append(int(i))
elif i == "C":
score_list.pop()
elif i == "+":
score_list.append(score_list[-1] + score_list[-2])
elif i == "D":
score_list.append(score_list[-1] * 2)
return sum(score_list)
557 Reverse Words in a String III (link)
Description
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Example 2:
Constraints:
class Solution:
def reverseWords(self, s: str) -> str:
res = ''
s = s.split(" ")
for i in s:
res += i[::-1]
res += " "
return res[:-1]
1197 Parsing A Boolean Expression (link)
Description
A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:
Given a string expression that represents a boolean expression, return the evaluation of that expression.
It is guaranteed that the given expression is valid and follows the given rules.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
st = deque()
for c in expression:
if c == "," or c == "(":
continue
if c in ["t", "f", "!", "&", "|"]:
st.append(c)
elif c == ")":
has_true = False
has_false = False
while st[-1] not in ["!", "&", "|"]:
top_value = st.pop()
if top_value == "t":
has_true = True
elif top_value == "f":
has_false = True
op = st.pop()
if op == "!":
st.append("t" if not has_true else "f")
elif op == "&":
st.append("f" if has_false else "t")
else:
st.append("t" if has_true else "f")
return st[-1] == "t"
415 Add Strings (link)
Description
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not
convert the inputs to integers directly.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j, carry = len(num1) - 1, len(num2) - 1, 0
ans = ""
return ans[::-1]
404 Sum of Left Leaves (link)
Description
Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Example 1:
Example 2:
Constraints:
def dfs(node,left):
if not node:
return
dfs(node.left,True)
dfs(node.right,False)
dfs(root,False)
return self.total
3093 Sum of Values at Indices With K Set Bits (link)
Description
You are given a 0-indexed integer array nums and an integer k.
Return an integer that denotes the sum of elements in nums whose corresponding indices have exactly k set bits in their binary
representation.
The set bits in an integer are the 1's present when it is written in binary.
For example, the binary representation of 21 is 10101, which has 3 set bits.
Example 1:
Example 2:
Constraints:
class Solution:
def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
ans = 0
for i in range(len(nums)):
binn = str(bin(i))[2:]
bin_count = binn.count("1")
if bin_count == k:
ans += nums[i]
return ans
338 Counting Bits (link)
Description
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary
representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
Follow up:
It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single
pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?
class Solution:
def countBits(self, n: int) -> List[int]:
ans = []
for i in range(n+1):
binn = str(bin(i))[2:]
one = binn.count("1")
ans.append(one)
return ans
1341 Split a String in Balanced Strings (link)
Description
Balanced strings are those that have an equal quantity of 'L' and 'R' characters.
Given a balanced string s, split it into some number of substrings such that:
Example 1:
Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.
Example 2:
Input: s = "RLRRRLLRLL"
Output: 2
Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'.
Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.
Example 3:
Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".
Constraints:
class Solution:
def balancedStringSplit(self, s: str) -> int:
count, ans = 0, 0
for char in s:
count += 1 if char == 'R' else -1
ans += count == 0
return ans
3195 Separate Black and White Balls (link)
Description
There are n balls on a table, each ball has a color black or white.
You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.
In each step, you can choose two adjacent balls and swap them.
Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.
Example 1:
Input: s = "101"
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "011".
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.
Example 2:
Input: s = "100"
Output: 2
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "010".
- Swap s[1] and s[2], s = "001".
It can be proven that the minimum number of steps needed is 2.
Example 3:
Input: s = "0111"
Output: 0
Explanation: All the black balls are already grouped to the right.
Constraints:
class Solution:
def minimumSteps(self, s: str) -> int:
ans = c = 0
for i in range(len(s)):
if s[i] == "1":
c += 1
else:
ans += c
return ans
2616 Maximal Score After Applying K Operations (link)
Description
You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.
In one operation:
Return the maximum possible score you can attain after applying exactly k operations.
The ceiling function ceil(val) is the least integer greater than or equal to val.
Example 1:
Example 2:
Constraints:
class Solution:
def maxKelements(self, nums: List[int], k: int) -> int:
heapify(pq:=[-x for x in nums])
score=0
for i in range(k):
x=-heappop(pq)
score+=x
if x==1:
score+=k-1-i
break
heappush(pq, -((x+2)//3))
return score
1635 Number of Good Pairs (link)
Description
Given an array of integers nums, return the number of good pairs.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
pairs = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
if nums[i] == nums[j] and i < j:
pairs += 1
return pairs
2137 Final Value of Variable After Performing Operations (link)
Description
There is a programming language with only four operations and one variable X:
Given an array of strings operations containing a list of operations, return the final value of X after performing all the operations.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def finalValueAfterOperations(self, operations: List[str]) -> int:
X = 0
return X
3076 Get the Size of a DataFrame (link)
Description
DataFrame players:
+-------------+--------+
| Column Name | Type |
+-------------+--------+
| player_id | int |
| name | object |
| age | int |
| position | object |
| ... | ... |
+-------------+--------+
Write a solution to calculate and display the number of rows and columns of players.
Example 1:
Input:
+-----------+----------+-----+-------------+--------------------+
| player_id | name | age | position | team |
+-----------+----------+-----+-------------+--------------------+
| 846 | Mason | 21 | Forward | RealMadrid |
| 749 | Riley | 30 | Winger | Barcelona |
| 155 | Bob | 28 | Striker | ManchesterUnited |
| 583 | Isabella | 32 | Goalkeeper | Liverpool |
| 388 | Zachary | 24 | Midfielder | BayernMunich |
| 883 | Ava | 23 | Defender | Chelsea |
| 355 | Violet | 18 | Striker | Juventus |
| 247 | Thomas | 27 | Striker | ParisSaint-Germain |
| 761 | Jack | 33 | Midfielder | ManchesterCity |
| 642 | Charlie | 36 | Center-back | Arsenal |
+-----------+----------+-----+-------------+--------------------+
Output:
[10, 5]
Explanation:
This DataFrame contains 10 rows and 5 columns.
import pandas as pd
Description
DataFrame students
+-------------+--------+
| Column Name | Type |
+-------------+--------+
| id | int |
| first | object |
| last | object |
| age | int |
+-------------+--------+
id to student_id
first to first_name
last to last_name
age to age_in_years
Example 1:
Input:
+----+---------+----------+-----+
| id | first | last | age |
+----+---------+----------+-----+
| 1 | Mason | King | 6 |
| 2 | Ava | Wright | 7 |
| 3 | Taylor | Hall | 16 |
| 4 | Georgia | Thompson | 18 |
| 5 | Thomas | Moore | 10 |
+----+---------+----------+-----+
Output:
+------------+------------+-----------+--------------+
| student_id | first_name | last_name | age_in_years |
+------------+------------+-----------+--------------+
| 1 | Mason | King | 6 |
| 2 | Ava | Wright | 7 |
| 3 | Taylor | Hall | 16 |
| 4 | Georgia | Thompson | 18 |
| 5 | Thomas | Moore | 10 |
+------------+------------+-----------+--------------+
Explanation:
The column names are changed accordingly.
import pandas as pd
Description
DataFrame: employees
+-------------+--------+
| Column Name | Type |
+-------------+--------+
| employee_id | int |
| name | object |
| department | object |
| salary | int |
+-------------+--------+
Example 1:
Input:
DataFrame employees
+-------------+-----------+-----------------------+--------+
| employee_id | name | department | salary |
+-------------+-----------+-----------------------+--------+
| 3 | Bob | Operations | 48675 |
| 90 | Alice | Sales | 11096 |
| 9 | Tatiana | Engineering | 33805 |
| 60 | Annabelle | InformationTechnology | 37678 |
| 49 | Jonathan | HumanResources | 23793 |
| 43 | Khaled | Administration | 40454 |
+-------------+-----------+-----------------------+--------+
Output:
+-------------+---------+-------------+--------+
| employee_id | name | department | salary |
+-------------+---------+-------------+--------+
| 3 | Bob | Operations | 48675 |
| 90 | Alice | Sales | 11096 |
| 9 | Tatiana | Engineering | 33805 |
+-------------+---------+-------------+--------+
Explanation:
Only the first 3 rows are displayed.
import pandas as pd
Description
Write a function argumentsLength that returns the count of arguments passed to it.
Example 1:
Example 2:
Constraints:
/**
* @param {...(null|boolean|number|string|Array|Object)} args
* @return {number}
*/
var argumentsLength = function(...args) {
let count = 0;
for(let i=0; i<args.length; i++){
count++;
}
return count;
};
/**
* argumentsLength(1, 2, 3); // 3
*/
453 Minimum Moves to Equal Array Elements (link)
Description
Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.
Example 1:
Example 2:
Constraints:
n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109
The answer is guaranteed to fit in a 32-bit integer.
class Solution:
def minMoves(self, nums: List[int]) -> int:
Return the minimum number of operations to make all elements of nums divisible by 3.
Example 1:
Output: 3
Explanation:
Subtract 1 from 1.
Add 1 to 2.
Subtract 1 from 4.
Example 2:
Output: 0
Constraints:
class Solution {
public int minimumOperations(int[] nums) {
int count = 0;
for(int i: nums){
if(i % 3 != 0)count++;
}
return count;
}
}
3447 Clear Digits (link)
Description
You are given a string s.
Delete the first digit and the closest non-digit character to its left.
Note that the operation cannot be performed on a digit that does not have any non-digit character to its left.
Example 1:
Input: s = "abc"
Output: "abc"
Explanation:
Example 2:
Input: s = "cb34"
Output: ""
Explanation:
Constraints:
class Solution:
def clearDigits(self, s: str) -> str:
stack = []
for i in s:
if i.isnumeric():
stack.pop()
else:
stack.append(i)
return "".join(stack)
2732 Counter (link)
Description
Given an integer n, return a counter function. This counter function initially returns n and then returns 1 more than the previous value
every subsequent time it is called (n, n + 1, n + 2, etc).
Example 1:
Input:
n = 10
["call","call","call"]
Output: [10,11,12]
Explanation:
counter() = 10 // The first time counter() is called, it returns n.
counter() = 11 // Returns 1 more than the previous time.
counter() = 12 // Returns 1 more than the previous time.
Example 2:
Input:
n = -2
["call","call","call","call","call"]
Output: [-2,-1,0,1,2]
Explanation: counter() initially returns -2. Then increases after each sebsequent call.
Constraints:
/**
* @param {number} n
* @return {Function} counter
*/
var createCounter = function(n) {
return function() {
return n++;
};
};
/**
* const counter = createCounter(10)
* counter() // 10
* counter() // 11
* counter() // 12
*/
2809 Create Hello World Function (link)
Description
Write a function createHelloWorld. It should return a new function that always returns "Hello World".
Example 1:
Input: args = []
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f(); // "Hello World"
Example 2:
Any arguments could be passed to the function but it should still always return "Hello World".
Constraints:
/**
* @return {Function}
*/
var createHelloWorld = function() {
return function(...args) {
return "Hello World";
}
};
/**
* const f = createHelloWorld();
* f(); // "Hello World"
*/
1002 Maximum Width Ramp (link)
Description
A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.
Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.
Example 1:
Example 2:
Constraints:
class Solution:
def maxWidthRamp(self, nums: list[int]) -> int:
stack = []
# First, build a stack with indices of the array where the elements are in decreasing order.
for i in range(len(nums)):
if not stack or nums[i] < nums[stack[-1]]:
stack.append(i)
max_width = 0
# Now traverse from the end of the array and try to maximize the ramp width.
for j in range(len(nums) - 1, -1, -1):
while stack and nums[j] >= nums[stack[-1]]:
i = stack.pop()
max_width = max(max_width, j - i)
return max_width
409 Longest Palindrome (link)
Description
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with
those letters.
Letters are case sensitive, for example, "Aa" is not considered a palindrome.
Example 1:
Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
Example 2:
Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.
Constraints:
class Solution:
def longestPalindrome(self, s: str) -> int:
count = Counter(s)
max_len = 0
odd_found = False
# If any odd character count exists, we can add one extra character in the center
if odd_found:
max_len += 1
return max_len
32 Longest Valid Parentheses (link)
Description
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = ""
Output: 0
Constraints:
class Solution:
def longestValidParentheses(self, s: str) -> int:
for i in range(len(s)):
if s[i] == '(': # Push the index of '(' onto the stack
stack.append(i)
else: # When we encounter ')'
stack.pop() # Pop the last '(' index
if not stack:
stack.append(i) # If stack is empty, push the current index
else:
# Update max_len based on the length of the valid substring
max_len = max(max_len, i - stack[-1])
return max_len
957 Minimum Add to Make Parentheses Valid (link)
Description
A parentheses string is valid if and only if:
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 "())))".
Example 1:
Input: s = "())"
Output: 1
Example 2:
Input: s = "((("
Output: 3
Constraints:
class Solution:
def minAddToMakeValid(self, s: str) -> int:
if not s:
return 0
stack = []
close = 0
for i in s:
if i == "(":
stack.append(i)
elif i == ")":
if stack:
curr = stack.pop()
if curr == i:
stack.append(curr)
else:
close += 1
Description
You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing
brackets ']'.
You may swap the brackets at any two indices any number of times.
Example 1:
Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".
Example 2:
Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".
Example 3:
Input: s = "[]"
Output: 0
Explanation: The string is already balanced.
Constraints:
n == s.length
2 <= n <= 106
n is even.
s[i] is either '['
or ']'.
The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.
class Solution:
def minSwaps(self, s: str) -> int:
ans = 0
for c in s:
if c == '[':
ans += 1
elif ans > 0:
ans -= 1
return (ans + 1) // 2
2331 Intersection of Multiple Arrays (link)
Description
Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are
present in each array of nums sorted in ascending order.
Example 1:
Example 2:
Constraints:
class Solution:
def intersection(self, nums: List[List[int]]) -> List[int]:
# Start with a set of the first list
res = set(nums[0])
Description
Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.
Note that the integers in the lists may be returned in any order.
Example 1:
Example 2:
Constraints:
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
ans=[]
a1=set(nums1)-set(nums2)
ans.extend([a1])
a2=set(nums2)-set(nums1)
ans.extend([a2])
return ans
350 Intersection of Two Arrays II (link)
Description
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times
as it shows in both arrays and you may return the result in any order.
Example 1:
Example 2:
Constraints:
Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory
at once?
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1 = Counter(nums1)
nums2 = Counter(nums2)
res = []
for i in nums1:
if i in nums2:
minn = min(nums1[i], nums2[i])
for _ in range(minn):
res.append(i)
return res
349 Intersection of Two Arrays (link)
Description
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may
return the result in any order.
Example 1:
Example 2:
Constraints:
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = set()
nums2 = set(nums2)
for i in nums1:
if i in nums2:
res.add(i)
return list(res)
2800 Minimum String Length After Removing Substrings (link)
Description
You are given a string s consisting only of uppercase English letters.
You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or
"CD" from s.
Return the minimum possible length of the resulting string that you can obtain.
Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.
Example 1:
Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.
Example 2:
Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.
Constraints:
class Solution:
def minLength(self, s: str) -> int:
stack = []
for i in s:
if not stack:
stack.append(i)
return len(stack)
1923 Sentence Similarity III (link)
Description
You are given two strings sentence1 and sentence2, each representing a sentence composed of words. A sentence is a list of words
that are separated by a single space with no leading or trailing spaces. Each word consists of only uppercase and lowercase English
characters.
Two sentences s1 and s2 are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these
sentences such that the two sentences become equal. Note that the inserted sentence must be separated from existing words by
spaces.
For example,
s1 = "Hello Jane" and s2 = "Hello my name is Jane" can be made equal by inserting "my name is" between "Hello" and "Jane" in
s1.
s1 = "Frog cool" and s2 = "Frogs are cool" are not similar, since although there is a sentence "s are" inserted into s1, it is not
separated from "Frog" by a space.
Given two sentences sentence1 and sentence2, return true if sentence1 and sentence2 are similar. Otherwise, return false.
Example 1:
Output: true
Explanation:
sentence2 can be turned to sentence1 by inserting "name is" between "My" and "Haley".
Example 2:
Output: false
Explanation:
No single sentence can be inserted inside one of the sentences to make it equal to the other.
Example 3:
Output: true
Explanation:
sentence2 can be turned to sentence1 by inserting "right now" at the end of the sentence.
Constraints:
class Solution:
def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
# Split the sentences into words
words1 = sentence1.split()
words2 = sentence2.split()
start, end = 0, 0
n1, n2 = len(words1), len(words2)
Description
Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
count = 0
tot2 = defaultdict(int)
return count
18 4Sum (link)
Description
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
Example 1:
Example 2:
Constraints:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
N = 4
if len(nums) < N:
return []
result = []
nums = sorted(nums)
helperSum(nums, target, [])
return result
16 3Sum Closest (link)
Description
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
You may assume that each input would have exactly one solution.
Example 1:
Example 2:
Constraints:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
closest = 0
minDiff = float("inf")
else:
k -= 1
Description
Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of
ones in that row.
In case there are multiple rows that have the maximum count of ones, the row with the smallest row number should be selected.
Return an array containing the index of the row, and the number of ones in it.
Example 1:
Example 2:
Example 3:
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.
class Solution:
def rowAndMaximumOnes(self, mat: List[List[int]]) -> List[int]:
a = 0
b = 0
for i in range(len(mat)):
if mat[i].count(1) > a:
a = mat[i].count(1)
b = i
return(b,a)
240 Search a 2D Matrix II (link)
Description
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Example 1:
Example 2:
Constraints:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-109 <= target <= 109
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == target:
return True
return False
74 Search a 2D Matrix (link)
Description
You are given an m x n integer matrix matrix with the following two properties:
Example 1:
Example 2:
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix)
m = len(matrix[0])
Description
You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n
/ 2 teams of size 2 such that the total skill of each team is equal.
The chemistry of a team is equal to the product of the skills of the players on that team.
Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill
of each team is equal.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def dividePlayers(self, skill: List[int]) -> int:
# Sort the skill array to pair the weakest with the strongest
skill.sort()
return chemistry
1620 Check If Array Pairs Are Divisible by k (link)
Description
Given an array of integers arr of even length n and an integer k.
We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.
Example 1:
Example 2:
Example 3:
Constraints:
arr.length == n
1 <= n <= 105
n is even.
-109 <= arr[i] <= 109
1 <= k <= 105
class Solution:
def canArrange(self, arr: List[int], k: int) -> bool:
freq = [0] * k
if freq[0] % 2 != 0:
return False
return True
80 Remove Duplicates from Sorted Array II (link)
Description
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element
appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part
of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the
final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Custom Judge:
The judge will test your solution with the following code:
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
Example 1:
Example 2:
Constraints:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 2
return k
46 Permutations (link)
Description
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 1:
return [nums[:]]
res = []
for _ in range(len(nums)):
n = nums.pop(0)
perms = self.permute(nums)
for p in perms:
p.append(n)
res.extend(perms)
nums.append(n)
return res
1256 Rank Transform of an Array (link)
Description
Given an array of integers arr, replace each element with its rank.
The rank represents how large the element is. The rank has the following rules:
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
hashSet = {}
for i, r in enumerate(sorted(set(arr))):
if r not in hashSet:
hashSet[r] = i + 1
Description
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the
values along the path equals targetSum.
Example 1:
Example 2:
Example 3:
Constraints:
Description
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
if n==1 or n==0:return n
length = 0
l = 0
r = 1
while(r<n):
patt = str(s[l])
k = r
while(k<n and s[k] not in patt):
patt += s[k]
k+=1
l = r
r = l+1
return length
11 Container With Most Water (link)
Description
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0)
and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Example 1:
Example 2:
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
max_area = 0
return max_area
1497 Design a Stack With Increment Operation (link)
Description
Design a stack that supports increment operations on its elements.
CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack.
void push(int x) Adds x to the top of the stack if the stack has not reached the maxSize.
int pop() Pops and returns the top of the stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack,
increment all the elements in the stack.
Example 1:
Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack stk = new CustomStack(3); // Stack is Empty []
stk.push(1); // stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.pop(); // return 2 --> Return top of the stack 2, stack becomes [1]
stk.push(2); // stack becomes [1, 2]
stk.push(3); // stack becomes [1, 2, 3]
stk.push(4); // stack still [1, 2, 3], Do not add another elements as size is 4
stk.increment(5, 100); // stack becomes [101, 102, 103]
stk.increment(2, 100); // stack becomes [201, 202, 103]
stk.pop(); // return 103 --> Return top of the stack 103, stack becomes [201, 202]
stk.pop(); // return 202 --> Return top of the stack 202, stack becomes [201]
stk.pop(); // return 201 --> Return top of the stack 201, stack becomes []
stk.pop(); // return -1 --> Stack is empty return -1.
Constraints:
class CustomStack:
self.stack[i] += val
Description
Your laptop keyboard is faulty, and whenever you type a character 'i' on it, it reverses the string that you have written. Typing other
characters works as expected.
You are given a 0-indexed string s, and you type each character of s using your faulty keyboard.
Return the final string that will be present on your laptop screen.
Example 1:
Input: s = "string"
Output: "rtsng"
Explanation:
After typing first character, the text on the screen is "s".
After the second character, the text is "st".
After the third character, the text is "str".
Since the fourth character is an 'i', the text gets reversed and becomes "rts".
After the fifth character, the text is "rtsn".
After the sixth character, the text is "rtsng".
Therefore, we return "rtsng".
Example 2:
Input: s = "poiinter"
Output: "ponter"
Explanation:
After the first character, the text on the screen is "p".
After the second character, the text is "po".
Since the third character you type is an 'i', the text gets reversed and becomes "op".
Since the fourth character you type is an 'i', the text gets reversed and becomes "po".
After the fifth character, the text is "pon".
After the sixth character, the text is "pont".
After the seventh character, the text is "ponte".
After the eighth character, the text is "ponter".
Therefore, we return "ponter".
Constraints:
class Solution:
def finalString(self, s: str) -> str:
res = ""
for i in s:
if i == "i":
res = res[::-1]
else:
res += i
return res
345 Reverse Vowels of a String (link)
Description
Given a string s, reverse only all the vowels in the string and return it.
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.
Example 1:
Input: s = "IceCreAm"
Output: "AceCreIm"
Explanation:
The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".
Example 2:
Input: s = "leetcode"
Output: "leotcede"
Constraints:
class Solution:
def reverseVowels(self, s: str) -> str:
l = 0
r = len(s) - 1
x = list(s)
vow = "aeiouAEIOU"
return "".join(x)
344 Reverse String (link)
Description
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
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:
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s) - 1
left += 1
right -= 1
19 Remove Nth Node From End of List (link)
Description
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Example 2:
Example 3:
Constraints:
fastPntr = head
for i in range(n):
fastPntr = fastPntr.next
curr = head
while(fastPntr and fastPntr.next):
curr = curr.next
fastPntr = fastPntr.next
if curr is head:
if not fastPntr:
return head.next
curr.next = curr.next.next
return head
1 Two Sum (link)
Description
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example 1:
Example 2:
Example 3:
Constraints:
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashMap = {}
for i in range(len(nums)):
diff = target - nums[i]
if diff in hashMap:
return [i, hashMap[diff]]
else:
hashMap[nums[i]] = i
20 Valid Parentheses (link)
Description
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Constraints:
class Solution:
def isValid(self, s: str) -> bool:
stack = []
closeToOpen = {")": "(", "]": "[", "}": "{"}
for c in s:
# check if c is closing bracket
if c in closeToOpen:
# check if character on top of stack is matching opening bracket
if stack and stack[-1] == closeToOpen[c]:
stack.pop()
else:
return False
else:
stack.append(c)
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.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution {
public int thirdMax(int[] nums) {
Integer max1 = null;
Integer max2 = null;
Integer max3 = null;
for(Integer n : nums){
if(n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
if(max1 == null || n>max1){
max3 = max2;
max2 = max1;
max1 = n;
}
else if(max2 == null || n > max2){
max3 = max2;
max2 = n;
}
else if(max3 == null || n > max3){
max3 = n;
}
}
return max3 == null ? max1 : max3;
}
}
1848 Sum of Unique Elements (link)
Description
You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def sumOfUnique(self, nums: List[int]) -> int:
seen = set()
dup = set()
summ = 0
for i in nums:
if i not in seen:
summ += i
seen.add(i)
return max(summ, 0)
1476 Count Negative Numbers in a Sorted Matrix (link)
Description
Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative
numbers in grid.
Example 1:
Example 2:
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
pos = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] < 0:
pos += 1
return pos
2614 Maximum Count of Positive Integer and Negative Integer (link)
Description
Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of
negative integers.
In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the
maximum of pos and neg.
Example 1:
Example 2:
Example 3:
Constraints:
Follow up: Can you solve the problem in O(log(n)) time complexity?
class Solution:
def maximumCount(self, nums: List[int]) -> int:
pos = 0
neg = 0
i = 0
while(i < len(nums)):
if nums[i] < 0:
neg += 1
if nums[i] > 0:
pos += 1
i += 1
Description
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If
target exists, then return its index. Otherwise, return -1.
Example 1:
Example 2:
Constraints:
class Solution {
public int search(int[] nums, int target) {
int L = 0;
int R = nums.length - 1;
Description
The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.
For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.
Example 1:
Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
Constraints:
class Solution:
def findComplement(self, num: int) -> int:
a=bin(num)[2:]
b=[]
for i in a:
if i=='1':
b.append('0')
else:
b.append('1')
c="".join(b)
return int(c,2)
225 Implement Stack using Queues (link)
Description
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal
stack (push, top, pop, and empty).
Notes:
You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty
operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-
ended queue) as long as you use only a queue's standard operations.
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
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.
Follow-up: Can you implement the stack using only one queue?
class MyStack:
def __init__(self):
self.stack = []
Description
Given an integer array 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:
Example 2:
Example 3:
Constraints:
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
left = 0
seen = set()
return False
2551 Apply Operations to an Array (link)
Description
You are given a 0-indexed array nums of size n consisting of non-negative integers.
You need to apply n - 1 operations to this array where, in the ith operation (0-indexed), you will apply the following on the ith element
of nums:
If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation.
After performing all the operations, shift all the 0's to the end of the array.
For example, the array [1,0,2,0,0,1] after shifting all its 0's to the end, is [1,2,1,0,0,0].
Note that the operations are applied sequentially, not all at once.
Example 1:
Example 2:
Constraints:
class Solution:
def applyOperations(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(1,n):
if nums[i] == nums[i - 1]:
nums[i-1] *= 2
nums[i] = 0
left = 0
i = 0
while(i < n):
if nums[i] != 0:
nums[left], nums[i] = nums[i], nums[left]
left += 1
i += 1
return nums
283 Move Zeroes (link)
Description
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Example 2:
Constraints:
Follow up: Could you minimize the total number of operations done?
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return
left = 0
for right in range(len(nums)):
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
268 Missing Number (link)
Description
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the
array.
Example 1:
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear
in nums.
Example 2:
Output: 2
Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear
in nums.
Example 3:
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear
in nums.
Constraints:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int summ = n * (n + 1) / 2;
int nums_sum = 0;
for(int i: nums){
nums_sum += i;
}
Description
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal
queue (push, peek, pop, and empty).
Notes:
You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty
operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-
ended queue) as long as you use only a stack's standard operations.
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
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.
Follow-up: 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.
class MyQueue:
def __init__(self):
self.stack = []
Description
Table: Customers
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| id | int |
| name | varchar |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table indicates the ID and name of a customer.
Table: Orders
+-------------+------+
| Column Name | Type |
+-------------+------+
| id | int |
| customerId | int |
+-------------+------+
id is the primary key (column with unique values) for this table.
customerId is a foreign key (reference columns) of the ID from the Customers table.
Each row of this table indicates the ID of an order and the ID of the customer who ordered it.
Example 1:
Input:
Customers table:
+----+-------+
| id | name |
+----+-------+
| 1 | Joe |
| 2 | Henry |
| 3 | Sam |
| 4 | Max |
+----+-------+
Orders table:
+----+------------+
| id | customerId |
+----+------------+
| 1 | 3 |
| 2 | 1 |
+----+------------+
Output:
+-----------+
| Customers |
+-----------+
| Henry |
| Max |
+-----------+
Description
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search
tree.
Example 1:
Example 2:
Input: head = []
Output: []
Constraints:
if not head:return
arr = []
curr = head
while curr:
arr.append(curr.val)
curr = curr.next
mid = (l + r) // 2
root = TreeNode(arr[mid])
return root
Description
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D
matrix and do the rotation.
Example 1:
Example 2:
Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
size = len(matrix)
for i in range(size):
for j in range(i+1, size):
matrix[j][i],matrix[i][j] = matrix[i][j],matrix[j][i]
for i in range(len(matrix)):
matrix[i].reverse()
108 Convert Sorted Array to Binary Search Tree (link)
Description
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Example 1:
Example 2:
Constraints:
# [-10, -3, 0, 5, 9]
return root
920 Uncommon Words from Two Sentences (link)
Description
A sentence is a string of single-space separated words where each word consists only of lowercase letters.
A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.
Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order.
Example 1:
Output: ["sweet","sour"]
Explanation:
The word "sweet" appears only in s1, while the word "sour" appears only in s2.
Example 2:
Output: ["banana"]
Constraints:
class Solution:
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
s1 = s1.split(" ")
s2 = s2.split(" ")
res = set()
for i in range(len(s1)):
if s1[i] not in s2 and s1[i] not in s1[:i] + s1[i+1:]:
res.add(s1[i])
for i in range(len(s2)):
if s2[i] not in s1 and s2[i] not in s2[:i] + s2[i+1:]:
res.add(s2[i])
return list(res)
817 Design HashMap (link)
Description
Design a HashMap without using any built-in hash table libraries.
Example 1:
Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]
Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
Constraints:
class MyHashMap:
def __init__(self):
self.hashMap = {}
Description
Design a HashSet without using any built-in hash table libraries.
Example 1:
Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]
Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // return False, (already removed)
Constraints:
class MyHashSet:
def __init__(self):
self.hashSet = {}
Description
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
int length = 1;
ListNode tail = head;
while(tail.next != null){
length++;
tail = tail.next;
}
k = k % length;
if(k == 0)return head;
return new_head;
}
}
3567 Convert Date to Binary (link)
Description
You are given a string date representing a Gregorian calendar date in the yyyy-mm-dd format.
date can be written in its binary representation obtained by converting year, month, and day to their binary representations without any
leading zeroes and writing them down in year-month-day format.
Example 1:
Output: "100000100000-10-11101"
Explanation:
100000100000, 10, and 11101 are the binary representations of 2080, 02, and 29 respectively.
Example 2:
Output: "11101101100-1-1"
Explanation:
Constraints:
date.length == 10
date[4] == date[7] == '-',and all other date[i]'s are digits.
The input is generated such that date represents a valid Gregorian calendar date between Jan 1st, 1900 and Dec 31st, 2100
(both inclusive).
class Solution:
Description
You are given a 0-indexed integer array nums having length n, an integer indexDifference, and an integer valueDifference.
Your task is to find two indices i and j, both in the range [0, n - 1], that satisfy the following conditions:
Return an integer array answer, where answer = [i, j] if there are two such indices, and answer = [-1, -1] otherwise. If there are
multiple choices for the two indices, return any of them.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:
n = len((nums))
for i in range(n):
for j in range(n):
Description
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no
intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
listA - The first linked list.
listB - The second linked list.
skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you
correctly return the intersected node, then your solution will be accepted.
Example 1:
Example 2:
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, i
Explanation: The two lists do not intersect, so return null.
Constraints:
Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
node_a = headA
node_b = headB
count_a, count_b = 0, 0
while node_a or node_b:
if node_a:
count_a += 1
node_a = node_a.next
if node_b:
count_b += 1
node_b = node_b.next
node_a = headA
node_b = headB
if count_a > count_b:
#print("a is longer")
while count_diff > 0:
node_a = node_a.next
count_diff -= 1
elif count_b > count_a:
#print("b is longer")
while count_diff > 0:
node_b = node_b.next
count_diff -= 1
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:
Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Example 2:
Input: numRows = 1
Output: [[1]]
Constraints:
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
temp = []
for j in range(i+1):
if j == 0 or j == i:
temp.append(1)
else:
temp.append(res[i-1][j] + res[i-1][j-1])
res.append(temp)
return res
451 Sort Characters By Frequency (link)
Description
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of
times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Example 1:
Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
Constraints:
class Solution:
def frequencySort(self, s: str) -> str:
freq = Counter(s)
return res
2594 Count Pairs Of Similar Strings (link)
Description
You are given a 0-indexed string array words.
For example, "abca" and "cba" are similar since both consist of characters 'a', 'b', and 'c'.
However, "abacba" and "bcfd" are not similar since they do not consist of the same characters.
Return the number of pairs (i, j) such that 0 <= i < j <= word.length - 1 and the two strings words[i] and words[j] are similar.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def similarPairs(self, words: List[str]) -> int:
hashMap = {}
count = 0
for i in words:
char = ''.join(sorted(set(i)))
if char in hashMap:
count += hashMap[char]
hashMap[char] += 1
else:
hashMap[char] = 1
return count
1786 Count the Number of Consistent Strings (link)
Description
You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in
the string appear in the string allowed.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
allowed = set(allowed)
count = 0
for i in words:
temp = True
for j in i:
if j not in allowed:
temp = False
break
if temp:
count += 1
return count
56 Merge Intervals (link)
Description
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-
overlapping intervals that cover all the intervals in the input.
Example 1:
Example 2:
Constraints:
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1)
return intervals;
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.
Example 2:
Input: num = 0
Output: 0
Constraints:
class Solution:
def addDigits(self, num: int) -> int:
if num <= 9:
return num
return (num - 1) % 9 + 1
202 Happy Number (link)
Description
Write an algorithm to determine if a number n is happy.
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
1 2 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Constraints:
class Solution:
def isHappy(self, n: int) -> bool:
hashSet = set()
curr = str(n)
if summ == 1:
return True
curr = str(summ)
return False
242 Valid Anagram (link)
Description
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Output: true
Example 2:
Output: false
Constraints:
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s_count = Counter(s)
t_count = Counter(t)
Description
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater
than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Example 2:
Example 3:
Constraints:
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:
i = 0
min_len = float('inf')
summ = 0
for j in range(len(nums)):
summ += nums[j]
Description
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] +
nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # Sort the array to use two-pointer technique
n = len(nums)
answer = set()
for i in range(n):
# If the current number is greater than 0, no triplet can sum to 0
if nums[i] > 0:
break
low, high = i + 1, n - 1
low += 1
high -= 1
return list(answer)
290 Word Pattern (link)
Description
Given a 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 non-empty word in s. Specifically:
Example 1:
Output: true
Explanation:
Example 2:
Output: false
Example 3:
Output: false
Constraints:
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
hashMap = {}
s = s.split(" ")
if len(s) != len(pattern):return False
j = 0
for i in pattern:
if i not in hashMap:
if s[j] in hashMap.values():
return False
hashMap[i] = s[j]
else:
if hashMap[i] != s[j]:
return False
j += 1
return True
6 Zigzag Conversion (link)
Description
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a
fixed font for better legibility)
P A H N
A P L S I I G
Y I R
Write the code that will take a string and make this conversion given a number of rows:
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows <= 1:
return s
V = [""] * numRows
direction = (numRows==1)-1
k = 0
for i in s:
V[k] += i
if k==0 or k==numRows-1:
direction *= -1
k+=direction
return ''.join(V)
228 Summary Ranges (link)
Description
You are given a sorted unique integer array nums.
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered
by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
"a->b" if a != b
"a" if a == b
Example 1:
Example 2:
Constraints:
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
ans = []
i = 0
while i < len(nums):
start = nums[i]
if start == nums[i]:
ans.append(f"{start}")
else:
ans.append(f"{start}->{nums[i]}")
i+=1
return ans
119 Pascal's Triangle II (link)
Description
Given an integer rowIndex, return the rowIndexth (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:
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0
Output: [1]
Example 3:
Input: rowIndex = 1
Output: [1,1]
Constraints:
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = []
for i in range(rowIndex+1):
temp = []
for j in range(i+1):
if j==0 or j==i:
temp.append(1)
else:
temp.append(res[j] + res[j-1])
res = temp
return res
54 Spiral Matrix (link)
Description
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Example 2:
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
left , right = 0, len(matrix[0])
top, bottom = 0, len(matrix)
return res
725 Split Linked List in Parts (link)
Description
Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.
The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to
some parts being null.
The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or
equal to parts occurring later.
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode[]}
*/
// Definition for singly-linked list.
var splitListToParts = function(root, k) {
// Create an array of ListNode pointers to store the k parts.
const parts = new Array(k).fill(null);
// Calculate the minimum guaranteed part size (n) and the number of extra nodes (r).
const n = Math.floor(len / k);
let r = len % k;
// Disconnect the current part from the rest of the list by setting prev.next to null.
if (prev) {
prev.next = null;
}
}
Description
You are given an array prices where prices[i] is the price of a given stock on the ith 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:
Example 2:
Constraints:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = prices[0]
max_profit = 0
for i in prices:
if(i < min_price):
min_price = i
profit = i - min_price
return max_profit
2216 Delete the Middle Node of a Linked List (link)
Description
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest
integer less than or equal to x.
Example 1:
Example 2:
Example 3:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteMiddle(ListNode head) {
if(head == null || head.next == null)return null;
fastPntr = fastPntr.next.next;
slowPntr = slowPntr.next;
}
slowPntr.next = slowPntr.next.next;
return head;
}
}
205 Isomorphic Strings (link)
Description
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters
may map to the same character, but a character may map to itself.
Example 1:
Output: true
Explanation:
Example 2:
Output: false
Explanation:
The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.
Example 3:
Output: true
Constraints:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_t = {}
t_s = {}
for i in range(len(s)):
char_s = s[i]
char_t = t[i]
if char_s in s_t:
if s_t[char_s] != char_t:
return False
if char_t in t_s:
if t_s[char_t] != char_s:
return False
s_t[char_s] = char_t
t_s[char_t] = char_s
return True
1827 Invalid Tweets (link)
Description
Table: Tweets
+----------------+---------+
| Column Name | Type |
+----------------+---------+
| tweet_id | int |
| content | varchar |
+----------------+---------+
tweet_id is the primary key (column with unique values) for this table.
content consists of alphanumeric characters, '!', or ' ' and no other special characters.
This table contains all the tweets in a social media app.
Write a solution to find the IDs of the invalid tweets. The tweet is invalid if the number of characters used in the content of the tweet is
strictly greater than 15.
Example 1:
Input:
Tweets table:
+----------+-----------------------------------+
| tweet_id | content |
+----------+-----------------------------------+
| 1 | Let us Code |
| 2 | More than fifteen chars are here! |
+----------+-----------------------------------+
Output:
+----------+
| tweet_id |
+----------+
| 2 |
+----------+
Explanation:
Tweet 1 has length = 11. It is a valid tweet.
Tweet 2 has length = 33. It is an invalid tweet.
Description
Table: Views
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| article_id | int |
| author_id | int |
| viewer_id | int |
| view_date | date |
+---------------+---------+
There is no primary key (column with unique values) for this table, the table may have duplicate rows.
Each row of this table indicates that some viewer viewed an article (written by some author) on some date.
Note that equal author_id and viewer_id indicate the same person.
Write a solution to find all the authors that viewed at least one of their own articles.
Example 1:
Input:
Views table:
+------------+-----------+-----------+------------+
| article_id | author_id | viewer_id | view_date |
+------------+-----------+-----------+------------+
| 1 | 3 | 5 | 2019-08-01 |
| 1 | 3 | 6 | 2019-08-02 |
| 2 | 7 | 7 | 2019-08-01 |
| 2 | 7 | 6 | 2019-08-02 |
| 4 | 7 | 1 | 2019-07-22 |
| 3 | 4 | 4 | 2019-07-21 |
| 3 | 4 | 4 | 2019-07-21 |
+------------+-----------+-----------+------------+
Output:
+------+
| id |
+------+
| 4 |
| 7 |
+------+
Description
Table: World
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| name | varchar |
| continent | varchar |
| area | int |
| population | int |
| gdp | bigint |
+-------------+---------+
name is the primary key (column with unique values) for this table.
Each row of this table gives information about the name of a country, the continent to which it belongs, its area, the population, a
Write a solution to find the name, population, and area of the big countries.
Example 1:
Input:
World table:
+-------------+-----------+---------+------------+--------------+
| name | continent | area | population | gdp |
+-------------+-----------+---------+------------+--------------+
| Afghanistan | Asia | 652230 | 25500100 | 20343000000 |
| Albania | Europe | 28748 | 2831741 | 12960000000 |
| Algeria | Africa | 2381741 | 37100000 | 188681000000 |
| Andorra | Europe | 468 | 78115 | 3712000000 |
| Angola | Africa | 1246700 | 20609294 | 100990000000 |
+-------------+-----------+---------+------------+--------------+
Output:
+-------------+------------+---------+
| name | population | area |
+-------------+------------+---------+
| Afghanistan | 25500100 | 652230 |
| Algeria | 37100000 | 2381741 |
+-------------+------------+---------+
Description
Table: Products
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| product_id | int |
| low_fats | enum |
| recyclable | enum |
+-------------+---------+
product_id is the primary key (column with unique values) for this table.
low_fats is an ENUM (category) of type ('Y', 'N') where 'Y' means this product is low fat and 'N' means it is not.
recyclable is an ENUM (category) of types ('Y', 'N') where 'Y' means this product is recyclable and 'N' means it is not.
Write a solution to find the ids of products that are both low fat and recyclable.
Example 1:
Input:
Products table:
+-------------+----------+------------+
| product_id | low_fats | recyclable |
+-------------+----------+------------+
| 0 | Y | N |
| 1 | Y | Y |
| 2 | N | Y |
| 3 | Y | Y |
| 4 | N | N |
+-------------+----------+------------+
Output:
+-------------+
| product_id |
+-------------+
| 1 |
| 3 |
+-------------+
Explanation: Only products 1 and 3 are both low fat and recyclable.
Description
Table: Customer
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| id | int |
| name | varchar |
| referee_id | int |
+-------------+---------+
In SQL, id is the primary key column for this table.
Each row of this table indicates the id of a customer, their name, and the id of the customer who referred them.
Find the names of the customer that are not referred by the customer with id = 2.
Example 1:
Input:
Customer table:
+----+------+------------+
| id | name | referee_id |
+----+------+------------+
| 1 | Will | null |
| 2 | Jane | null |
| 3 | Alex | 2 |
| 4 | Bill | null |
| 5 | Zack | 1 |
| 6 | Mark | 2 |
+----+------+------------+
Output:
+------+
| name |
+------+
| Will |
| Jane |
| Bill |
| Zack |
+------+
Description
Given the head of a linked list head, in which each node contains an integer value.
Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.
The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
while(nextNode != null){
ListNode dummy = current;
ListNode gcd = new ListNode(gcd(current.val, nextNode.val));
// current = current.next;
// nextNode = nextNode.next;
current.next = gcd;
gcd.next = nextNode;
// dummy.next = gcd;
// gcd.next = current;
current = nextNode;
nextNode = nextNode.next;
}
return head;
}
}
680 Valid Palindrome II (link)
Description
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = "aba"
Output: true
Example 2:
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Example 3:
Input: s = "abc"
Output: false
Constraints:
class Solution {
public:
bool isPalindrome(string s, int left, int right){
while(left < right){
if(s[left] != s[right]){
return false;
}
left++;
right--;
}
return true;
}
bool validPalindrome(string s) {
int left = 0;
int right = s.length() - 1;
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.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
left++;
right--;
}
return true;
}
}
203 Remove Linked List Elements (link)
Description
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new
head.
Example 1:
Example 2:
Example 3:
Constraints:
curr = dummy
while curr and curr.next:
if curr.next.val == val:
# Skip the node with the matching value
curr.next = curr.next.next
else:
# Move to the next node
curr = curr.next
return dummy.next
234 Palindrome Linked List (link)
Description
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Example 2:
Constraints:
# (Optional) Restore the list if you need to keep the original structure
# Reverse the second half again
return True
206 Reverse Linked List (link)
Description
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Example 2:
Example 3:
Input: head = []
Output: []
Constraints:
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
Description
Given a binary tree root and a linked list with head as the first node.
Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary
tree otherwise return False.
In this context downward path means a path that starts at some node and goes downwards.
Example 1:
Example 2:
Example 3:
Constraints:
The number of nodes in the tree will be in the range [1, 2500].
The number of nodes in the list will be in the range [1, 100].
1 <= Node.val <= 100 for each node in the linked list and binary tree.
Description
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Example 2:
Constraints:
return dfs(root, 0)
222 Count Complete Tree Nodes (link)
Description
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last
level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example 1:
Example 2:
Input: root = []
Output: 0
Example 3:
Constraints:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
Description
Given an integer x, return true if x is a palindrome, and false otherwise.
Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Constraints:
Follow up: Could you solve it without converting the integer to a string?
class Solution {
public boolean isPalindrome(int x) {
if(x<0)return false;
int res = 0;
int temp = x;
while(temp>0){
int last = temp % 10;
res = res *10 +last;
temp = temp / 10;
}
return(res == x);
}
}
42 Trapping Rain Water (link)
Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap
after raining.
Example 1:
Example 2:
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
class Solution {
public int trap(int[] height) {
if (height.length < 3) return 0;
int tallest = 0;
for (int i = 1; i < height.length; i++)
if (height[tallest] < height[i]) tallest = i;
int water = 0;
for (int i = 0, tall = 0; i < tallest; i++) {
if (tall < height[i]) tall = height[i];
else water += tall - height[i];
}
for (int i = height.length - 1, tall = 0; i > tallest; i--) {
if (tall < height[i]) tall = height[i];
else water += tall - height[i];
}
return water;
}
}
13 Roman to Integer (link)
Description
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The
number 27 is written as XXVII, which is XX + 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 as IV. Because the one is before the five we subtract it making four. The same principle applies to the number
nine, which is written as IX. There are six instances where subtraction is used:
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
class Solution:
def romanToInt(self, s: str) -> int:
for i in range(len(s)):
# check if there is a "next value" (i + 1)
# if there is then check if the next value is greater than the previous
if i + 1 < len(s) and roman[s[i]] < roman[s[i+1]]:
# if the previous value is less, we subtract that value from the result
result -= roman[s[i]]
# otherwise we add it to our result
else:
result += roman[s[i]]
# we return the result we find
return result
167 Two Sum II - Input Array Is Sorted (link)
Description
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up
to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <=
numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
Description
Seven different symbols represent Roman numerals with the following values:
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal
place value into a Roman numeral has the following rules:
If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that
symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for
example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9
(IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append
5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
Example 1:
Output: "MMMDCCXLIX"
Explanation:
Example 2:
Input: num = 58
Output: "LVIII"
Explanation:
50 = L
8 = VIII
Example 3:
Output: "MCMXCIV"
Explanation:
1000 = M
900 = CM
90 = XC
4 = IV
Constraints:
class Solution {
public static String intToRoman(int num) {
String M[] = {"", "M", "MM", "MMM"};
String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}
}
238 Product of Array Except Self (link)
Description
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Example 2:
Constraints:
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space
complexity analysis.)
class Solution:
def productExceptSelf( nums: List[int]) -> List[int]:
n = len(nums)
left = [0]*n
right = [0]*n
left_mul,right_mul = 1,1
for i in range(n):
j = -i-1
left[i] = left_mul
right[j] = right_mul
left_mul *= nums[i]
right_mul *= nums[j]
f = open('user.out', 'w')
for i in stdin:
nums = list(map(int,i.rstrip()[1:-1].split(r',')))
print(str(productExceptSelf(nums)).replace(" ", ""), file=f)
exit(0)
392 Is Subsequence (link)
Description
Given two strings s and t, return true if s is a subsequence of t, or false 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).
Example 1:
Example 2:
Constraints:
Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has
its subsequence. In this scenario, how would you change your code?
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = j = 0
while(i < len(s) and j < len(t)):
if s[i] == t[j]:
i += 1
j += 1
else:
j+=1
Description
Given an alphanumeric string s, return the second largest numerical digit that appears in s, or -1 if it does not exist.
Example 1:
Input: s = "dfa12321afd"
Output: 2
Explanation: The digits that appear in s are [1, 2, 3]. The second largest digit is 2.
Example 2:
Input: s = "abc1111"
Output: -1
Explanation: The digits that appear in s are [1]. There is no second largest digit.
Constraints:
class Solution:
def secondHighest(self, s: str) -> int:
nums = set()
for i in s:
if i.isdigit():
nums.add(i)
print(nums)
nums = sorted(nums)
if len(nums) <=1:
return -1
return int(nums[-2])
1927 Maximum Ascending Subarray Sum (link)
Description
Given an array of positive integers nums, return the maximum possible sum of an strictly increasing subarray in nums.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution {
public int maxAscendingSum(int[] nums) {
int max_sum = 0;
int curr_sum = nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i] > nums[i-1]){
curr_sum += nums[i];
}
else{
max_sum = Math.max(curr_sum, max_sum);
curr_sum = nums[i];
}
}
return Math.max(curr_sum, max_sum);
}
}
2058 Concatenation of Array (link)
Description
Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i]
for 0 <= i < n (0-indexed).
Example 1:
Example 2:
Constraints:
n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000
class Solution {
public int[] getConcatenation(int[] nums) {
int n = nums.length;
int[] nums2 = new int[2*n];
}
}
4 Median of Two Sorted Arrays (link)
Description
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
Example 1:
Example 2:
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
# arr = []
# nums1 = deque(nums1)
# nums2 = deque(nums2)
# arr.extend(nums1)
# arr.extend(nums2)
Description
Given a binary array nums, return the maximum number of consecutive 1's in the array.
Example 1:
Example 2:
Constraints:
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
maximum = 0
current = 0
for i in range(len(nums)):
if nums[i] == 1:
current += 1
else:
maximum = max(maximum , current)
current = 0
Description
Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming
weight).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
Example 2:
Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
Constraints:
Follow up: If this function is called many times, how would you optimize it?
class Solution:
def hammingWeight(self, n: int) -> int:
binary = str(bin(n))[2:]
ones = 0
for i in binary:
if i == '1':
ones += 1
return ones
142 Linked List Cycle II (link)
Description
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle.
Note that pos is not passed as a parameter.
Example 1:
Example 2:
Example 3:
Constraints:
The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return
slow_pntr = head
fast_pntr = head
if (slow_pntr == fast_pntr):
break
else:
return
detect_cycle = head
while(detect_cycle != slow_pntr):
detect_cycle = detect_cycle.next
slow_pntr = slow_pntr.next
return detect_cycle
137 Single Number II (link)
Description
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single
element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Example 2:
Constraints:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hashMap = {}
for i in nums:
if i in hashMap:
hashMap[i] += 1
else:
hashMap[i] = 1
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.
Example 1:
Output: 1
Example 2:
Output: 4
Example 3:
Output: 1
Constraints:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
single_number = 0
for num in nums:
single_number ^= num
return single_number
141 Linked List Cycle (link)
Description
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a
parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Example 2:
Example 3:
Constraints:
The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow_pntr = head;
ListNode fast_pntr = head;
if(slow_pntr == fast_pntr){
return true;
}
}
return false;
}
}
145 Binary Tree Postorder Traversal (link)
Description
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Output: [3,2,1]
Explanation:
Example 2:
Output: [4,6,7,5,2,9,8,3,1]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Output: [1]
Constraints:
The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
res = []
_postOrderTraversal(root, res)
return res
144 Binary Tree Preorder Traversal (link)
Description
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Output: [1,2,3]
Explanation:
Example 2:
Output: [1,2,4,5,6,7,3,8,9]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Output: [1]
Constraints:
res = []
_preOrderTraversal(root, res)
return res
1894 Merge Strings Alternately (link)
Description
You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is
longer than the other, append the additional letters onto the end of the merged string.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
m, n = len(word1) , len(word2)
i=j=0
res = ''
return res
2350 Find Closest Number to Zero (link)
Description
Given an integer array nums of size n, return the number with the value closest to 0 in nums. If there are multiple answers, return the
number with the largest value.
Example 1:
Example 2:
Constraints:
class Solution:
def findClosestNumber(self, nums: List[int]) -> int:
closest = nums[0]
for x in nums:
if abs(x) < abs(closest):
closest = x
Description
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slowPtr = head;
ListNode fastPtr = head;
Description
Given an integer num, return the number of steps to reduce it to zero.
In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
Example 1:
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
Example 2:
Input: num = 8
Output: 4
Explanation:
Step 1) 8 is even; divide by 2 and obtain 4.
Step 2) 4 is even; divide by 2 and obtain 2.
Step 3) 2 is even; divide by 2 and obtain 1.
Step 4) 1 is odd; subtract 1 and obtain 0.
Example 3:
Constraints:
class Solution {
public int numberOfSteps(int num) {
int steps = 0;
while(num != 0){
if(num%2 == 0){
steps++;
num = num / 2;
}
else{
steps++;
num--;
}
}
return steps;
}
}
412 Fizz Buzz (link)
Description
Given an integer n, return a string array answer (1-indexed) where:
Example 1:
Input: n = 3
Output: ["1","2","Fizz"]
Example 2:
Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]
Example 3:
Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]
Constraints:
class Solution:
def fizzBuzz(self, n: int) -> List[str]:
res = []
for i in range(1, n+1):
Description
You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the ithcustomer has in the jthbank. 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.
Example 1:
Example 2:
Example 3:
Constraints:
m == accounts.length
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100
class Solution {
public int maximumWealth(int[][] accounts) {
int maxWealth = 0;
Description
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Example 1:
Example 2:
Example 3:
Constraints:
class Solution {
public int[] runningSum(int[] nums) {
int temp = nums[0];
for(int i=1; i<nums.length; i++){
nums[i] = nums[i] + temp;
temp = nums[i];
}
return nums;
}
}
101 Symmetric Tree (link)
Description
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Example 2:
Constraints:
Description
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Example 1:
Example 2:
Example 3:
Constraints:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if((p == null || q == null) || (p.val != q.val)){
return false;
}
return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
}
}
94 Binary Tree Inorder Traversal (link)
Description
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Output: [1,3,2]
Explanation:
Example 2:
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Output: [1]
Constraints:
Description
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as
well.
Example 1:
Example 2:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while(current != null && current.next != null){
if(current.val == current.next.val){
current.next = current.next.next;
}
else{
current = current.next;
}
}
return head;
}
}
70 Climbing Stairs (link)
Description
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
class Solution {
public int climbStairs(int n) {
int a = 0;
int b = 1;
int temp;
Description
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Example 2:
Constraints:
class Solution
{
public String addBinary(String a, String b)
{
StringBuilder sb = new StringBuilder();
int carry = 0;
int i = a.length() - 1;
int j = b.length() - 1;
Description
You are given a large integer represented as an integer array digits, where each digits[i] is the ith 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 leading 0's.
Increment the large integer by one and return the resulting array of digits.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in reversed(range(len(digits))):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
return [1] + digits
35 Search Insert Position (link)
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.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution {
public int searchInsert(int[] nums, int target) {
if (nums.length == 1) {
if (nums[0] >= target)
return 0;
else
return 1;
int start = 0;
int end = nums.length - 1;
int ans = 0;
Description
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-
negative as well.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
Constraints:
class Solution {
public int mySqrt(int x) {
return (int) Math.sqrt(x);
}
}
383 Ransom Note (link)
Description
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false
otherwise.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
ransomNote = list(ransomNote)
magazine = list(magazine)
for i in range(len(ransomNote)):
if ransomNote[i] in magazine:
index = magazine.index(ransomNote[i])
del magazine[index]
else:
return False
return True
14 Longest Common Prefix (link)
Description
Write a function to find the longest common prefix string amongst an array of strings.
Example 1:
Example 2:
Constraints:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
max_str = max(strs)
min_str = min(strs)
out = ''
for i in range(len(min_str)):
if max_str[i] == min_str[i]:
out += min_str[i]
else:
break
return out
28 Find the Index of the First Occurrence in a String (link)
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.
Example 1:
Example 2:
Constraints:
class Solution {
public int strStr(String haystack, String needle) {
int l = needle.length();
if (temp.equals(needle))
return i;
}
return -1;
}
}
151 Reverse Words in a String (link)
Description
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a
single space separating the words. Do not include any extra spaces.
Example 1:
Example 2:
Example 3:
Constraints:
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
class Solution:
def reverseWords(self, s: str) -> str:
reversedWord = ''
splitted = list(s.split())[::-1]
for i in splitted:
reversedWord = reversedWord + " " +i
return reversedWord.lstrip()
58 Length of Last Word (link)
Description
Given a string s consisting of words and spaces, return the length of the last word in the string.
Example 1:
Example 2:
Example 3:
Constraints:
class Solution:
def lengthOfLastWord(self, s: str) -> int:
s = s.lower().rstrip()
last_word = 0
for i in s:
if i == " ":
last_word = 0
continue
last_word += 1
return last_word
217 Contains Duplicate (link)
Description
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Output: true
Explanation:
Example 2:
Output: false
Explanation:
Example 3:
Output: true
Constraints:
import java.util.HashSet;
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet set = new HashSet<>();
for(int i=0;i<nums.length;i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
continue;
}
if(set.contains(nums[i]))
return true;
}
return false;
}
}
169 Majority Element (link)
Description
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in
the array.
Example 1:
Example 2:
Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in O(1) space?
class Solution {
public int majorityElement(int[] nums) {
int appearance = 1;
else
appearance--;
if(appearance == 0){
nums[0] = nums[i];
appearance++;
}
}
return nums[0];
}
}
26 Remove Duplicates from Sorted Array (link)
Description
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears
only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums
initially. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:
The judge will test your solution with the following code:
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
Example 1:
Example 2:
Constraints:
class Solution {
public int removeDuplicates(int[] nums) {
int index = 1;
for(int i=1; i<nums.length; i++){
if(nums[i] != nums[i-1]){
nums[index] = nums[i];
index++;
}
}
return index;
}
}
27 Remove Element (link)
Description
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be
changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining
elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:
The judge will test your solution with the following code:
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
Example 1:
Example 2:
Constraints:
class Solution {
public int removeElement(int[] nums, int val) {
int j = 0;
for(int i = 0; i<nums.length; i++){
if(nums[i] != val){
nums[j] = nums[i];
j++;
}
}
return j;
}
}
21 Merge Two Sorted Lists (link)
Description
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Example 2:
Example 3:
Constraints:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
88 Merge Sorted Array (link)
Description
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number
of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1
has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and
should be ignored. nums2 has a length of n.
Example 1:
Example 2:
Example 3:
Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
Follow up: Can you come up with an algorithm that runs in O(m + n) time?
import copy
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
if n==0:return
temp = copy.deepcopy(nums1)[:len(nums1)-n]
nums1.clear()
while(temp and nums2):
if m==0:
break
if nums2[0] <= temp[0]:
nums1.append(nums2[0])
nums2.pop(0)
else:
nums1.append(temp[0])
temp.pop(0)
m -= 1
for i in temp:
nums1.append(i)
for i in nums2:
nums1.append(i)
2168 Check if Numbers Are Ascending in a Sentence (link)
Description
A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number
consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.
For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such
as "puppy" are words.
Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other
than the last number, each number is strictly smaller than the number on its right in s).
Example 1:
Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.
Example 2:
Example 3:
Constraints:
class Solution:
def areNumbersAscending(self, s: str) -> bool:
maxx = 0
n = len(s)
i = 0
while(i<n):
if not s[i].isdigit():
i += 1
continue
num = s[i] #35
j = 1
while(i+j < n and s[i+j].isdigit()):
num += s[i+j]
j+=1
else:
i = i+j
num = int(num)
if (num <= maxx):
return False
else:
maxx = num
return True
8 String to Integer (atoi) (link)
Description
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
Example 1:
Input: s = "42"
Output: 42
Explanation:
The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
Example 2:
Output: -42
Explanation:
Example 3:
Input: s = "1337c0d3"
Output: 1337
Explanation:
Example 4:
Input: s = "0-1"
Output: 0
Explanation:
Example 5:
Explanation:
Constraints:
class Solution:
symbol = {'+':1,'-':-1}
def myAtoi(self, s: str) -> int:
res = 0
temp = 1
start = False
for i in s:
if i.isalpha():
break
elif i == ' ':
if start==True:break
elif(not i.isdigit()):
if(start==True):
break
if i not in self.symbol:
break
else:
start = True
temp = self.symbol[i]
continue
else:
start = True
digit = int(i)
res = res * 10 + digit
res = res * temp
if(res >= 2**31):
return 2**31-1
elif(res <= -1*(2**31)):
return -1*(2**31)
else:
return res
7 Reverse Integer (link)
Description
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer
range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
Constraints:
class Solution:
def reverse(self, x: int) -> int:
res = 0
temp = -x if x<0 else x
while temp:
rem = temp%10
res = (res*10)+rem
temp//=10
return 0
if x<0:
return -res
return res
5 Longest Palindromic Substring (link)
Description
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s)<=1:return s
hashmap = {}
for i in range(len(s)):
for j in range(i+1,len(s)+1):
patt = s[i:j]
if patt == patt[::-1]:
hashmap[len(patt)] = patt
maximum = max(hashmap)
return hashmap[maximum]
2724 Convert an Array Into a 2D Array With Conditions (link)
Description
You are given an integer array nums. You need to create a 2D array from nums satisfying the following conditions:
The 2D array should contain only the elements of the array nums.
Each row in the 2D array contains distinct integers.
The number of rows in the 2D array should be minimal.
Return the resulting array. If there are multiple answers, return any of them.
Note that the 2D array can have a different number of elements on each row.
Example 1:
Example 2:
Constraints:
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
hashmap = {}
for i in nums:
if i in hashmap:
hashmap[i] += 1
else:
hashmap[i] = 1
maximum = max(hashmap.values())
for i in hashmap:
j = 0
while hashmap[i]:
array[j].append(i)
hashmap[i] -= 1
j+=1
return array
455 Assign Cookies (link)
Description
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one
cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a
size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number
of your content children and output the maximum number.
Example 1:
Example 2:
Constraints:
Note: This question is the same as 2410: Maximum Matching of Players With Trainers.
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
empty = len(s)==0
if empty:return 0
g.sort()
s.sort()
maxchild = 0
cookies = len(s)-1
child = len(g) -1
return maxchild
2 Add Two Numbers (link)
Description
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of
their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Example 2:
Example 3:
Constraints:
The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
temp = ListNode(0)
curr = temp
carry = 0
while(l1 or l2 or carry):
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
dummy,out = divmod(v1+v2+carry,10)
carry = dummy
curr.next = ListNode(out)
curr = curr.next
return temp.next