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:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105-109<= nums[i] <= 109
class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
# Loop through all numbers in `nums`
n = len(nums)
for current_index in range(n):
# Loop through the remaining numbers
for comparison_index in range(current_index + 1, n):
# Return True if the numbers at the two indices are equal
if nums[current_index] == nums[comparison_index]:
return True
# Return False if no equality is found after completing the iteration
return False
solution = Solution()
print(solution.containsDuplicate(nums=[1, 2, 3, 1]))
print(solution.containsDuplicate(nums=[1, 2, 3, 4]))
print(solution.containsDuplicate(nums=[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]))True
False
True
class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
# Sort the list `nums` in ascending order
nums.sort()
# Loop through all numbers in the sorted list from the second element
for index in range(1, len(nums)):
# Return True if the current number is equal to the previous number
if nums[index] == nums[index - 1]:
return True
# Return False if no equality is found after completing the iteration
return False
solution = Solution()
print(solution.containsDuplicate(nums=[1, 2, 3, 1]))
print(solution.containsDuplicate(nums=[1, 2, 3, 4]))
print(solution.containsDuplicate(nums=[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]))True
False
True
class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
# Create an empty set to store unique numbers in `nums`
unique_nums: set[int] = set()
# Loop through all numbers in `nums`
for num in nums:
# Return True if the current number is already in the set
if num in unique_nums:
return True
# Otherwise, add the number to the set
unique_nums.add(num)
# Return False if no duplicates are found after completing the iteration
return False
solution = Solution()
print(solution.containsDuplicate(nums=[1, 2, 3, 1]))
print(solution.containsDuplicate(nums=[1, 2, 3, 4]))
print(solution.containsDuplicate(nums=[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]))True
False
True
Given two strings s and t, return true if t is an anagram of
s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104sandtconsist of lowercase English letters.
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:
# Base case: If the lengths of `s` and `t` are different, they cannot be anagrams
if len(s) != len(t):
return False
# Loop through all characters in `s`
for char_s in s:
# Create a flag to check if a matching character is found
is_matched = False
# Loop through all characters and their indices in `t`
for index, char_t in enumerate(t):
# If the character in `s` and the character in `t` are equal
if char_t == char_s:
# Remove the character from `t`
t = t[:index] + t[index + 1 :]
# Set the flag to True and exit the loop
is_matched = True
break
# Return False if no match is found for the character in `s`
if not is_matched:
return False
# Return True after completing the iteration
return True
solution = Solution()
print(solution.isAnagram(s="anagram", t="nagaram"))
print(solution.isAnagram(s="rat", t="car"))True
False
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
solution = Solution()
print(solution.isAnagram(s="anagram", t="nagaram"))
print(solution.isAnagram(s="rat", t="car"))True
False
from typing import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
solution = Solution()
print(solution.isAnagram(s="anagram", t="nagaram"))
print(solution.isAnagram(s="rat", t="car"))True
False
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Base case: If the lengths of `s` and `t` are different, they cannot be anagrams
if len(s) != len(t):
return False
# Create a list to count the frequency of each English character in `s` and `t`
counts = [0] * 26
# Loop through all characters in `s` and `t`
for index, char in enumerate(s):
# Increment the counts for the character in `s`
counts[ord(char) - ord("a")] += 1
# Decrement the counts for the character in `t`
counts[ord(t[index]) - ord("a")] -= 1
# Return true if the counts are zero
return all(count == 0 for count in counts)
solution = Solution()
print(solution.isAnagram(s="anagram", t="nagaram"))
print(solution.isAnagram(s="rat", t="car"))True
False
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Map each lowercase English letter to a unique prime number
prime_numbers = {
"a": 2,
"b": 3,
"c": 5,
"d": 7,
"e": 11,
"f": 13,
"g": 17,
"h": 19,
"i": 23,
"j": 29,
"k": 31,
"l": 37,
"m": 41,
"n": 43,
"o": 47,
"p": 53,
"q": 59,
"r": 61,
"s": 67,
"t": 71,
"u": 73,
"v": 79,
"w": 83,
"x": 89,
"y": 97,
"z": 101,
}
# Initialize the products of prime numbers corresponding to characters in `s` and `t`
product_s = 1
product_t = 1
# Loop through all characters in `s`
for char in s:
# Multiply the product corresponding to `s` by the prime number corresponding to the character
product_s *= prime_numbers[char]
# Loop through all characters in `t`
for char in t:
# Multiply the product corresponding to `t` by the prime number corresponding to the character
product_t *= prime_numbers[char]
# Return True if the products are equal
return product_s == product_t
solution = Solution()
print(solution.isAnagram(s="anagram", t="nagaram"))
print(solution.isAnagram(s="rat", t="car"))True
False
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.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104-109<= nums[i] <= 109-109<= target <= 109- Only one valid answer exists.
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]:
# Loop through all numbers in `nums`
n = len(nums)
for current_index in range(n):
# Loop through the remaining numbers
for comparison_index in range(current_index + 1, n):
# Return True if the sum of the numbers at two indices equals `target`
if nums[current_index] + nums[comparison_index] == target:
return [current_index, comparison_index]
# Return an empty list if no equality is found after completing the iteration
return []
solution = Solution()
print(solution.twoSum(nums=[2, 7, 11, 15], target=9))
print(solution.twoSum(nums=[3, 2, 4], target=6))
print(solution.twoSum(nums=[3, 3], target=6))[0, 1]
[1, 2]
[0, 1]
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
# Create a sorted list of tuples containing the original index and value of `nums`
nums_sorted = sorted(enumerate(nums), key=lambda x: x[1])
# Loop until two pointers at the start and at the end of the sorted list meet
left, right = 0, len(nums) - 1
while left < right:
# Calculate the sum of the values at the current pointers
current_sum = nums_sorted[left][1] + nums_sorted[right][1]
# Return the original indices of the two numbers if the current sum is equal to `target`
if current_sum == target:
return [nums_sorted[left][0], nums_sorted[right][0]]
# If the current sum is less than `target`, move the left pointer to the right
if current_sum < target:
left += 1
# If the current sum is greater than `target`, move the right pointer to the left
else:
right -= 1
# Return an empty list if no solution is found after completing the iteration
return []
solution = Solution()
print(solution.twoSum(nums=[2, 7, 11, 15], target=9))
print(solution.twoSum(nums=[3, 2, 4], target=6))
print(solution.twoSum(nums=[3, 3], target=6))[0, 1]
[1, 2]
[0, 1]
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
# Create a dictionary to store the numbers and their indices in `nums`
nums_index: dict[int, int] = {}
# Loop through all numbers and their indices in `nums`
for index, num in enumerate(nums):
# Calculate the complement of the current number and `target`
complement = target - num
# Return the indices of the two numbers if the complement is in the dictionary
if complement in nums_index:
return [nums_index[complement], index]
# Otherwise, add the current number and its index to the dictionary
nums_index[num] = index
# Return an empty list if no equality is found after completing the iteration
return []
solution = Solution()
print(solution.twoSum(nums=[2, 7, 11, 15], target=9))
print(solution.twoSum(nums=[3, 2, 4], target=6))
print(solution.twoSum(nums=[3, 3], target=6))[0, 1]
[1, 2]
[0, 1]
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or
false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
Constraints:
1 <= s.length <= 2 * 105sconsists only of printable ASCII characters.
class Solution:
def isPalindrome(self, s: str) -> bool:
# Normalize `s`
normalized_s = "".join(
# Convert all characters to lowercase
char.lower() for char in s
# Join characters that are alphanumeric
if char.isalnum()
)
# Return True if the normalized string is equal to its reverse
return normalized_s == normalized_s[::-1]
solution = Solution()
print(solution.isPalindrome(s="A man, a plan, a canal: Panama"))
print(solution.isPalindrome(s="race a car"))
print(solution.isPalindrome(s=" "))True
False
True
class Solution:
def isPalindrome(self, s: str) -> bool:
def alpha_num(c: str) -> bool:
"""Check if a given character is alphanumeric."""
return (
ord("A") <= ord(c) <= ord("Z")
or ord("a") <= ord(c) <= ord("z")
or ord("0") <= ord(c) <= ord("9")
)
# Loop through `s` using two pointers from the left and from the right
left, right = 0, len(s) - 1
while left < right:
# Move the pointers closer to the center until an alphanumeric character is found
while left < right and not alpha_num(s[left]):
left += 1
while left < right and not alpha_num(s[right]):
right -= 1
# Return False if the characters at the left and right pointers are not equal
if s[left].lower() != s[right].lower():
return False
# Move the pointers closer to the center
left += 1
right -= 1
# Return True after completing the iteration
return True
solution = Solution()
print(solution.isPalindrome(s="A man, a plan, a canal: Panama"))
print(solution.isPalindrome(s="race a car"))
print(solution.isPalindrome(s=" "))True
False
True
Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum()Initializes theTwoSumobject, with an empty array initially.void add(int number)Addsnumberto the data structure.boolean find(int value)Returnstrueif there exists any pair of numbers whose sum is equal tovalue, otherwise, it returnsfalse.
Example 1:
Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]
Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1); // [] --> [1]
twoSum.add(3); // [1] --> [1,3]
twoSum.add(5); // [1,3] --> [1,3,5]
twoSum.find(4); // 1 + 3 = 4, return true
twoSum.find(7); // No two integers sum up to 7, return false
Constraints:
-10^5 <= number <= 10^5-2^31 <= value <= 2^31 - 1- At most
5 * 10^4calls will be made toaddandfind.
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:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 104
class Solution:
def maxProfit(self, prices: list[int]) -> int:
# Initialize the maximum profit to zero
max_profit = 0
# Loop through all days of `prices` as the buying day
num_days = len(prices)
for buy_day in range(num_days):
# Loop through all subsequent days as the selling day
for sell_day in range(buy_day + 1, num_days):
# Calculate the potential profit for the pair of days
potential_profit = prices[sell_day] - prices[buy_day]
# Update the maximum profit if the potential profit is higher
max_profit = max(potential_profit, max_profit)
# Return the maximum profit
return max_profit
solution = Solution()
print(solution.maxProfit(prices=[7, 1, 5, 3, 6, 4]))
print(solution.maxProfit(prices=[7, 6, 4, 3, 1]))5
0
class Solution:
def maxProfit(self, prices: list[int]) -> int:
# Initialize the minimum price to the first price in `prices`
min_price = prices[0]
# Initialize the maximum profit to zero
max_profit = 0
# Loop through all numbers in `prices` from the second day
for price in prices[1:]:
# Update the minimum numbers if the current number is lower
min_price = min(min_price, price)
# Calculate the potential profit
profit = price - min_price
# Update the maximum profit if the potential profit is higher
max_profit = max(max_profit, profit)
# Return the maximum profit
return max_profit
solution = Solution()
print(solution.maxProfit(prices=[7, 1, 5, 3, 6, 4]))
print(solution.maxProfit(prices=[7, 6, 4, 3, 1]))5
0
Given a string s containing just the characters '(', ')', '{',
'}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
class Solution:
def isValid(self, s: str) -> bool:
# Define a dictionary of matching parentheses pairs
matching_parentheses = {"(": ")", "{": "}", "[": "]"}
# Loop through all characters in `s` until no more pairs are found
while any(open_paren + close_paren in s for open_paren, close_paren in matching_parentheses.items()):
# Replace each pair of matching parentheses with an empty string
for open_paren, close_paren in matching_parentheses.items():
s = s.replace(open_paren + close_paren, "")
# Return True if the string is empty after completing the iteration
return not s
solution = Solution()
print(solution.isValid(s="()"))
print(solution.isValid(s="()[]{}"))
print(solution.isValid(s="(]"))True
True
False
class Solution:
def isValid(self, s: str) -> bool:
# Base case: If `s` is empty, it is considered valid
if not s:
return True
# Define a dictionary of matching parentheses pairs
matching_parentheses = {"(": ")", "{": "}", "[": "]"}
# Loop through `s` up to the second-to-last character
index = 0
length = len(s)
while index < length - 1:
# Check each pair of characters for a matching set of parentheses
for open_paren, close_paren in matching_parentheses.items():
# If a matching pair is found
if s[index] == open_paren and s[index + 1] == close_paren:
# Create a new string without the matched parentheses
new_string = s[:index] + s[index + 2:]
# Recursively check if the new string is valid
return self.isValid(new_string)
# Move to the next character in the string
index += 1
# Return False if no such valid pairs are found after completing the iteration
return False
solution = Solution()
print(solution.isValid(s="()"))
print(solution.isValid(s="()[]{}"))
print(solution.isValid(s="(]"))True
True
False
class Solution:
def isValid(self, s: str) -> bool:
# Initialize an empty stack to keep track of opening parentheses
stack: list[str] = []
# Define a dictionary of matching parentheses pairs
matching_parentheses = {")": "(", "}": "{", "]": "["}
# Loop through all characters in `s`
for char in s:
# Check if the current character is a closing parenthesis
if char in matching_parentheses:
# Return False if the stack is empty or the top of the stack does not match the opening parenthesis
if not stack or stack.pop() != matching_parentheses[char]:
return False
else:
# Push the current character onto the stack if it is an opening parenthesis
stack.append(char)
# Return True if the stack is empty after completing the iteration
return not stack
solution = Solution()
print(solution.isValid(s="()"))
print(solution.isValid(s="()[]{}"))
print(solution.isValid(s="(]"))True
True
False
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.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104-104< nums[i], target < 104- All the integers in
numsare unique. numsis sorted in ascending order.
class Solution:
def search(self, nums: list[int], target: int) -> int:
# Loop until two pointers at the start and at the end of `nums` meet
left, right = 0, len(nums) - 1
while left <= right:
# Calculate the middle index between two pointers
mid = (left + right) // 2
# Return the index if the middle element equal `target`
if nums[mid] == target:
return mid
# If the middle element is less than `target` adjust the left pointer to search the right half
if nums[mid] < target:
left, right = mid + 1, right
# Otherwise, adjust the right pointer to search the left half
else:
left, right = left, mid - 1
# Return -1 if `target` is not found in the list after completing the iteration
return -1
solution = Solution()
print(solution.search([-1, 0, 3, 5, 9, 12], target=9))
print(solution.search([-1, 0, 3, 5, 9, 12], target=2))4
-1
class Solution:
def search(self, nums: list[int], target: int) -> int:
def binary_search(left: int, right: int) -> int:
"""Recursively performs a binary search."""
# Base case: if the left index exceeds the right index, `target` is not found
if left > right:
return -1
# Calculate the middle index of `nums`
mid = (left + right) // 2
# Return the index if the element at the middle index equal `target`
if nums[mid] == target:
return mid
return (
# Recursively search the right half if `target` is greater than the middle element
binary_search(mid + 1, right)
# Otherwise, search the left half
if nums[mid] < target
else binary_search(left, mid - 1)
)
# Start the binary search on `nums`
return binary_search(0, len(nums) - 1)
solution = Solution()
print(solution.search([-1, 0, 3, 5, 9, 12], target=9))
print(solution.search([-1, 0, 3, 5, 9, 12], target=2))4
-1
class Solution:
def search(self, nums: list[int], target: int) -> int:
# Return 0 if the first element in `nums` matches `target`
if nums[0] == target:
return 0
# Otherwise, initialize the search bound to 1
bound = 1
# Increase the bound exponentially until it surpasses `target` or reach the end of `nums`
n = len(nums)
while bound < n and nums[bound] < target:
bound *= 2
# Loop until two pointers at half of the bound and at the minimum of the bound or the last index meet
left = bound // 2
right = min(bound, n - 1)
while left <= right:
# Calculate the middle index between two pointers
mid = (left + right) // 2
# Return the index if the middle element equal `target`
if nums[mid] == target:
return mid
# If the middle element is less than `target`, adjust the left pointer to search the right half
if nums[mid] < target:
left, right = mid + 1, right
# Otherwise, adjust the right pointer to search the left half
else:
left, right = left, mid - 1
# Return -1 if `target` is not found in the list after completing the iteration
return -1
solution = Solution()
print(solution.search([-1, 0, 3, 5, 9, 12], target=9))
print(solution.search([-1, 0, 3, 5, 9, 12], target=2))4
-1
Given the head of a singly linked list, reverse the list, and return
the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(
self,
val: int = 0,
nextNode: "Optional[ListNode]" = None,
) -> None:
self.val: int = val
self.next: Optional[ListNode] = nextNode
# Helper function to convert list to linked list
def list_to_linked_list(lst: list[int]) -> Optional[ListNode]:
dummy = ListNode()
current = dummy
for value in lst:
current.next = ListNode(value)
current = current.next
return dummy.next
# Helper function to convert linked list to list
def linked_list_to_list(node: Optional[ListNode]) -> list[int]:
result: list[int] = []
while node:
result.append(node.val)
node = node.next
return resultclass Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Initialize a variable to keep track of the previous node
previous_node = None
# Loop through all nodes in `head`
current_node = head
while current_node:
# Store the next node of the current node in a temporary variable
temp = current_node.next
# Point the next node of the current node to the previous node
current_node.next = previous_node
# Move the previous node to the current node
previous_node = current_node
# Move the current node to the next node stored in the temporary variable
current_node = temp
# Return the previous node that points to the new head after completing the iteration
return previous_node
solution = Solution()
print(linked_list_to_list(solution.reverseList(list_to_linked_list([1, 2, 3, 4, 5]))))
print(linked_list_to_list(solution.reverseList(list_to_linked_list([1, 2]))))
print(linked_list_to_list(solution.reverseList(list_to_linked_list([]))))[5, 4, 3, 2, 1]
[2, 1]
[]
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Base case: if `head` is empty or has only one node, return the list as is
if not head or not head.next:
return head
# Recursively reverse the list from the second node
reversed_head = self.reverseList(head.next)
# After completing the recursion, point the next node of the end of the reversed list to the current node
head.next.next = head
# Point the next node of the current node to None
head.next = None
# Return the head of the reversed list
return reversed_head
solution = Solution()
print(linked_list_to_list(solution.reverseList(list_to_linked_list([1, 2, 3, 4, 5]))))
print(linked_list_to_list(solution.reverseList(list_to_linked_list([1, 2]))))
print(linked_list_to_list(solution.reverseList(list_to_linked_list([]))))[5, 4, 3, 2, 1]
[2, 1]
[]
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.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
class Solution:
def mergeTwoLists(
self, list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
current = dummy
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
if list1:
current.next = list1
else:
current.next = list2
return dummy.next
solution = Solution()
print(linked_list_to_list(solution.mergeTwoLists(list_to_linked_list([1, 2, 4]), list_to_linked_list([1, 3, 4]))))
print(linked_list_to_list(solution.mergeTwoLists(list_to_linked_list([]), list_to_linked_list([]))))
print(linked_list_to_list(solution.mergeTwoLists(list_to_linked_list([]), list_to_linked_list([0]))))[1, 1, 2, 3, 4, 4]
[]
[0]
class Solution:
def mergeTwoLists(
self, list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
solution = Solution()
print(linked_list_to_list(solution.mergeTwoLists(list_to_linked_list([1, 2, 4]), list_to_linked_list([1, 3, 4]))))
print(linked_list_to_list(solution.mergeTwoLists(list_to_linked_list([]), list_to_linked_list([]))))
print(linked_list_to_list(solution.mergeTwoLists(list_to_linked_list([]), list_to_linked_list([0]))))[1, 1, 2, 3, 4, 4]
[]
[0]
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:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
def list_to_linked_list_cycle(lst: list[int], pos: int) -> Optional[ListNode]:
nodes = [ListNode(val) for val in lst]
for i in range(1, len(lst)):
nodes[i - 1].next = nodes[i]
if pos != -1:
nodes[-1].next = nodes[pos]
return nodes[0]class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
visited_nodes = {}
current_node = head
while current_node:
if current_node in visited_nodes:
return True
visited_nodes[current_node] = True
current_node = current_node.next
return False
solution = Solution()
print(solution.hasCycle(list_to_linked_list_cycle([3, 2, 0, -4], 1)))
print(solution.hasCycle(list_to_linked_list_cycle([1, 2], 0)))
print(solution.hasCycle(list_to_linked_list_cycle([1], -1)))True
True
False
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
solution = Solution()
print(solution.hasCycle(list_to_linked_list_cycle([3, 2, 0, -4], 1)))
print(solution.hasCycle(list_to_linked_list_cycle([1, 2], 0)))
print(solution.hasCycle(list_to_linked_list_cycle([1], -1)))True
True
False
Given the root of a binary tree, invert the tree, and return its
root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
from collections import deque
from typing import Optional
class TreeNode:
def __init__(
self,
val: Optional[int] = 0,
left: Optional["TreeNode"] = None,
right: Optional["TreeNode"] = None,
) -> None:
self.val = val
self.left = left
self.right = right
def list_to_tree(values: list[Optional[int]]) -> Optional[TreeNode]:
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while i < len(values):
current = queue.pop(0)
if values[i] is not None:
current.left = TreeNode(values[i])
queue.append(current.left)
i += 1
if i < len(values) and values[i] is not None:
current.right = TreeNode(values[i])
queue.append(current.right)
i += 1
return root
def tree_to_list(root: Optional[TreeNode]) -> list[Optional[int]]:
result: list[Optional[int]] = []
queue: deque[Optional[TreeNode]] = deque([root])
while queue:
current = queue.popleft()
if current:
result.append(current.val)
queue.append(current.left)
queue.append(current.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return resultclass Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
stack = [root]
while stack:
current = stack.pop()
current.left, current.right = current.right, current.left
if current.left:
stack.append(current.left)
if current.right:
stack.append(current.right)
return root
solution = Solution()
print(tree_to_list(solution.invertTree(list_to_tree([4, 2, 7, 1, 3, 6, 9]))))
print(tree_to_list(solution.invertTree(list_to_tree([2, 1, 3]))))
print(tree_to_list(solution.invertTree(list_to_tree([]))))[4, 7, 2, 9, 6, 3, 1]
[2, 3, 1]
[]
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return root
solution = Solution()
print(tree_to_list(solution.invertTree(list_to_tree([4, 2, 7, 1, 3, 6, 9]))))
print(tree_to_list(solution.invertTree(list_to_tree([2, 1, 3]))))
print(tree_to_list(solution.invertTree(list_to_tree([]))))[4, 7, 2, 9, 6, 3, 1]
[2, 3, 1]
[]
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
solution = Solution()
print(tree_to_list(solution.invertTree(list_to_tree([4, 2, 7, 1, 3, 6, 9]))))
print(tree_to_list(solution.invertTree(list_to_tree([2, 1, 3]))))
print(tree_to_list(solution.invertTree(list_to_tree([]))))[4, 7, 2, 9, 6, 3, 1]
[2, 3, 1]
[]
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:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. -100 <= Node.val <= 100
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
stack: list[tuple[Optional[TreeNode], int]] = [(root, 1)]
max_depth = 0
while stack:
node, depth = stack.pop()
if node:
max_depth = max(max_depth, depth)
stack.append((node.left, depth + 1))
stack.append((node.right, depth + 1))
return max_depth
solution = Solution()
print(solution.maxDepth(list_to_tree([3, 9, 20, None, None, 15, 7])))
print(solution.maxDepth(list_to_tree([1, None, 2])))3
2
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
queue: deque[tuple[Optional[TreeNode], int]] = deque([(root, 1)])
max_depth = 0
while queue:
node, depth = queue.popleft()
if node:
max_depth = max(max_depth, depth)
queue.append((node.left, depth + 1))
queue.append((node.right, depth + 1))
return max_depth
solution = Solution()
print(solution.maxDepth(list_to_tree([3, 9, 20, None, None, 15, 7])))
print(solution.maxDepth(list_to_tree([1, None, 2])))3
2
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
return (
1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) if root else 0
)
solution = Solution()
print(solution.maxDepth(list_to_tree([3, 9, 20, None, None, 15, 7])))
print(solution.maxDepth(list_to_tree([1, None, 2])))3
2
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:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints:
- The number of nodes in both trees is in the range
[0, 100]. -104<= Node.val <= 104
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
node1, node2 = stack.pop()
if not node1 and not node2:
continue
if not node1 or not node2 or node1.val != node2.val:
return False
stack.append((node1.right, node2.right))
stack.append((node1.left, node2.left))
return True
solution = Solution()
print(solution.isSameTree(list_to_tree([1, 2, 3]), list_to_tree([1, 2, 3])))
print(solution.isSameTree(list_to_tree([1, 2]), list_to_tree([1, None, 2])))
print(solution.isSameTree(list_to_tree([1, 2, 1]), list_to_tree([1, 1, 2])))True
False
False
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
queue = deque([(p, q)])
while queue:
node1, node2 = queue.popleft()
if not node1 and not node2:
continue
if not node1 or not node2 or node1.val != node2.val:
return False
queue.append((node1.right, node2.right))
queue.append((node1.left, node2.left))
return True
solution = Solution()
print(solution.isSameTree(list_to_tree([1, 2, 3]), list_to_tree([1, 2, 3])))
print(solution.isSameTree(list_to_tree([1, 2]), list_to_tree([1, None, 2])))
print(solution.isSameTree(list_to_tree([1, 2, 1]), list_to_tree([1, 1, 2])))True
False
False
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return (
p == q
if not p or not q
else (
p.val == q.val
and self.isSameTree(p.left, q.left)
and self.isSameTree(p.right, q.right)
)
)
solution = Solution()
print(solution.isSameTree(list_to_tree([1, 2, 3]), list_to_tree([1, 2, 3])))
print(solution.isSameTree(list_to_tree([1, 2]), list_to_tree([1, None, 2])))
print(solution.isSameTree(list_to_tree([1, 2, 1]), list_to_tree([1, 1, 2])))True
False
False
Given the roots of two binary trees root and subRoot, return true
if there is a subtree of root with the same structure and node values
ofsubRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in
tree and all of this node's descendants. The tree tree could also be
considered as a subtree of itself.
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Constraints:
- The number of nodes in the
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. -104<= root.val <= 104-104<= subRoot.val <= 104
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
return (
False
if not root
else self.isSameTree(root, subRoot)
or self.isSubtree(root.left, subRoot)
or self.isSubtree(root.right, subRoot)
)
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return (
p == q
if not p or not q
else (
p.val == q.val
and self.isSameTree(p.left, q.left)
and self.isSameTree(p.right, q.right)
)
)
solution = Solution()
print(solution.isSubtree(list_to_tree([3, 4, 5, 1, 2]), list_to_tree([4, 1, 2])))
print(solution.isSubtree(list_to_tree([3, 4, 5, 1, 2, None, None, None, None, 0]), list_to_tree([4, 1, 2])))True
False
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:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -100 <= Node.val <= 100
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
stack: list[tuple[Optional[TreeNode], bool]] = [(root, False)]
depth: dict[Optional[TreeNode], int] = {}
diameter = 0
while stack:
node, visited = stack.pop()
if node:
if visited:
left_depth = depth.get(node.left, 0)
right_depth = depth.get(node.right, 0)
depth[node] = max(left_depth, right_depth) + 1
diameter = max(diameter, left_depth + right_depth)
else:
stack.append((node, True))
stack.append((node.left, False))
stack.append((node.right, False))
return diameter
solution = Solution()
print(solution.diameterOfBinaryTree(list_to_tree([1, 2, 3, 4, 5])))
print(solution.diameterOfBinaryTree(list_to_tree([1, 2])))3
1
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
diameter = [0]
def depth(node: Optional["TreeNode"]) -> int:
if not node:
return 0
left_depth = depth(node.left)
right_depth = depth(node.right)
diameter[0] = max(diameter[0], left_depth + right_depth)
return max(left_depth, right_depth) + 1
depth(root)
return diameter[0]
solution = Solution()
print(solution.diameterOfBinaryTree(list_to_tree([1, 2, 3, 4, 5])))
print(solution.diameterOfBinaryTree(list_to_tree([1, 2])))3
1
Given a binary tree, determine if it is height-balanced.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -104<= Node.val <= 104
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(node: Optional[TreeNode]) -> int:
if not node:
return 0
left_height, right_height = dfs(node.left), dfs(node.right)
if (
left_height == -1
or right_height == -1
or abs(left_height - right_height) > 1
):
return -1
return max(left_height, right_height) + 1
return dfs(root) != -1
solution = Solution()
print(solution.isBalanced(list_to_tree([3, 9, 20, None, None, 15, 7])))
print(solution.isBalanced(list_to_tree([1, 2, 2, 3, 3, None, None, 4, 4])))
print(solution.isBalanced(list_to_tree([])))True
False
True
Design a class to find the kth largest element in a
stream. Note that it is the kth largest element in the
sorted order, not the kth distinct element.
Implement KthLargest class:
KthLargest(int k, int[] nums)Initializes the object with the integerkand the stream of integersnums.int add(int val)Appends the integervalto the stream and returns the element representing thekthlargest element in the stream.
Example 1:
Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
Constraints:
1 <= k <= 1040 <= nums.length <= 104-104<= nums[i] <= 104-104<= val <= 104- At most
104calls will be made toadd. - It is guaranteed that there will be at least
kelements in the array when you search for thekthelement.
class KthLargest:
def __init__(self, k: int, nums: list[int]):
self.k = k
self.nums = sorted(nums, reverse=True)
def add(self, val: int) -> int:
self.nums.append(val)
self.nums.sort(reverse=True)
return self.nums[self.k - 1]
obj = KthLargest(3, [4, 5, 8, 2])
print(obj.add(3))
print(obj.add(5))
print(obj.add(10))
print(obj.add(9))
print(obj.add(4))4
5
5
8
8
import heapq
class KthLargest:
def __init__(self, k: int, nums: list[int]):
self.k = k
self.min_heap: list[int] = []
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.min_heap, val)
if len(self.min_heap) > self.k:
heapq.heappop(self.min_heap)
return self.min_heap[0]
obj = KthLargest(3, [4, 5, 8, 2])
print(obj.add(3))
print(obj.add(5))
print(obj.add(10))
print(obj.add(9))
print(obj.add(4))4
5
5
8
8
You are given an array of integers stones where stones[i] is the
weight of the ith stone.
We are playing a game with the stones. On each turn, we choose the
heaviest two stones and smash them together. Suppose the heaviest
two stones have weights x and y with x <= y. The result of this
smash is:
- If
x == y, both stones are destroyed, and - If
x != y, the stone of weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones
left, return 0.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
Example 2:
Input: stones = [1]
Output: 1
Constraints:
1 <= stones.length <= 301 <= stones[i] <= 1000
class Solution:
def lastStoneWeight(self, stones: list[int]) -> int:
while len(stones) > 1:
stones.sort(reverse=True)
x = stones.pop(0)
y = stones.pop(0)
if x != y:
stones.append(x - y)
return stones[0] if stones else 0
solution = Solution()
print(solution.lastStoneWeight([2, 7, 4, 1, 8, 1]))
print(solution.lastStoneWeight([1]))1
1
import heapq
class Solution:
def lastStoneWeight(self, stones: list[int]) -> int:
stones = [-stone for stone in stones]
heapq.heapify(stones)
while len(stones) > 1:
x = heapq.heappop(stones)
y = heapq.heappop(stones)
if x != y:
heapq.heappush(stones, x - y)
return -stones[0] if stones else 0
solution = Solution()
print(solution.lastStoneWeight([2, 7, 4, 1, 8, 1]))
print(solution.lastStoneWeight([1]))1
1
Given an array of strings strs, group the anagrams together. You
can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
for char in s:
is_matched = False
for i, c in enumerate(t):
if c == char:
t = t[:i] + t[i + 1 :]
is_matched = True
break
if not is_matched:
return False
return True
anagram_groups: list[list[str]] = []
used = [False] * len(strs)
for i, str_i in enumerate(strs):
if not used[i]:
group = [str_i]
used[i] = True
for j, str_j in enumerate(strs[i + 1 :], start=i + 1):
if not used[j] and is_anagram(str_i, str_j):
group.append(str_j)
used[j] = True
anagram_groups.append(group)
return anagram_groups
solution = Solution()
print(solution.groupAnagrams(strs=["eat", "tea", "tan", "ate", "nat", "bat"]))
print(solution.groupAnagrams(strs=[""]))
print(solution.groupAnagrams(strs=["a"]))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['']]
[['a']]
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
anagrams: dict[str, list[str]] = defaultdict(list)
for s in strs:
sorted_str = "".join(sorted(s))
anagrams[sorted_str].append(s)
return list(anagrams.values())
solution = Solution()
print(solution.groupAnagrams(strs=["eat", "tea", "tan", "ate", "nat", "bat"]))
print(solution.groupAnagrams(strs=[""]))
print(solution.groupAnagrams(strs=["a"]))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['']]
[['a']]
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
anagrams: dict[tuple[int, ...], list[str]] = defaultdict(list)
for s in strs:
count = [0] * 26
for char in s:
count[ord(char) - ord("a")] += 1
key = tuple(count)
anagrams[key].append(s)
return list(anagrams.values())
solution = Solution()
print(solution.groupAnagrams(strs=["eat", "tea", "tan", "ate", "nat", "bat"]))
print(solution.groupAnagrams(strs=[""]))
print(solution.groupAnagrams(strs=["a"]))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['']]
[['a']]
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
prime_numbers = {
"a": 2,
"b": 3,
"c": 5,
"d": 7,
"e": 11,
"f": 13,
"g": 17,
"h": 19,
"i": 23,
"j": 29,
"k": 31,
"l": 37,
"m": 41,
"n": 43,
"o": 47,
"p": 53,
"q": 59,
"r": 61,
"s": 67,
"t": 71,
"u": 73,
"v": 79,
"w": 83,
"x": 89,
"y": 97,
"z": 101,
}
anagrams: dict[int, list[str]] = {}
for word in strs:
product = 1
for char in word:
product *= prime_numbers[char]
if product in anagrams:
anagrams[product].append(word)
else:
anagrams[product] = [word]
return list(anagrams.values())
solution = Solution()
print(solution.groupAnagrams(strs=["eat", "tea", "tan", "ate", "nat", "bat"]))
print(solution.groupAnagrams(strs=[""]))
print(solution.groupAnagrams(strs=["a"]))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['']]
[['a']]
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.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order.-1000 <= target <= 1000- The tests are generated such that there is exactly one solution.
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
return []
solution = Solution()
print(solution.twoSum(numbers=[2, 7, 11, 15], target=9))
print(solution.twoSum(numbers=[2, 3, 4], target=6))
print(solution.twoSum(numbers=[-1, 0], target=-1))[1, 2]
[1, 3]
[1, 2]
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
numbers_index: dict[int, int] = {}
for index, num in enumerate(numbers):
complement = target - num
if complement in numbers_index:
return [numbers_index[complement] + 1, index + 1]
numbers_index[num] = index
return []
solution = Solution()
print(solution.twoSum(numbers=[2, 7, 11, 15], target=9))
print(solution.twoSum(numbers=[2, 3, 4], target=6))
print(solution.twoSum(numbers=[-1, 0], target=-1))[1, 2]
[1, 3]
[1, 2]
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
if current_sum < target:
left += 1
else:
right -= 1
return []
solution = Solution()
print(solution.twoSum(numbers=[2, 7, 11, 15], target=9))
print(solution.twoSum(numbers=[2, 3, 4], target=6))
print(solution.twoSum(numbers=[-1, 0], target=-1))[1, 2]
[1, 3]
[1, 2]
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:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105<= nums[i] <= 105
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
n = len(nums)
triplets: list[list[int]] = []
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == 0:
triplet = sorted([nums[i], nums[j], nums[k]])
if triplet not in triplets:
triplets.append(triplet)
return triplets
solution = Solution()
print(solution.threeSum(nums=[-1, 0, 1, 2, -1, -4]))
print(solution.threeSum(nums=[0, 1, 1]))
print(solution.threeSum(nums=[0, 0, 0]))[[-1, 0, 1], [-1, -1, 2]]
[]
[[0, 0, 0]]
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:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40- All elements of
candidatesare distinct. 1 <= target <= 40
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
result: list[list[int]] = []
def backtrack(start: int, current: list[int], total: int) -> None:
if total == target:
result.append(current[:])
return
if total > target:
return
for i in range(start, len(candidates)):
current.append(candidates[i])
backtrack(i, current, total + candidates[i])
current.pop()
backtrack(0, [], 0)
return result
solution = Solution()
print(solution.combinationSum([2, 3, 6, 7], 7))
print(solution.combinationSum([2, 3, 5], 8))
print(solution.combinationSum([2], 1))[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
- The number of nodes in the list is in the range
[1, 5 * 104]. 1 <= Node.val <= 1000
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# Base case: If the list is empty or has only one node, it cannot be reordered
if not head or not head.next:
return
# Use two pointers to find the middle of the list
slow: Optional[ListNode] = head
fast: Optional[ListNode] = head.next
while slow and slow.next and fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half of the list from slow.next
prev: Optional[ListNode] = None
curr: Optional[ListNode] = slow.next if slow else None
if slow:
slow.next = None
while curr:
# Store the next node
next_temp = curr.next
# Reverse the link
curr.next = prev
# Move prev to the current node and the current node to the next node
prev, curr = curr, next_temp
# Merge the two halves together
first: Optional[ListNode] = head
second: Optional[ListNode] = prev
while first and second:
# Store the next nodes
temp1, temp2 = first.next, second.next
# Reorder nodes
first.next, second.next = second, temp1
# Move to the next nodes
first, second = temp1, temp2
solution = Solution()
head = list_to_linked_list([1, 2, 3, 4])
solution.reorderList(head)
print(linked_list_to_list(head))
head = list_to_linked_list([1, 2, 3, 4, 5])
solution.reorderList(head)
print(linked_list_to_list(head))[1, 4, 2, 3]
[1, 5, 2, 4, 3]
You are given an n x n integer matrix grid where each value
grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere
is t. You can swim from a square to another 4-directionally adjacent
square if and only if the elevation of both squares individually are at
most t. You can swim infinite distances in zero time. Of course, you
must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square
(n - 1, n - 1) if you start at the top left square (0, 0).
Example 1:
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
Example 2:
Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 500 <= grid[i][j] < n2- Each value
grid[i][j]is unique.
from collections import deque
class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
n = len(grid)
def can_swim(t: int) -> bool:
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue: deque[tuple[int, int]] = deque([(0, 0)])
visited: set[tuple[int, int]] = set()
visited.add((0, 0))
while queue:
x, y = queue.popleft()
if x == n - 1 and y == n - 1:
return True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (
0 <= nx < n
and 0 <= ny < n
and (nx, ny) not in visited
and grid[nx][ny] <= t
):
visited.add((nx, ny))
queue.append((nx, ny))
return False
low, high = grid[0][0], max(max(row) for row in grid)
while low < high:
mid = (low + high) // 2
if can_swim(mid):
high = mid
else:
low = mid + 1
return low