**[Leetle][]**
*Since January 1st, 2025*
![](static/leetle-og.png width="33%" style="margin-bottom: 500px;")
> "Leetle is a daily coding game, in the spirit of LeetCode & Wordle.
> The challenges are meant to be quick and easy, but help reinforce Python
> syntax and methods. The challenges are created by a mix of LLMs, mostly
> Claude 3.5 Sonnet, and hand-tested. --[Ron Kiehn][]"
![](static/logo.png width="33%" style="opacity: 0.25; margin-top: 500px;")
[Leetle]: https://leetle.app/archive
[Ron Kiehn]: https://ronkiehn.dev/
# [FizzBuzz](fizz_buzz_001.py)
Write a function `solve` that takes a number `n` and returns a list of numbers
from 1 to `n`. If the number is divisible by 3, replace it with 'Fizz'. If the
number is divisible by 5, replace it with 'Buzz'. If the number is divisible
by both 3 and 5, replace it with 'FizzBuzz'.
## Solution
``` Python
def solve(nums):
return [i % 3 // 2 * "Fizz" + i % 5 // 4 * "Buzz" or i + 1 for i in range(nums)]
```
## Test Cases
``` Python
assert (got := solve(15)) == [
1,
2,
"Fizz",
4,
"Buzz",
"Fizz",
7,
8,
"Fizz",
"Buzz",
11,
"Fizz",
13,
14,
"FizzBuzz",
], f"{got=}"
assert (got := solve(5)) == [1, 2, "Fizz", 4, "Buzz"], f"{got=}"
assert (got := solve(1)) == [1], f"{got=}"
assert (got := solve(3)) == [1, 2, "Fizz"], f"{got=}"
assert (got := solve(10)) == [
1,
2,
"Fizz",
4,
"Buzz",
"Fizz",
7,
8,
"Fizz",
"Buzz",
], f"{got=}"
assert (got := solve(20)) == [
1,
2,
"Fizz",
4,
"Buzz",
"Fizz",
7,
8,
"Fizz",
"Buzz",
11,
"Fizz",
13,
14,
"FizzBuzz",
16,
17,
"Fizz",
19,
"Buzz",
], f"{got=}"
```
# [Single Number](single_number_002.py)
Write a function `solve` that finds the number that appears only once in a list
where all other numbers appear twice.
## Solution
``` Python
def solve(nums):
return sum(set(nums)) * 2 - sum(nums)
```
## Test Cases
``` Python
assert (got := solve([4, 1, 2, 1, 2])) == 4, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([2, 2, 1])) == 1, f"{got=}"
assert (got := solve([1, 0, 1])) == 0, f"{got=}"
assert (got := solve([1, 1, 2, 2, 4])) == 4, f"{got=}"
assert (got := solve([7, 3, 7])) == 3, f"{got=}"
```
# [Majority Element](majority_element_003.py)
Write a function `solve` that finds the majority element in a list. The majority
element appears more than n/2 times where n is the length of the list.
## Solution
``` Python
def solve(nums):
return next(i for i in set(nums) if nums.count(i) > len(nums) // 2)
```
## Test Cases
``` Python
assert (got := solve([3, 2, 3])) == 3, f"{got=}"
assert (got := solve([2, 2, 1, 1, 1, 2, 2])) == 2, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (
got := solve([1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5, 5, 5, 5, 5])
) == 2, f"{got=}"
assert (got := solve([1, 1, 1, 2, 2, 2, 2, 2, 2])) == 2, f"{got=}"
assert (got := solve([1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1])) == 1, f"{got=}"
```
# [Missing Number](missing_number_004.py)
Write a function `solve` that finds the missing number in a list of numbers
from 0 to n. The list is missing one number.
## Solution
``` Python
def solve(nums):
return next(i for i in range(max(nums) + 2) if i not in nums)
```
## Test Cases
``` Python
assert (got := solve([3, 0, 1])) == 2, f"{got=}"
assert (got := solve([0, 1])) == 2, f"{got=}"
assert (got := solve([9, 6, 4, 2, 3, 5, 7, 0, 1])) == 8, f"{got=}"
assert (got := solve([0])) == 1, f"{got=}"
assert (got := solve([0, 1, 2, 3, 4, 5, 6, 7, 8])) == 9
assert (got := solve([1])) == 0, f"{got=}"
```
# [Valid Anagram](valid_anagram_005.py)
Write a function `solve` that determines if two strings are anagrams of each other.
An anagram is a word formed by rearranging the letters of another word.
## Solution
``` Python
def solve(s1, s2):
return sorted(s1) == sorted(s2)
```
## Test Cases
``` Python
assert (got := solve("listen", "silent")) is True, f"{got=}"
assert (got := solve("hello", "world")) is False, f"{got=}"
assert (got := solve("rat", "tar")) is True, f"{got=}"
assert (got := solve("", "")) is True, f"{got=}"
assert (got := solve("anagram", "nagaram")) is True, f"{got=}"
assert (got := solve("aaabbb", "ab")) is False, f"{got=}"
```
# [Maximum Subarray](maximum_subarray_006.py)
Write a function `solve` that finds the nonempty contiguous subarray with the
largest sum in a list.
## Solution
``` Python
def solve(nums):
n = len(nums)
return max(sum(nums[i:j]) for i in range(n) for j in range(i + 1, n + 1))
```
## Test Cases
``` Python
assert (got := solve([-2, 1, -3, 4, -1, 2, 1, -5, 4])) == 6, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([5, 4, -1, 7, 8])) == 23, f"{got=}"
assert (got := solve([-1])) == -1, f"{got=}"
assert (got := solve([-2, 1])) == 1, f"{got=}"
assert (got := solve([-2, -1])) == -1, f"{got=}"
```
# [Valid Parentheses](valid_parentheses_007.py)
Write a function `solve` that determines if a string `s` of parentheses is
valid. Valid parentheses must be closed in the correct order.
## Solution
``` Python
def solve(s):
stack, expect = [], dict(zip("([{", ")]}"))
for c in s:
if c in expect.keys():
stack.append(expect[c])
elif not stack or c != stack.pop():
return False
return not stack
```
## Test Cases
``` Python
assert (got := solve("()[]{}")) is True, f"{got=}"
assert (got := solve("(]")) is False, f"{got=}"
assert (got := solve("")) is True, f"{got=}"
assert (got := solve("([)]")) is False, f"{got=}"
assert (got := solve("{[]}")) is True, f"{got=}"
assert (got := solve("((")) is False, f"{got=}"
assert (got := solve(")")) is False, f"{got=}"
```
# [Two Sum](two_sum_008.py)
Write a function `solve` that finds two numbers in a list that add up to a
target value. Return a list with their indices in order. If the target cannot
be made, return an empty list.
## Solution
``` Python
from itertools import combinations as c
def solve(nums, target):
result = [[p, i] for (p, a), (i, r) in c(enumerate(nums), 2) if a + r == target]
return result[0] if result else result
```
## Test Cases
``` Python
assert (got := solve([2, 7, 11, 15], 9)) == [0, 1], f"{got=}"
assert (got := solve([3, 2, 4], 6)) == [1, 2], f"{got=}"
assert (got := solve([3, 3], 6)) == [0, 1], f"{got=}"
assert (got := solve([1, 2, 3, 4], 7)) == [2, 3], f"{got=}"
assert (got := solve([1, 5, 8, 3], 11)) == [2, 3], f"{got=}"
assert (got := solve([1, 2, 3, 4], 8)) == [], f"{got=}"
```
# [Sliding Window Maximum](sliding_window_maximum_009.py)
Write a function `solve` that returns the maximum number in each window of
size `k` sliding from left to right in a list.
Your function should return a list of ints.
## Solution
``` Python
def solve(nums, k):
return [max(nums[i : i + k]) for i in range(len(nums) - k + 1)]
```
## Test Cases
``` Python
assert (got := solve([1, 3, -1, -3, 5, 3, 6, 7], 3)) == [
3,
3,
5,
5,
6,
7,
], f"{got=}"
assert (got := solve([1, 2, 3, 4], 2)) == [2, 3, 4], f"{got=}"
assert (got := solve([1], 1)) == [1], f"{got=}"
assert (got := solve([1, 2, 3], 3)) == [3], f"{got=}"
assert (got := solve([1, -1], 1)) == [1, -1], f"{got=}"
assert (got := solve([4, 2, 3, 1, 5, 6], 4)) == [4, 5, 6], f"{got=}"
```
# [First Missing Positive](first_missing_positive_010.py)
Write a function `solve` that finds the first missing positive integer given
an unsorted list. That is, the smallest positive integer not in the list.
## Solution
``` Python
def solve(nums):
return min(set(range(1, max(nums) + 2)) - set(nums))
```
## Test Cases
``` Python
assert (got := solve([3, 4, -1, 1])) == 2, f"{got=}"
assert (got := solve([1, 2, 0])) == 3, f"{got=}"
assert (got := solve([7, 8, 9, 11, 12])) == 1, f"{got=}"
assert (got := solve([1])) == 2, f"{got=}"
assert (got := solve([-5, -3, -2, 1])) == 2, f"{got=}"
assert (got := solve([1, 1, 2, 2])) == 3, f"{got=}"
```
# [Palindrome Check](palindrome_check_011.py)
Write a function `solve` that checks if a string is a palindrome, considering
only alphanumeric characters and ignoring case.
## Solution
``` Python
def solve(s):
return (r := "".join(i for i in s.lower() if i.isalnum())) == r[::-1]
```
## Test Cases
``` Python
assert (got := solve("A man, a plan, a canal: Panama")) is True, f"{got=}"
assert (got := solve("race a car")) is False, f"{got=}"
assert (got := solve("")) is True, f"{got=}"
assert (got := solve("0p")) is False, f"{got=}"
assert (got := solve("Was it a car or a cat I saw?")) is True, f"{got=}"
assert (got := solve("12321")) is True, f"{got=}"
```
# [Count Islands (Square)](count_islands_012.py)
Write a function `solve` that counts the number of islands in a 2D grid.
An island is surrounded by water (0s) and is formed by connecting adjacent
lands (1s) horizontally or vertically.
## Solution
``` Python
def solve(nums):
def bound(x, y):
return 0 <= x < len(nums) and 0 <= y < len(nums[0])
def dfs(x, y):
seen.append((x, y))
for i, j in [(x + i, y + j) for i, j in dir if bound(x + i, y + j)]:
if nums[i][j] and (i, j) not in seen:
dfs(i, j)
number, seen, dir = 0, [], [(-1, 0), (0, 1), (1, 0), (0, -1)]
for x in range(len(nums)):
for y in range(len(nums[0])):
if nums[x][y] and (x, y) not in seen:
number += 1
dfs(x, y)
return number
```
## Test Cases
``` Python
assert (got := solve([[1, 1, 0], [0, 1, 0], [1, 0, 1]])) == 3, f"{got=}"
assert (got := solve([[1, 1, 1], [1, 1, 1], [1, 1, 1]])) == 1, f"{got=}"
assert (got := solve([[0, 0, 0], [0, 0, 0], [0, 0, 0]])) == 0, f"{got=}"
assert (got := solve([[1, 0, 1], [0, 1, 0], [1, 0, 1]])) == 5, f"{got=}"
assert (got := solve([[1]])) == 1, f"{got=}"
assert (got := solve([[1, 1], [1, 1]])) == 1, f"{got=}"
```
# [Running Sum](running_sum_013.py)
Write a function `solve` that returns the running sum of a list. The running
sum is the sum of all elements up to each index.
## Solution
``` Python
def solve(nums):
return [sum(nums[: i + 1]) for i, _ in enumerate(nums)]
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) == [1, 3, 6, 10], f"{got=}"
assert (got := solve([1, 1, 1, 1, 1])) == [1, 2, 3, 4, 5], f"{got=}"
assert (got := solve([3, 1, 2, 10, 1])) == [3, 4, 6, 16, 17], f"{got=}"
assert (got := solve([1])) == [1], f"{got=}"
assert (got := solve([-1, -2, -3])) == [-1, -3, -6], f"{got=}"
assert (got := solve([0, 0, 0])) == [0, 0, 0], f"{got=}"
```
# [Reverse Words](reverse_words_014.py)
Write a function `solve` that reverses the words in a string.
Words are separated by spaces.
## Solution
``` Python
def solve(s):
return " ".join(reversed(s.split()))
```
## Test Cases
``` Python
assert (got := solve("the sky is blue")) == "blue is sky the", f"{got=}"
assert (got := solve("hello world")) == "world hello", f"{got=}"
assert (got := solve("a good example")) == "example good a", f"{got=}"
assert (got := solve("")) == "", f"{got=}"
assert (got := solve("one")) == "one", f"{got=}"
assert (
got := solve("a b c d e f g h i j k l m n o p q r s t u v w x y z")
) == "z y x w v u t s r q p o n m l k j i h g f e d c b a", f"{got=}"
```
# [Matrix Rotation](matrix_rotation_015.py)
Write a function `solve` that rotates an `n` x `n` matrix
90 degrees clockwise in place.
## Solution
``` Python
def solve(s):
return [list(i)[::-1] for i in zip(*s)]
```
## Test Cases
``` Python
assert (got := solve([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) == [
[7, 4, 1],
[8, 5, 2],
[9, 6, 3],
], f"{got=}"
assert (got := solve([[1]])) == [[1]], f"{got=}"
assert (got := solve([[1, 2], [3, 4]])) == [[3, 1], [4, 2]], f"{got=}"
assert (
got := solve([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
) == [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]], f"{got=}"
assert (got := solve([[0, 0], [0, 1]])) == [[0, 0], [1, 0]], f"{got=}"
assert (got := solve([[1, 1, 1], [2, 2, 2], [3, 3, 3]])) == [
[3, 2, 1],
[3, 2, 1],
[3, 2, 1],
], f"{got=}"
```
# [Longest Consecutive Sequence](longest_consecutive_sequence_016.py)
Write a function `solve` that finds the length of the longest consecutive
sequence in an unsorted list.
## Solution
``` Python
def solve(nums):
res, nums = 0, set(nums)
for num in nums:
if num - 1 not in nums:
cur, seq = num, 1
while cur + 1 in nums:
cur, seq = cur + 1, seq + 1
res = max(res, seq)
return res
```
## Test Cases
``` Python
assert (got := solve([100, 4, 200, 1, 3, 2])) == 4, f"{got=}"
assert (got := solve([0, 3, 7, 2, 5, 8, 4, 6, 1])) == 9, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([1, 2, 0, 1])) == 3, f"{got=}"
assert (got := solve([1, 1, 1, 1])) == 1, f"{got=}"
```
# [Count Vowels](count_vowels_017.py)
Write a function `solve` that counts the number of vowels (a,e,i,o,u)
in a string, ignoring case.
## Solution
``` Python
def solve(text):
return sum(text.lower().count(v) for v in "aeiou")
```
## Test Cases
``` Python
assert (got := solve("Hello World")) == 3, f"{got=}"
assert (got := solve("AEIOU")) == 5, f"{got=}"
assert (got := solve("xyz")) == 0, f"{got=}"
assert (got := solve("")) == 0, f"{got=}"
assert (got := solve("aEiOu")) == 5, f"{got=}"
assert (got := solve("Python Programming")) == 4, f"{got=}"
```
# [Pascal's Triangle](pascals_triangle_018.py)
Write a function `solve` that generates the first n rows of
[Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle).
## Solution
``` Python
def solve(n):
if n == 0:
return []
res = [[1]]
for i in range(1, n):
p, x = res[-1], [1]
for j in range(1, i):
x.append(p[j - 1] + p[j])
x.append(1)
res.append(x)
return res
```
## Test Cases
``` Python
assert (got := solve(3)) == [[1], [1, 1], [1, 2, 1]], f"{got=}"
assert (got := solve(1)) == [[1]], f"{got=}"
assert (got := solve(4)) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]], f"{got=}"
assert (got := solve(5)) == [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
], f"{got=}"
assert (got := solve(2)) == [[1], [1, 1]], f"{got=}"
assert (got := solve(0)) == [], f"{got=}"
```
# [Binary Tree Maximum Depth](binary_tree_maximum_depth_019.py)
Write a function that finds the maximum depth of a binary tree.
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. The tree is represented as
an array of nodes in [level-order traversal][1]. None indicates empty nodes.
[1]: https://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_search
## Solution
``` Python
def solve(root):
return max(solve(root.left), solve(root.right)) + 1 if root else 0
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([3, 9, 20, None, None, 15, 7]))) == 3, f"{got=}"
assert (got := solve(None)) == 0, f"{got=}"
assert (got := solve(bt([1]))) == 1, f"{got=}"
assert (got := solve(bt([1, 2]))) == 2, f"{got=}"
assert (got := solve(bt([1, None, 2]))) == 2, f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, 5]))) == 3, f"{got=}"
```
# [Reverse Linked List](reverse_linked_list_020.py)
Write a function that, given the head of a singly linked list,
reverses the list. Return the root node of the reversed list.
## Solution
``` Python
def solve(head):
p = None
while head:
head.next, p, head = p, head, head.next
return p
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([1, 2, 3, 4, 5])))) == [5, 4, 3, 2, 1], f"{got=}"
assert (got := t(solve(sl([])))) == [], f"{got=}"
assert (got := t(solve(sl([1])))) == [1], f"{got=}"
assert (got := t(solve(sl([2, 2, 2])))) == [2, 2, 2], f"{got=}"
assert (got := t(solve(sl([1, 2, 3, 4])))) == [4, 3, 2, 1], f"{got=}"
assert (got := t(solve(sl([2, 5, 2, 1, 3])))) == [3, 1, 2, 5, 2], f"{got=}"
```
# [Factorial](factorial_021.py)
Write a function `solve` that returns the factorial of a given integer n.
Return 1 if n is 0.
## Solution
``` Python
from math import factorial as solve
```
## Test Cases
``` Python
assert (got := solve(0)) == 1, f"{got=}"
assert (got := solve(1)) == 1, f"{got=}"
assert (got := solve(5)) == 120, f"{got=}"
assert (got := solve(7)) == 5_040, f"{got=}"
assert (got := solve(10)) == 3_628_800, f"{got=}"
assert (got := solve(12)) == 479_001_600, f"{got=}"
```
# [Merge Sorted Lists](merge_sorted_lists_022.py)
Write a function `solve` that merges two sorted lists into one sorted list.
## Solution
``` Python
def solve(list1, list2):
result, i1, i2 = [], 0, 0
while i1 < len(list1) and i2 < len(list2):
b = 1 - (list1[i1] < list2[i2])
result.append((list1, list2)[b][(i1, i2)[b]])
i1, i2 = i1 + 1 - b, i2 + b
return result + list1[i1:] + list2[i2:]
```
## Test Cases
``` Python
assert (got := solve([1, 3, 5], [2, 4, 6])) == [1, 2, 3, 4, 5, 6], f"{got=}"
assert (got := solve([], [])) == [], f"{got=}"
assert (got := solve([1], [2])) == [1, 2], f"{got=}"
assert (got := solve([1, 2, 7], [2, 2, 3])) == [1, 2, 2, 2, 3, 7], f"{got=}"
assert (got := solve([0, 0, 0], [0, 0, 0])) == [0, 0, 0, 0, 0, 0], f"{got=}"
assert (got := solve([1, 2, 3], [4, 5, 6])) == [1, 2, 3, 4, 5, 6], f"{got=}"
```
# [Validate Palindromic Number](validate_palindromic_number_023.py)
Write a function `solve` that checks whether an integer is a palindrome
without converting it to a string.
## Solution
``` Python
def solve(num):
res = []
while num > 0:
res.append(num % 10)
num //= 10
return num >= 0 and res == res[::-1]
```
## Test Cases
``` Python
assert (got := solve(121)) is True, f"{got=}"
assert (got := solve(-121)) is False, f"{got=}"
assert (got := solve(10)) is False, f"{got=}"
assert (got := solve(0)) is True, f"{got=}"
assert (got := solve(12321)) is True, f"{got=}"
assert (got := solve(12345)) is False, f"{got=}"
```
# [Minimum Rotated Sorted Array](minimum_rotated_sorted_array_024.py)
Write a function `solve` that finds the minimum element
in a rotated sorted array.
## Solution
``` Python
def solve(nums):
if len(nums) < 2:
return (nums + [None])[0]
for i in range(len(nums)):
if nums[i] > nums[i + 1]:
return nums[i + 1]
```
## Test Cases
``` Python
assert (got := solve([3, 4, 5, 1, 2])) == 1, f"{got=}"
assert (got := solve([4, 5, 6, 7, 0, 1, 2])) == 0, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([2, 1])) == 1, f"{got=}"
assert (got := solve([5, 6, 7, 8, 9, 1, 2, 3, 4])) == 1, f"{got=}"
assert (got := solve([10, 1, 10, 10, 10])) == 1, f"{got=}"
```
# [Climbing Stairs](climbing_stairs_025.py)
Write a function `solve` that calculates how many distinct ways you can climb
a staircase of n steps, taking 1 or 2 steps at a time.
## Solution
``` Python
def solve(n):
return n if n <= 3 else solve(n - 1) + solve(n - 2)
```
## Test Cases
``` Python
assert (got := solve(1)) == 1, f"{got=}"
assert (got := solve(2)) == 2, f"{got=}"
assert (got := solve(3)) == 3, f"{got=}"
assert (got := solve(5)) == 8, f"{got=}"
assert (got := solve(10)) == 89, f"{got=}"
assert (got := solve(20)) == 10_946, f"{got=}"
```
# [Merge Intervals](merge_intervals_026.py)
Write a function `solve` that merges overlapping intervals and returns the
merged list. Intervals are represented as lists of two integers: start and end.
## Solution
``` Python
def solve(intervals):
output = []
for x, y in intervals:
for i, (w, z) in enumerate(output):
r = range(w, z + 1)
if x in r or y in r:
output[i] = [min(x, w), max(y, z)]
break
else:
output.append([x, y])
return output
```
## Test Cases
``` Python
assert (got := solve([[1, 3], [2, 6], [8, 10], [15, 18]])) == [
[1, 6],
[8, 10],
[15, 18],
], f"{got=}"
assert (got := solve([[1, 4], [4, 5]])) == [[1, 5]], f"{got=}"
assert (got := solve([[1, 3]])) == [[1, 3]], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([[1, 2], [2, 3], [3, 4]])) == [[1, 4]], f"{got=}"
assert (got := solve([[1, 4], [2, 3]])) == [[1, 4]], f"{got=}"
```
# [Power Of Two](power_of_two_027.py)
Write a function `solve` that checks if an integer is a power of two.
## Solution
``` Python
def solve(n):
return n.bit_count() == 1
```
## Test Cases
``` Python
assert (got := solve(1)) is True, f"{got=}"
assert (got := solve(16)) is True, f"{got=}"
assert (got := solve(3)) is False, f"{got=}"
assert (got := solve(0)) is False, f"{got=}"
assert (got := solve(32)) is True, f"{got=}"
assert (got := solve(64)) is True, f"{got=}"
```
# [Reverse Integer](reverse_integer_028.py)
Write a function solve that reverses the digits of an integer. If the reversed
integer overflows, return 0.
Assume the input is a 32-bit signed integer, so the reversed integer must be
within the range [-2^31, 2^31-1].
## Solution
``` Python
def solve(n):
an, out = abs(n), 0
while an:
out, an = out * 10 + an % 10, an // 10
return 0 if out.bit_length() > 31 else out if n > 0 else -out
```
## Test Cases
``` Python
assert (got := solve(123)) == 321, f"{got=}"
assert (got := solve(-123)) == -321, f"{got=}"
assert (got := solve(120)) == 21, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(1534236469)) == 0, f"{got=}"
assert (got := solve(-2147483648)) == 0, f"{got=}"
```
# [Queue Reconstruction by Height](queue_reconstruction_by_height_029.py)
Write a function `solve` that reconstructs a queue based on the heights of
people and the number of people in front of them. Each person is represented by
a pair [height, k], where height is the person's height and k is greater than
or equal to the number of people in front of this person (BEFORE them in the
list) who have a height greater than or equal to height.
## Solution
``` Python
def solve(people):
out = []
for p in sorted(people, key=lambda x: (-x[0], x[1])):
out.insert(p[1], p)
return out
```
## Test Cases
``` Python
assert (got := solve([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]])) == [
[5, 0],
[7, 0],
[5, 2],
[6, 1],
[4, 4],
[7, 1],
], f"{got=}"
assert (got := solve([[1, 0], [2, 0], [3, 0]])) == [
[1, 0],
[2, 0],
[3, 0],
], f"{got=}"
assert (got := solve([[1, 1], [2, 0], [3, 0]])) == [
[2, 0],
[1, 1],
[3, 0],
], f"{got=}"
assert (got := solve([[1, 1], [2, 0], [3, 1]])) == [
[2, 0],
[1, 1],
[3, 1],
], f"{got=}"
assert (got := solve([[1, 1], [2, 1], [3, 1]])) == [
[3, 1],
[1, 1],
[2, 1],
], f"{got=}"
assert (got := solve([[1, 0], [2, 1], [3, 2]])) == [
[1, 0],
[3, 2],
[2, 1],
], f"{got=}"
```
# [Remove Duplicates from Sorted Array](remove_duplicates_from_sorted_array_030.py)
Write a function `solve` that removes duplicates from a sorted array in-place,
and return the new length.
## Solution
``` Python
def solve(nums):
return len(set(nums))
```
## Test Cases
``` Python
assert (got := solve([1, 1, 2])) == 2, f"{got=}"
assert (got := solve([0, 0, 1, 1, 1, 2, 2, 3, 3, 4])) == 5, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([1, 1, 1, 1, 1])) == 1, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == 5, f"{got=}"
assert (got := solve([1, 1, 2, 2, 3, 3])) == 3, f"{got=}"
```
# [Length of Last Word](length_of_last_word_031.py)
Write a function `solve` that returns the length of the last word in a string.
## Solution
``` Python
def solve(s):
return len(x.rsplit(None, 1)[-1]) if (x := s.rstrip()) else 0
```
## Test Cases
``` Python
assert (got := solve("Hello World")) == 5, f"{got=}"
assert (got := solve("fly me to the moon ")) == 4, f"{got=}"
assert (got := solve("luffy is still joyboy")) == 6, f"{got=}"
assert (got := solve("")) == 0, f"{got=}"
assert (got := solve("one two three")) == 5, f"{got=}"
assert (
got := solve("a b c d e f g h i j k l m n o p q r s t u v w x y z")
) == 1, f"{got=}"
assert (got := solve(" ")) == 0, f"{got=}"
```
# [Find First and Last Position of Element in Sorted Array](fflpesa_032.py)
Write a function `solve` that finds the starting and ending position of a
target value in a sorted array. If the target is not found, return [-1,-1].
Ideally, your solution should run in O(logn) time.
## Solution
``` Python
def solve(nums, target):
results = []
for i, op in enumerate([int.__lt__, int.__le__]):
span = 0, len(nums) - 1
while span[0] <= span[1]:
mid = (span[0] + span[1]) // 2
span = (mid + 1, span[1]) if op(nums[mid], target) else (span[0], mid - 1)
results.append(span[i])
return results if results[0] <= results[1] else [-1, -1]
```
## Test Cases
``` Python
assert (got := solve([5, 7, 7, 8, 8, 10], 8)) == [3, 4], f"{got=}"
assert (got := solve([5, 7, 7, 8, 8, 10], 6)) == [-1, -1], f"{got=}"
assert (got := solve([], 0)) == [-1, -1], f"{got=}"
assert (got := solve([1], 1)) == [0, 0], f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 3)) == [2, 2], f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 6)) == [-1, -1], f"{got=}"
```
# [Number of Steps to Reduce to Zero](number_of_steps_to_reduce_to_zero__033.py)
Write a function `solve` that returns the number of steps to reduce a
non-negative integer to zero. If it's even, divide by 2; if it's odd, subtract 1.
## Solution
``` Python
def solve(num):
return max([0, num.bit_length() + num.bit_count() - 1])
```
## Test Cases
``` Python
assert (got := solve(14)) == 6, f"{got=}"
assert (got := solve(8)) == 4, f"{got=}"
assert (got := solve(123)) == 12, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(1)) == 1, f"{got=}"
assert (got := solve(2)) == 2, f"{got=}"
```
# [Binary Tree Inorder Traversal](binary_tree_inorder_traversal_034.py)
Write a function `solve` that returns the inorder traversal of a
binary tree's nodes' values.
## Solution
``` Python
def solve(root):
if root is None:
return []
return solve(root.left) + [root.val] + solve(root.right)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, None, 2, 3]))) == [1, 3, 2], f"{got=}"
assert (got := solve(None)) == [], f"{got=}"
assert (got := solve(bt([1]))) == [1], f"{got=}"
assert (got := solve(bt([1, 2]))) == [2, 1], f"{got=}"
assert (got := solve(bt([1, None, 2]))) == [1, 2], f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, 5, 6, 7]))) == [
4,
2,
5,
1,
6,
3,
7,
], f"{got=}"
```
# [Counting Bits](counting_bits_035.py)
Write a function `solve` that returns an array of the number of 1-bits
(Hamming weight) for each number from 0 to n.
## Solution
``` Python
def solve(n):
return [i.bit_count() for i in range(n + 1)]
```
## Test Cases
``` Python
assert (got := solve(2)) == [0, 1, 1], f"{got=}"
assert (got := solve(5)) == [0, 1, 1, 2, 1, 2], f"{got=}"
assert (got := solve(10)) == [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2], f"{got=}"
assert (got := solve(0)) == [0], f"{got=}"
assert (got := solve(1)) == [0, 1], f"{got=}"
assert (got := solve(3)) == [0, 1, 1, 2], f"{got=}"
```
# [Single Linked List Middle](single_linked_list_middle_036.py)
Write a function `solve` that returns the middle node of a singly linked list.
If two middles, return the second one.
## Solution
``` Python
def solve(head):
tortoise = hare = head
while hare and hare.next:
tortoise = tortoise.next
hare = hare.next.next
return tortoise
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
assert (got := solve(sl([1, 2, 3, 4, 5])).val) == 3, f"{got=}"
assert (got := solve(sl([1, 2, 3, 4, 5, 6])).val) == 4, f"{got=}"
assert (got := solve(sl([1, 2, 3])).val) == 2, f"{got=}"
assert (got := solve(sl([1, 2])).val) == 2, f"{got=}"
assert (got := solve(sl([1])).val) == 1, f"{got=}"
assert (got := solve(sl([1, 2, 3, 4, 5, 6, 7])).val) == 4, f"{got=}"
```
# [Count Prime Numbers](count_prime_numbers_037.py)
Write a function `solve` that counts the number of prime numbers less than n.
## Solution
``` Python
def solve(n):
multiples, primes = {0, 1}, set()
for i in range(2, n):
if i not in multiples:
primes.add(i)
for j in range(i * i, n + 1, i):
multiples.add(j)
return len(primes)
```
## Test Cases
``` Python
assert (got := solve(10)) == 4, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(1)) == 0, f"{got=}"
assert (got := solve(2)) == 0, f"{got=}"
assert (got := solve(30)) == 10, f"{got=}"
assert (got := solve(50)) == 15, f"{got=}"
```
# [Balanced Binary Tree](balanced_binary_tree_038.py)
Write a function `solve` that checks if a binary tree is height-balanced.
A height-balanced binary tree is defined as a binary tree in which the left
and right subtrees of every node differ in height by no more than 1.
## Solution
``` Python
def solve(root):
def height(node):
if not node:
return 0
return max(height(node.left), height(node.right)) + 1
if not root:
return True
if abs(height(root.left) - height(root.right)) > 1:
return False
return solve(root.left) and solve(root.right)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([3, 9, 20, None, None, 15, 7]))) is True, f"{got=}"
assert (got := solve(bt([]))) is True, f"{got=}"
assert (got := solve(bt([1, 2, 2, 3, 3, None, None, 4, 4]))) is False, f"{got=}"
assert (
got := solve(bt([1, 2, 2, 3, None, None, 3, 4, None, None, 4]))
) is False, f"{got=}"
assert (
got := solve(bt([1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, None, None, 5, 5]))
) is True, f"{got=}"
assert (got := solve(bt([1, 2, 2, 3, 3, None, None, 4, 4]))) is False, f"{got=}"
```
# [Armstrong Number](armstrong_number_039.py)
Write a function `solve` that checks if an integer is an Armstrong number
(a.k.a Narcissistic number).
## Solution
``` Python
def solve(num):
return sum(int(i) ** len(str(num)) for i in str(num)) == num
```
## Test Cases
``` Python
assert (got := solve(153)) is True, f"{got=}"
assert (got := solve(370)) is True, f"{got=}"
assert (got := solve(9474) is True), f"{got=}"
assert (got := solve(123)) is False, f"{got=}"
assert (got := solve(407)) is True, f"{got=}"
assert (got := solve(1634)) is True, f"{got=}"
```
# [Zigzag Conversion](zigzag_conversion_040.py)
Write a function `solve` that reads a string in a zigzag pattern on a given
number of rows, then returns the row-by-row read string. If 'zigzag pattern'
is unclear, see the relevant question.
## Solution
``` Python
def solve(s, numRows):
if numRows <= 1:
return s
rows, row, step = [""] * numRows, 0, 1
for c in s:
rows[row] += c
step = 1 if row == 0 else -1 if row == numRows - 1 else step
row += step
return "".join(rows)
```
## Test Cases
``` Python
assert (got := solve("PAYPALISHIRING", 3)) == "PAHNAPLSIIGYIR", f"{got=}"
assert (got := solve("PAYPALISHIRING", 4)) == "PINALSIGYAHRPI", f"{got=}"
assert (got := solve("ABC", 1)) == "ABC", f"{got=}"
assert (got := solve("HELLO", 2)) == "HLOEL", f"{got=}"
assert (got := solve("ZIGZAG", 3)) == "ZAIZGG", f"{got=}"
assert (got := solve("PYTHON", 4)) == "PYNTOH", f"{got=}"
```
# [3Sum Closest](three_sum_closest_041.py)
Write a function `solve` that finds the sum of three integers in an array that
is closest to a target number. Return the sum of the three integers. You may
assume that each input would have exactly one solution.
## Solution
``` Python
def solve(nums, target):
nums.sort()
result = sum(nums[:3])
for i in range(len(nums) - 2):
begin, end = i + 1, len(nums) - 1
while begin < end:
current = nums[i] + nums[begin] + nums[end]
if abs(current - target) <= abs(result - target):
result = max(result, current)
if current > target:
end -= 1
else:
begin += 1
return result
```
## Test Cases
``` Python
assert (got := solve([-1, 2, 1, -4], 1)) == 2, f"{got=}"
assert (got := solve([0, 0, 0], 1)) == 0, f"{got=}"
assert (got := solve([1, 1, 1, 1], 0)) == 3, f"{got=}"
assert (got := solve([1, 1, 1, 1], 4)) == 3, f"{got=}"
assert (got := solve([1, 1, 1, 1], 2)) == 3, f"{got=}"
assert (got := solve([1, 1, 1, 1], 3)) == 3, f"{got=}"
assert (got := solve([1, 2, 6, 10], 13)) == 13, f"{got=}"
```
# [Longest Substring Without Repeating Characters](lswrc_042.py)
Write a function `solve` that finds the length of the longest substring without
repeating characters.
## Solution
``` Python
def solve(s):
chars, start, length = {}, 0, 0
for i, c in enumerate(s):
if c in chars and chars[c] >= start:
start = chars[c] + 1
else:
length = max(length, i - start + 1)
chars[c] = i
return length
```
## Test Cases
``` Python
assert (got := solve("abcabcbb")) == 3, f"{got=}"
assert (got := solve("bbbbb")) == 1, f"{got=}"
assert (got := solve("pwwkew")) == 3, f"{got=}"
assert (got := solve("")) == 0, f"{got=}"
assert (got := solve("dvdf")) == 3, f"{got=}"
assert (got := solve("aab")) == 2, f"{got=}"
```
# [Divide Two Integers](divide_two_integers_043.py)
Write a function `solve` that divides two integers without using multiplication,
division, and mod operator. Return the quotient as an int after dividing.
Assume 32-bit signed integers.
## Solution
``` Python
def solve(dividend, divisor):
neg = (dividend < 0) ^ (divisor < 0)
dividend, divisor = abs(dividend), abs(divisor)
if divisor == 0:
return None
result = 0
while dividend >= divisor:
dividend -= divisor
result += 1
return -result if neg else result
```
## Test Cases
``` Python
assert (got := solve(10, 3)) == 3, f"{got=}"
assert (got := solve(7, -3)) == -2, f"{got=}"
assert (got := solve(0, 1)) == 0, f"{got=}"
assert (got := solve(1, 1)) == 1, f"{got=}"
assert (got := solve(1, 2)) == 0, f"{got=}"
assert (got := solve(100, 1)) == 100, f"{got=}"
```
# [Longest Palindromic Substring](longest_palindromic_substring_044.py)
Write a function `solve` that finds the longest palindromic substring in a string.
## Solution
``` Python
def solve(s):
ss, begin, size = len(s), 0, 1
if ss == 0:
return ""
for i in range(ss):
for j in range(2):
low, high = i, i + j
while low >= 0 and high < ss and s[low] == s[high]:
newsize = high - low + 1
if newsize > size:
begin, size = low, newsize
low, high = low - 1, high + 1
return s[begin : begin + size]
```
## Test Cases
``` Python
assert (got := solve("babd")) == "bab", f"{got=}"
assert (got := solve("cbbd")) == "bb", f"{got=}"
assert (got := solve("a")) == "a", f"{got=}"
assert (got := solve("ac")) == "a", f"{got=}"
assert (got := solve("racecar")) == "racecar", f"{got=}"
assert (got := solve("aaaaaa")) == "aaaaaa", f"{got=}"
```
# [Regular Expression Matching](regular_expression_matching_045.py)
Write a function `solve` that implements regular expression matching with
support for '.' and '*'. '.' matches any single character, '*' matches zero or
more of the preceding element.
## Solution
``` Python
def solve(s, p):
if not p:
return not s
match = bool(s) and p[0] in {s[0], "."}
if len(p) >= 2 and p[1] == "*":
return solve(s, p[2:]) or match and solve(s[1:], p)
else:
return match and solve(s[1:], p[1:])
```
## Test Cases
``` Python
assert (got := solve("aa", "a*")) is True, f"{got=}"
assert (got := solve("ab", ".*")) is True, f"{got=}"
assert (got := solve("mississippi", "mis*is*p*.")) is False, f"{got=}"
assert (got := solve("", ".*")) is True, f"{got=}"
assert (got := solve("aab", "c*a*b")) is True, f"{got=}"
assert (got := solve("ab", ".*c")) is False, f"{got=}"
```
# [Container With Most Water](container_with_most_water_046.py)
Write a function `solve` that finds two lines that together with the x-axis
forms a container, such that the container contains the most water.
## Solution
``` Python
def solve(height):
result, left, right = 0, 0, len(height) - 1
while left < right:
result = max(result, min(height[left], height[right]) * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return result
```
## Test Cases
``` Python
assert (got := solve([1, 8, 6, 2, 5, 4, 8, 3, 7])) == 49, f"{got=}"
assert (got := solve([1, 1])) == 1, f"{got=}"
assert (got := solve([4, 3, 2, 1, 4])) == 16, f"{got=}"
assert (got := solve([1, 2, 4, 3])) == 4, f"{got=}"
assert (got := solve([1, 2, 1])) == 2, f"{got=}"
assert (got := solve([1, 8, 100, 2, 100, 4, 8, 3, 7])) == 200, f"{got=}"
```
# [Integer to Roman](integer_to_roman_047.py)
Write a function `solve` that converts an integer to a roman numeral.
## Solution
``` Python
def solve(num):
roman = dict(
zip(
(1_000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1),
"M CM D CD C XC L XL X IX V IV I".split(),
)
)
result = ""
for i in roman:
if num > 0:
times, num = divmod(num, i)
result += roman[i] * times
return result
```
## Test Cases
``` Python
assert (got := solve(3)) == "III", f"{got=}"
assert (got := solve(58)) == "LVIII", f"{got=}"
assert (got := solve(1994)) == "MCMXCIV", f"{got=}"
assert (got := solve(3999)) == "MMMCMXCIX", f"{got=}"
assert (got := solve(9)) == "IX", f"{got=}"
assert (got := solve(40)) == "XL", f"{got=}"
```
# [Add Binary](add_binary_048.py)
Write a function `solve` that adds two binary strings and returns their sum
as a binary string.
## Solution
``` Python
def solve(a, b):
return bin(int(a, 2) + int(b, 2))[2:]
```
## Test Cases
``` Python
assert (got := solve("11", "1")) == "100", f"{got=}"
assert (got := solve("1010", "1011")) == "10101", f"{got=}"
assert (got := solve("0", "0")) == "0", f"{got=}"
assert (got := solve("1111", "1111")) == "11110", f"{got=}"
assert (got := solve("1", "111")) == "1000", f"{got=}"
assert (got := solve("1001", "1")) == "1010", f"{got=}"
```
# [Remove Nth Node From End of List](remove_nth_node_from_end_of_list_049.py)
Write a function `solve` that removes the nth node from the end of a singly
linked list. Return the head.
## Solution
``` Python
def solve(head, n):
tortoise = hare = head
for _ in range(n):
hare = hare.next
if not hare:
return head.next
while hare and hare.next:
hare, tortoise = hare.next, tortoise.next
tortoise.next = tortoise.next.next
return head
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([1, 2, 3, 4, 5]), 2))) == [1, 2, 3, 5], f"{got=}"
assert (got := t(solve(sl([1]), 1))) == [], f"{got=}"
assert (got := t(solve(sl([1, 2]), 1))) == [1], f"{got=}"
assert (got := t(solve(sl([1, 2]), 2))) == [2], f"{got=}"
assert (got := t(solve(sl([1, 2, 3]), 3))) == [2, 3], f"{got=}"
assert (got := t(solve(sl([2, 4, 6, 8, 10]), 5))) == [4, 6, 8, 10], f"{got=}"
```
# [Invert a Binary Tree](invert_a_binary_tree_050.py)
Write a function `solve` that inverts a binary tree.
Return the root of the inverted tree.
## Solution
``` Python
def solve(root):
if root:
root.left, root.right = solve(root.right), solve(root.left)
return root
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
def t(root):
result = []
if root is None:
return []
queue = [root]
while queue:
curr = queue.pop(0)
if curr is None:
result.append(None)
continue
result.append(curr.val)
queue.append(curr.left)
queue.append(curr.right)
while result[-1] is None:
result.pop()
return result
assert (got := t(solve(bt([4, 2, 7, 1, 3, 6, 9])))) == [
4,
7,
2,
9,
6,
3,
1,
], f"{got=}"
assert (got := t(solve(bt([])))) == [], f"{got=}"
assert (got := t(solve(bt([1])))) == [1], f"{got=}"
assert (got := t(solve(bt([2, 1, 3])))) == [2, 3, 1], f"{got=}"
assert (got := t(solve(bt([3, 9, 20, None, None, 15, 7])))) == [
3,
20,
9,
7,
15,
], f"{got=}"
assert (got := t(solve(bt([1, 2, 3, 4, None, 5])))) == [
1,
3,
2,
None,
5,
None,
4,
], f"{got=}"
```
# [Majority Element II (n/3)](majority_element_ii_051.py)
Write a function `solve` that finds all elements that appear more than
n/3 times in an array.
## Solution
``` Python
def solve(nums):
return [i for i in dict.fromkeys(nums) if nums.count(i) > len(nums) // 3]
```
## Test Cases
``` Python
assert (got := solve([3, 2, 3])) == [3], f"{got=}"
assert (got := solve([1])) == [1], f"{got=}"
assert (got := solve([1, 2])) == [1, 2], f"{got=}"
assert (got := solve([2, 2, 1, 1, 1, 2, 2])) == [2, 1], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([8, 8, 8, 8, 9])) == [8], f"{got=}"
```
# [Validate BST](validate_bst_052.py)
Write a function `solve` that checks if a binary tree is
a valid binary search tree.
## Solution
``` Python
def solve(root):
val = None
while root:
if not root.left:
if val is not None and root.val <= val:
return False
val, root = root.val, root.right
else:
prev = root.left
while prev.right and prev.right != root:
prev = prev.right
if not prev.right:
prev.right, root = root, root.left
else:
prev.right = None
if val is not None and root.val <= val:
return False
val, root = root.val, root.right
return True
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([2, 1, 3]))) is True, f"{got=}"
assert (got := solve(bt([5, 1, 4, None, None, 3, 6]))) is False, f"{got=}"
assert (got := solve(bt([]))) is True, f"{got=}"
assert (got := solve(bt([1, None, 1]))) is False, f"{got=}"
assert (got := solve(bt([10, 5, 15, None, None, 6, 20]))) is False, f"{got=}"
assert (got := solve(bt([3, 2, 5, 1]))) is True, f"{got=}"
```
# [Unique Paths in a Grid](unique_paths_in_a_grid_053.py)
Write a function `solve` that returns the number of possible unique paths
to reach bottom-right from top-left in an m x n grid (only moves down or right).
## Solution
``` Python
def solve(m, n):
paths = 1
for i in range(m - 1):
paths = paths * (i + n) // (i + 1)
return paths
```
## Test Cases
``` Python
assert (got := solve(3, 7)) == 28, f"{got=}"
assert (got := solve(3, 2)) == 3, f"{got=}"
assert (got := solve(7, 3)) == 28, f"{got=}"
assert (got := solve(1, 1)) == 1, f"{got=}"
assert (got := solve(2, 2)) == 2, f"{got=}"
assert (got := solve(3, 3)) == 6, f"{got=}"
```
# [Best Time to Buy and Sell Stock](best_time_to_buy_and_sell_stock_054.py)
Write a function `solve` that calculates the maximum profit you can achieve
from buying and selling stocks multiple times. You may not engage in multiple
transactions simultaneously (i.e., you must sell the stock before you buy
again). The input is an array of prices where prices[i] is the price of a given
stock on the ith day.
## Solution
``` Python
def solve(prices):
return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))
```
## Test Cases
``` Python
assert (got := solve([7, 1, 5, 3, 6, 4])) == 7, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == 4, f"{got=}"
assert (got := solve([7, 6, 4, 3, 1])) == 0, f"{got=}"
assert (got := solve([1, 7, 2, 3, 6, 7, 6, 7])) == 12, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([2, 2, 2])) == 0, f"{got=}"
assert (got := solve([7, 10, 1, 3, 6, 9, 2])) == 11, f"{got=}"
assert (got := solve([1, 3, 6, 9, 11])) == 10, f"{got=}"
```
# [Jump Game](jump_game_055.py)
Write a function `solve` that determines if you can reach the last index in an
array. Each element represents the maximum jump length at that position.
## Solution
``` Python
def solve(nums):
x = 0
for i, n in enumerate(nums):
if x < i:
return False
x = max(x, i + n)
return True
```
## Test Cases
``` Python
assert (got := solve([2, 3, 1, 1, 4])) is True, f"{got=}"
assert (got := solve([3, 2, 1, 0, 4])) is False, f"{got=}"
assert (got := solve([0])) is True, f"{got=}"
assert (got := solve([1, 0, 1])) is False, f"{got=}"
assert (got := solve([1, 1, 1, 1, 1])) is True, f"{got=}"
assert (got := solve([1, 1, 1, 1, 0])) is True, f"{got=}"
```
# [Rotate Array (Cyclic)](rotate_array_056.py)
Write a function `solve`
## Solution
``` Python
def solve(nums, k):
return nums[-k % len(nums) :] + nums[: -k % len(nums)]
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4, 5, 6, 7], 3)) == [
5,
6,
7,
1,
2,
3,
4,
], f"{got=}"
assert (got := solve([-1, -100, 3, 99], 2)) == [3, 99, -1, -100], f"{got=}"
assert (got := solve([1], 0)) == [1], f"{got=}"
assert (got := solve([1, 2], 3)) == [2, 1], f"{got=}"
assert (got := solve([1, 2, 3], 3)) == [1, 2, 3], f"{got=}"
assert (got := solve([2, 4, 6, 8], 1)) == [8, 2, 4, 6], f"{got=}"
```
# [Valid Palindrome One Deletion](valid_palindrome_one_deletion_057.py)
Write a function `solve` that returns true if the string can become a
palindrome by deleting at most one character.
## Solution
``` Python
def solve(s):
for x in [s] + [(s[:i] + s[i + 1 :]) for i in range(len(s))]:
if (r := "".join(i for i in x.lower() if i.isalnum())) == r[::-1]:
return True
return False
```
## Test Cases
``` Python
assert (got := solve("aba")) is True, f"{got=}"
assert (got := solve("abca")) is True, f"{got=}"
assert (got := solve("abc")) is False, f"{got=}"
assert (got := solve("cbbcc")) is True, f"{got=}"
assert (got := solve("a")) is True, f"{got=}"
assert (got := solve("raceacar")) is True, f"{got=}"
```
# [Unique Paths](unique_paths_058.py)
Write a function `solve` that returns the number of unique paths if the grid
has obstacles (1 means blocked).
## Solution
``` Python
def solve(obstacleGrid):
paths = [0] * len(obstacleGrid[0])
paths[0] = int(not obstacleGrid[0][0])
for x in range(len(obstacleGrid)):
for y in range(len(obstacleGrid[0])):
if obstacleGrid[x][y] == 1:
paths[y] = 0
elif y > 0:
paths[y] += paths[y - 1]
return paths[-1]
```
## Test Cases
``` Python
assert (got := solve([[0, 0, 0], [0, 1, 0], [0, 0, 0]])) == 2, f"{got=}"
assert (got := solve([[0, 1], [0, 0]])) == 1, f"{got=}"
assert (got := solve([[1]])) == 0, f"{got=}"
assert (got := solve([[0]])) == 1, f"{got=}"
assert (got := solve([[0, 0], [1, 0]])) == 1, f"{got=}"
assert (got := solve([[0, 0], [0, 1]])) == 0, f"{got=}"
```
# [Counting Inversions](counting_inversions_059.py)
Write a function `solve` that counts the number of inversions in an array.
An inversion is a pair of elements that are out of order.
## Solution
``` Python
def solve(nums):
return len([(x, y) for i, x in enumerate(nums) for y in nums[i + 1 :] if x > y])
```
## Test Cases
``` Python
assert (got := solve([2, 4, 1, 3, 5])) == 3, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == 0, f"{got=}"
assert (got := solve([5, 4, 3, 2, 1])) == 10, f"{got=}"
assert (got := solve([1, 1, 1, 1, 1])) == 0, f"{got=}"
assert (got := solve([1, 3, 5, 2, 4, 6])) == 3, f"{got=}"
assert (got := solve([1, 5, 3, 2, 4])) == 4, f"{got=}"
```
# [Kth Largest Element](kth_largest_element_060.py)
Write a function `solve` that finds the kth largest element in an unsorted array.
## Solution
``` Python
def solve(nums, k):
return sorted(nums, reverse=True)[k - 1]
```
## Test Cases
``` Python
assert (got := solve([3, 2, 1, 5, 6, 4], 2)) == 5, f"{got=}"
assert (got := solve([3, 2, 1], 1)) == 3, f"{got=}"
assert (got := solve([2, 2, 3, 1], 2)) == 2, f"{got=}"
assert (got := solve([10, 10, 9], 1)) == 10, f"{got=}"
assert (got := solve([5, 4, 3, 2, 1], 1)) == 5, f"{got=}"
assert (got := solve([5, 4, 3, 2, 1], 5)) == 1, f"{got=}"
```
# [Longest Common Prefix](longest_common_prefix_061.py)
Write a function `solve` that finds the longest common prefix
among an array of strings.
## Solution
``` Python
def solve(strs):
if len(strs) < 2:
return ("", strs[0])[len(strs)]
strs.sort()
i = 0
while i < min(len(strs[0]), len(strs[-1])) and strs[0][i] == strs[-1][i]:
i += 1
return strs[0][:i]
```
## Test Cases
``` Python
assert (got := solve(["flower", "flow", "flight"])) == "fl", f"{got=}"
assert (got := solve(["dog", "racecar", "car"])) == "", f"{got=}"
assert (
got := solve(["interspecies", "interstellar", "interstate"])
) == "inters", f"{got=}"
assert (got := solve([""])) == "", f"{got=}"
assert (got := solve(["a"])) == "a", f"{got=}"
assert (got := solve(["prefix", "prefix"])) == "prefix", f"{got=}"
```
# [Spiral Matrix](spiral_matrix_062.py)
Write a function `solve` that returns all elements of an m x n matrix in spiral order.
## Solution
``` Python
def solve(matrix):
return matrix and [*matrix.pop(0)] + solve([*zip(*matrix)][::-1])
```
## Test Cases
``` Python
assert (got := solve([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) == [
1,
2,
3,
6,
9,
8,
7,
4,
5,
], f"{got=}"
assert (got := solve([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])) == [
1,
2,
3,
4,
8,
12,
11,
10,
9,
5,
6,
7,
], f"{got=}"
assert (got := solve([[1]])) == [1], f"{got=}"
assert (got := solve([[1, 2], [3, 4]])) == [1, 2, 4, 3], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([[1, 2, 3]])) == [1, 2, 3], f"{got=}"
```
# [Reorder List](reorder_list_063.py)
Write a function `solve` that reorders a singly linked list such that the last
element becomes the second element.
ie: `L0→L1→...→Ln-1→Ln` becomes `L0→Ln→L1→Ln-1→...`
## Solution
``` Python
def solve(head):
if not head:
return None
tortoise = hare = head
while hare and hare.next:
tortoise, hare = tortoise.next, hare.next.next
previous, current = None, tortoise
while current:
current.next, previous, current = previous, current, current.next
previous, current = head, previous
while current.next:
previous.next, previous = current, previous.next
current.next, current = previous, current.next
return head
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([1, 2, 3, 4, 5])))) == [1, 5, 2, 4, 3], f"{got=}"
assert (got := t(solve(sl([1, 2, 3, 4])))) == [1, 4, 2, 3], f"{got=}"
assert (got := t(solve(sl([1])))) == [1], f"{got=}"
assert (got := t(solve(sl([])))) == [], f"{got=}"
assert (got := t(solve(sl([1, 2])))) == [1, 2], f"{got=}"
assert (got := t(solve(sl([1, 2, 3])))) == [1, 3, 2], f"{got=}"
```
# [Group Anagrams](group_anagrams_064.py)
Write a function `solve` that groups anagrams together.
## Solution
``` Python
def solve(strs):
result = {}
for s in strs:
result.setdefault("".join(sorted(s)), []).append(s)
return list(result.values())
```
## Test Cases
``` Python
assert (got := solve(["eat", "tea", "tan", "ate", "nat", "bat"])) == [
["eat", "tea", "ate"],
["tan", "nat"],
["bat"],
], f"{got=}"
assert (got := solve([""])) == [[""]], f"{got=}"
assert (got := solve(["a"])) == [["a"]], f"{got=}"
assert (got := solve(["ab", "ba", "abc", "cba"])) == [
["ab", "ba"],
["abc", "cba"],
], f"{got=}"
assert (got := solve(["listen", "silent", "enlist"])) == [
["listen", "silent", "enlist"]
], f"{got=}"
assert (got := solve(["rat", "tar", "art"])) == [["rat", "tar", "art"]], f"{got=}"
```
# [Binary Search](binary_search_065.py)
Write a function `solve` that performs a binary search on a sorted list to find
a target and return its index. If the target is not in the list, return -1.
## Solution
``` Python
def solve(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
elif nums[mid] > target:
hi = mid
else:
return mid
return -1
```
## Test Cases
``` Python
assert (got := solve([1, 2, 4, 5, 7, 9], 5)) == 3, f"{got=}"
assert (got := solve([1, 2, 4, 5, 7, 9], 6)) == -1, f"{got=}"
assert (got := solve([1, 2, 4, 5, 7, 9], 1)) == 0, f"{got=}"
assert (got := solve([1, 2, 4, 5, 7, 9], 9)) == 5, f"{got=}"
assert (got := solve([1, 2, 4, 5, 7, 9], 2)) == 1, f"{got=}"
assert (got := solve([1, 2, 4, 5, 7, 9], 4)) == 2, f"{got=}"
```
# [Hamming Distance](hamming_distance_066.py)
Write a function `solve` that computes the Hamming distance between two integers
(number of differing bits).
## Solution
``` Python
def solve(x, y):
return (x ^ y).bit_count()
```
## Test Cases
``` Python
assert (got := solve(1, 4)) == 2, f"{got=}"
assert (got := solve(3, 1)) == 1, f"{got=}"
assert (got := solve(0, 0)) == 0, f"{got=}"
assert (got := solve(7, 8)) == 4, f"{got=}"
assert (got := solve(10, 20)) == 4, f"{got=}"
assert (got := solve(15, 15)) == 0, f"{got=}"
```
# [Multiply Strings](multiply_strings_067.py)
Write a function `solve` that multiplies two non-negative integers
represented as strings.
## Solution
``` Python
def solve(num1, num2):
return str(int(num1) * int(num2))
```
## Test Cases
``` Python
assert (got := solve("123", "456")) == "56088", f"{got=}"
assert (got := solve("2", "3")) == "6", f"{got=}"
assert (got := solve("0", "0")) == "0", f"{got=}"
assert (got := solve("123", "0")) == "0", f"{got=}"
assert (got := solve("2", "2")) == "4", f"{got=}"
assert (got := solve("999", "999")) == "998001", f"{got=}"
```
# [Subset Sum](subset_sum_068.py)
Write a function `solve` to determine if a subset of a list sums to a given target.
## Solution
``` Python
def solve(nums, target):
if target == 0:
return True
if not nums:
return False
return solve(nums[:-1], target) or solve(nums[:-1], target - nums[-1])
```
## Test Cases
``` Python
assert (got := solve([2, 3, 7, 8, 10], 11)) is True, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 9)) is True, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 15)) is True, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 16)) is False, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 0)) is True, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5], 1)) is True, f"{got=}"
```
# [Find All Duplicates in an Array](find_all_duplicates_in_an_array_069.py)
Write a function `solve` that finds all integers that appear exactly twice in
an array where each integer is in the range [1, n] (inclusive) where n is the
size of the array. Return the list of duplicates in ascending order.
## Solution
``` Python
def solve(nums):
return sorted(i for i in set(nums) if nums.count(i) > 1)
```
## Test Cases
``` Python
assert (got := solve([4, 3, 2, 7, 8, 2, 3, 1])) == [2, 3], f"{got=}"
assert (got := solve([1, 1, 2, 3, 3, 4, 5, 5])) == [1, 3, 5], f"{got=}"
assert (got := solve([1])) == [], f"{got=}"
assert (got := solve([1, 1])) == [1], f"{got=}"
assert (got := solve([1, 1, 2, 2])) == [1, 2], f"{got=}"
assert (got := solve([1, 2, 3, 4])) == [], f"{got=}"
```
# [Unique Email Addresses](unique_email_addresses_070.py)
Write a function `solve` that returns the number of unique email addresses
in an array after parsing '+' and '.' rules.
Every valid email consists of a local name and a domain name, separated by the
'@' sign. Besides lowercase letters, the email may contain one or more '.' or
'+'. If there are periods '.' between some characters in the local name part of
an email address, mail sent there will be forwarded to the same address without
dots in the local name. If there is a plus '+' in the local name, everything
after the first plus sign will be ignored. This allows certain emails to be
filtered. Note that these rules do not apply to domain names.
## Solution
``` Python
def solve(emails):
return len(
{
(name.split("+")[0].replace(".", ""), domain)
for name, domain in (email.rsplit("@", 1) for email in emails)
}
)
```
## Test Cases
``` Python
assert (
got := solve(["test.email+alex@leetle.app", "test.e.mail+bob.cathy@leetle.app"])
) == 1, f"{got=}"
assert (got := solve(["a@leetle.app", "b@leetle.app", "c@leetle.app"])) == 3, f"{got=}"
assert (
got := solve(["test.email+alex@leetle.app", "test.email.leet+alex@le.app"])
) == 2, f"{got=}"
assert (
got := solve(["test.email+alex@leetle.app", "test.email@leetle.app"])
) == 1, f"{got=}"
assert (
got := solve(["test.email+alex@leetle.app", "test.email+alex@leetle.app"])
) == 1, f"{got=}"
assert (
got := solve(["test.email+alex@leetle.app", "test.email+alex@le.app"])
) == 2, f"{got=}"
```
# [Binary Tree Preorder Traversal](binary_tree_preorder_traversal_071.py)
Write `solve` for the preorder traversal of a binary tree.
Return the list of values in preorder.
## Solution
``` Python
def solve(root):
if root is None:
return []
return [root.val] + solve(root.left) + solve(root.right)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, None, 2, 3]))) == [1, 2, 3], f"{got=}"
assert (got := solve(bt([]))) == [], f"{got=}"
assert (got := solve(bt([1]))) == [1], f"{got=}"
assert (got := solve(bt([1, 2, 3]))) == [1, 2, 3], f"{got=}"
assert (got := solve(bt([1, None, 2]))) == [1, 2], f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, 5]))) == [1, 2, 4, 5, 3], f"{got=}"
```
# [Best Time to Buy and Sell Stock with Cooldown](bttbasswc_072.py)
Write a function `solve` to maximize profit with a 1-day cooldown period after
selling. You cannot engage in multiple transactions simultaneously (i.e., you
must sell the stock before you buy again). The input is an array of prices where
prices[i] is the price of a given stock on the ith day.
## Solution
``` Python
def solve(prices):
dp = [[0, 0, 0] for _ in range(len(prices) + 1)]
dp[0][0] = -prices[0]
buy, sell, keep = range(3)
for i in range(len(prices)):
dp[i + 1][buy] = max(dp[i][buy], dp[i][keep] - prices[i])
dp[i + 1][sell] = max(dp[i][sell], dp[i][buy] + prices[i])
dp[i + 1][keep] = dp[i][sell]
return dp[-1][sell]
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 0, 2])) == 3, f"{got=}"
assert (got := solve([1])) == 0, f"{got=}"
assert (got := solve([1, 2])) == 1, f"{got=}"
assert (got := solve([2, 1, 4])) == 3, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == 4, f"{got=}"
assert (got := solve([7, 1, 5, 3, 6, 4])) == 5, f"{got=}"
```
# [Permutation in String](permutation_in_string_073.py)
Write a function `solve` to return true if s2 contains any permutation of s1.
A permutation is any rearrangement of the characters.
## Solution
``` Python
from itertools import permutations
def solve(s1, s2):
for s in {"".join(i) for i in permutations(s1)}:
if s in s2:
return True
return False
```
## Test Cases
``` Python
assert (got := solve("ab", "eidbaooo")) is True, f"{got=}"
assert (got := solve("ab", "eidboaoo")) is False, f"{got=}"
assert (got := solve("abc", "ccccbbbbaaaa")) is False, f"{got=}"
assert (got := solve("adc", "dcda")) is True, f"{got=}"
assert (got := solve("hello", "ooolleoooleh")) is False, f"{got=}"
assert (got := solve("a", "ab")) is True, f"{got=}"
```
# [Reverse a String](reverse_a_string_074.py)
Write a function `solve` that reverses a string.
## Solution
``` Python
def solve(s):
return s[::-1]
```
## Test Cases
``` Python
assert (got := solve("hello")) == "olleh", f"{got=}"
assert (got := solve("world")) == "dlrow", f"{got=}"
assert (got := solve("aaaaa")) == "aaaaa", f"{got=}"
assert (got := solve("")) == "", f"{got=}"
assert (got := solve("a")) == "a", f"{got=}"
assert (got := solve("racecar")) == "racecar", f"{got=}"
```
# [Check if a Number is Even](check_if_a_number_is_even_075.py)
Write a function `solve` that checks if a number is even.
## Solution
``` Python
def solve(num):
return not num & 1
```
## Test Cases
``` Python
assert (got := solve(4)) is True, f"{got=}"
assert (got := solve(7)) is False, f"{got=}"
assert (got := solve(0)) is True, f"{got=}"
assert (got := solve(100)) is True, f"{got=}"
assert (got := solve(99)) is False, f"{got=}"
assert (got := solve(-2)) is True, f"{got=}"
```
# [Find the Maximum of Three Numbers](find_the_maximum_of_three_numbers_076.py)
Write a function `solve` that finds the maximum of three numbers.
## Solution
``` Python
def solve(a, b, c):
return max(a, b, c)
```
## Test Cases
``` Python
assert (got := solve(3, 7, 5)) == 7, f"{got=}"
assert (got := solve(10, 3, 15)) == 15, f"{got=}"
assert (got := solve(5, 5, 5)) == 5, f"{got=}"
assert (got := solve(-1, -3, -2)) == -1, f"{got=}"
assert (got := solve(0, 0, 1)) == 1, f"{got=}"
assert (got := solve(100, 50, 25)) == 100, f"{got=}"
```
# [Check if a String is a Palindrome](check_if_a_string_is_a_palindrome_077.py)
Write a function `solve` that checks if a string is a palindrome
(reads the same backward as forward).
## Solution
``` Python
def solve(s):
return s == s[::-1]
```
## Test Cases
``` Python
assert (got := solve("racecar")) is True, f"{got=}"
assert (got := solve("hello")) is False, f"{got=}"
assert (got := solve("level")) is True, f"{got=}"
assert (got := solve("a")) is True, f"{got=}"
assert (got := solve("")) is True, f"{got=}"
assert (got := solve("noon")) is True, f"{got=}"
```
# [Find the Length of a List](find_the_length_of_a_list_078.py)
Write a function `solve` that returns the length of a list.
## Solution
``` Python
def solve(arr):
return len(arr)
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) == 4, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5, 6])) == 6, f"{got=}"
assert (got := solve([0, 0, 0])) == 3, f"{got=}"
assert (got := solve(["a", "b", "c"])) == 3, f"{got=}"
```
# [Sum of All Numbers in a List](sum_of_all_numbers_in_a_list_079.py)
Write a function `solve` that calculates the sum of all numbers in a list.
## Solution
``` Python
def solve(nums):
return sum(nums)
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) == 10, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([5])) == 5, f"{got=}"
assert (got := solve([10, 20, 30])) == 60, f"{got=}"
assert (got := solve([-1, 1])) == 0, f"{got=}"
assert (got := solve([-5, -3, -1])) == -9, f"{got=}"
```
# [Find the First Non-Repeating Character](ftfnrc_080.py)
Write a function `solve` that finds the first non-repeating character in a string.
Return the character, or an empty string if no such character exists.
## Solution
``` Python
def solve(s):
for c in s:
if s.count(c) == 1:
return c
return ""
```
## Test Cases
``` Python
assert (got := solve("aabbcdd")) == "c", f"{got=}"
assert (got := solve("hello")) == "h", f"{got=}"
assert (got := solve("aabb")) == "", f"{got=}"
assert (got := solve("z")) == "z", f"{got=}"
assert (got := solve("")) == "", f"{got=}"
assert (got := solve("leetcode")) == "l", f"{got=}"
```
# [Convert a String to Uppercase](convert_a_string_to_uppercase_081.py)
Write a function `solve` that converts a string to uppercase.
## Solution
``` Python
def solve(s):
return s.upper()
```
## Test Cases
``` Python
assert (got := solve("hello")) == "HELLO", f"{got=}"
assert (got := solve("WORLD")) == "WORLD", f"{got=}"
assert (got := solve("Hello World")) == "HELLO WORLD", f"{got=}"
assert (got := solve("aaaaa")) == "AAAAA", f"{got=}"
assert (got := solve("")) == "", f"{got=}"
assert (got := solve("a")) == "A", f"{got=}"
```
# [Find the Factorial of a Number](find_the_factorial_of_a_number_082.py)
Write a function `solve` that calculates the factorial of a number.
## Solution
``` Python
def solve(n):
from math import factorial
return factorial(n)
```
## Test Cases
``` Python
assert (got := solve(5)) == 120, f"{got=}"
assert (got := solve(0)) == 1, f"{got=}"
assert (got := solve(1)) == 1, f"{got=}"
assert (got := solve(10)) == 3628800, f"{got=}"
assert (got := solve(3)) == 6, f"{got=}"
assert (got := solve(7)) == 5040, f"{got=}"
```
# [Merge Two Lists](merge_two_lists_083.py)
Write a function `solve` that merges two lists into a single list.
## Solution
``` Python
def solve(list1, list2):
return list1 + list2
```
## Test Cases
``` Python
assert (got := solve([1, 2], [3, 4])) == [1, 2, 3, 4], f"{got=}"
assert (got := solve([], [])) == [], f"{got=}"
assert (got := solve([1], [2])) == [1, 2], f"{got=}"
assert (got := solve([1, 2, 3], [])) == [1, 2, 3], f"{got=}"
assert (got := solve([], [4, 5, 6])) == [4, 5, 6], f"{got=}"
assert (got := solve([1, 3, 5], [2, 4, 6])) == [1, 3, 5, 2, 4, 6], f"{got=}"
```
# [Return the Last Element of a List](return_the_last_element_of_a_list_084.py)
Write a function `solve` that returns the last element of a list,
or null if the list is empty.
## Solution
``` Python
def solve(arr):
if arr:
return arr[-1]
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) == 4, f"{got=}"
assert (got := solve([])) is None, f"{got=}"
assert (got := solve([5])) == 5, f"{got=}"
assert (got := solve([10, 20, 30])) == 30, f"{got=}"
assert (got := solve(["a", "b", "c"])) == "c", f"{got=}"
assert (got := solve([True, False])) is False, f"{got=}"
```
# [Remove Duplicates from a List](remove_duplicates_from_a_list_085.py)
Write a function `solve` that removes duplicates from a list
while preserving the original order.
## Solution
``` Python
def solve(arr):
return list(dict.fromkeys(arr).keys())
```
## Test Cases
``` Python
assert (got := solve([1, 2, 2, 3, 4, 4])) == [1, 2, 3, 4], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([5, 5, 5])) == [5], f"{got=}"
assert (got := solve([1, 2, 3])) == [1, 2, 3], f"{got=}"
assert (got := solve([3, 1, 3, 2, 1])) == [3, 1, 2], f"{got=}"
assert (got := solve(["a", "a", "b", "c", "b"])) == ["a", "b", "c"], f"{got=}"
```
# [Find the Intersection of Two Lists](find_the_intersection_of_two_lists_086.py)
Write a function `solve` that finds the intersection of two lists (elements
that appear in both lists), and returns a sorted list of these elements.
## Solution
``` Python
def solve(list1, list2):
return sorted(set(list1) & set(list2))
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3], [2, 3, 4])) == [2, 3], f"{got=}"
assert (got := solve([], [])) == [], f"{got=}"
assert (got := solve([1, 2], [3, 4])) == [], f"{got=}"
assert (got := solve([1, 1, 2, 2], [2, 2])) == [2], f"{got=}"
assert (got := solve([1, 2, 3], [1, 2, 3])) == [1, 2, 3], f"{got=}"
assert (got := solve(["a", "b", "c"], ["b", "c", "d"])) == [
"b",
"c",
], f"{got=}"
```
# [Check if a String Contains a Substring](ciascas_087.py)
Write a function `solve` that checks if a string contains a given substring.
## Solution
``` Python
def solve(s, substring):
return substring in s
```
## Test Cases
``` Python
assert (got := solve("hello", "ell")) is True, f"{got=}"
assert (got := solve("world", "xyz")) is False, f"{got=}"
assert (got := solve("python", "")) is True, f"{got=}"
assert (got := solve("", "a")) is False, f"{got=}"
assert (got := solve("testing", "test")) is True, f"{got=}"
assert (got := solve("banana", "nana")) is True, f"{got=}"
```
# [Generate a List of Squares from 1 to N](galosf1tn_088.py)
Write a function `solve` that generates a list of squares from 1 to N (inclusive).
## Solution
``` Python
def solve(n):
return [i**2 for i in range(1, n + 1)]
```
## Test Cases
``` Python
assert (got := solve(4)) == [1, 4, 9, 16], f"{got=}"
assert (got := solve(1)) == [1], f"{got=}"
assert (got := solve(0)) == [], f"{got=}"
assert (got := solve(5)) == [1, 4, 9, 16, 25], f"{got=}"
assert (got := solve(2)) == [1, 4], f"{got=}"
assert (got := solve(7)) == [1, 4, 9, 16, 25, 36, 49], f"{got=}"
```
# [Sort a List](sort_a_list_089.py)
Write a function `solve` that sorts a list of numbers in ascending order.
## Solution
``` Python
def solve(arr):
return sorted(arr)
```
## Test Cases
``` Python
assert (got := solve([3, 1, 4, 2])) == [1, 2, 3, 4], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([5])) == [5], f"{got=}"
assert (got := solve([5, 5, 5])) == [5, 5, 5], f"{got=}"
assert (got := solve([9, 8, 7, 6, 5])) == [5, 6, 7, 8, 9], f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == [1, 2, 3, 4, 5], f"{got=}"
```
# [Check if All Elements in a List Are Unique](ciaeialau_090.py)
Write a function `solve` that checks if all elements in a list are unique
(no duplicates).
## Solution
``` Python
def solve(arr):
return arr == list(set(arr))
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) is True, f"{got=}"
assert (got := solve([1, 2, 2, 3])) is False, f"{got=}"
assert (got := solve([])) is True, f"{got=}"
assert (got := solve([1])) is True, f"{got=}"
assert (got := solve([1, 1, 1, 1])) is False, f"{got=}"
assert (got := solve(["a", "b", "c", "a"])) is False, f"{got=}"
```
# [Find the Most Frequent Element](find_the_most_frequent_element_091.py)
Write a function `solve` that finds the most frequent element in a list.
## Solution
``` Python
from collections import Counter
def solve(arr):
if arr:
return Counter(arr).most_common(1)[0][0]
```
## Test Cases
``` Python
assert (got := solve([1, 3, 3, 3, 2, 1])) == 3, f"{got=}"
assert (got := solve([1, 1, 2, 2])) == 1, f"{got=}"
assert (got := solve([5])) == 5, f"{got=}"
assert (got := solve([])) is None, f"{got=}"
assert (got := solve(["a", "b", "b", "c"])) == "b", f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == 1, f"{got=}"
```
# [Return the Absolute Value of a Number](rtavoan_092.py)
Write a function `solve` that returns the absolute value of a number.
## Solution
``` Python
def solve(num):
return abs(num)
```
## Test Cases
``` Python
assert (got := solve(-5)) == 5, f"{got=}"
assert (got := solve(5)) == 5, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(-10.5)) == 10.5, f"{got=}"
assert (got := solve(-999)) == 999, f"{got=}"
assert (got := solve(42)) == 42, f"{got=}"
```
# [Repeat a String N Times](repeat_a_string_n_times_093.py)
Write a function `solve` that repeats a string n times.
## Solution
``` Python
def solve(s, n):
return s * n
```
## Test Cases
``` Python
assert (got := solve("hi", 3)) == "hihihi", f"{got=}"
assert (got := solve("abc", 2)) == "abcabc", f"{got=}"
assert (got := solve("x", 5)) == "xxxxx", f"{got=}"
assert (got := solve("", 10)) == "", f"{got=}"
assert (got := solve("hello", 1)) == "hello", f"{got=}"
assert (got := solve("world", 0)) == "", f"{got=}"
```
# [Find the Minimum of a List](find_the_minimum_of_a_list_094.py)
Write a function `solve` that finds the minimum value in a list.
## Solution
``` Python
def solve(arr):
return min(arr)
```
## Test Cases
``` Python
assert (got := solve([3, 1, 4, 2])) == 1, f"{got=}"
assert (got := solve([5])) == 5, f"{got=}"
assert (got := solve([10, 20, -5])) == -5, f"{got=}"
assert (got := solve([0, -1, -2])) == -2, f"{got=}"
assert (got := solve([1, 2, 3])) == 1, f"{got=}"
assert (got := solve([1, 100, 10000])) == 1, f"{got=}"
```
# [Check if a Number is Prime](check_if_a_number_is_prime_095.py)
## Solution
``` Python
def solve(n):
return all(n % i for i in range(2, int(n**0.5) + 1)) if n > 1 else False
```
## Test Cases
``` Python
assert (got := solve(7)) is True, f"{got=}"
assert (got := solve(4)) is False, f"{got=}"
assert (got := solve(1)) is False, f"{got=}"
assert (got := solve(2)) is True, f"{got=}"
assert (got := solve(-3)) is False, f"{got=}"
assert (got := solve(13)) is True, f"{got=}"
```
# [Convert Celsius to Fahrenheit](convert_celsius_to_fahrenheit_096.py)
Write a function `solve` that converts a temperature from Celsius to Fahrenheit.
## Solution
``` Python
def solve(celsius):
return celsius * 9 / 5 + 32
```
## Test Cases
``` Python
assert (got := solve(25)) == 77, f"{got=}"
assert (got := solve(0)) == 32, f"{got=}"
assert (got := solve(-10)) == 14, f"{got=}"
assert (got := solve(100)) == 212, f"{got=}"
assert (got := solve(-40)) == -40, f"{got=}"
assert (got := solve(37)) == 98.6, f"{got=}"
```
# [Count Words in a String](count_words_in_a_string_097.py)
Write a function `solve` that counts the number of words in a string.
Words are separated by spaces.
## Solution
``` Python
def solve(s):
return len(s.split())
```
## Test Cases
``` Python
assert (got := solve("Hello world, how are you?")) == 5, f"{got=}"
assert (got := solve("")) == 0, f"{got=}"
assert (got := solve("One")) == 1, f"{got=}"
assert (got := solve("spaced words")) == 2, f"{got=}"
assert (got := solve("Programming is fun")) == 3, f"{got=}"
assert (got := solve("This is a sentence with seven words in it")) == 9, f"{got=}"
```
# [Check if a Year is a Leap Year](check_if_a_year_is_a_leap_year_098.py)
Write a function `solve` that determines if a given year is a leap year.
## Solution
``` Python
def solve(year):
return year % 4 == 0 and (not year % 100 == 0 or year % 400 == 0)
```
## Test Cases
``` Python
assert (got := solve(2020)) is True, f"{got=}"
assert (got := solve(2100)) is False, f"{got=}"
assert (got := solve(2000)) is True, f"{got=}"
assert (got := solve(1900)) is False, f"{got=}"
assert (got := solve(2024)) is True, f"{got=}"
assert (got := solve(1997)) is False, f"{got=}"
```
# [Generate Fibonacci Sequence](generate_fibonacci_sequence_099.py)
Write a function `solve` that generates the first n numbers of the
Fibonacci sequence. The Fibonacci sequence starts with 0 and 1, and each
subsequent number is the sum of the two preceding numbers.
## Solution
``` Python
def solve(n):
a, b, result = 0, 1, [0, 1]
for _ in range(n - 2):
a, b = b, a + b
result.append(b)
return result[:n]
```
## Test Cases
``` Python
assert (got := solve(6)) == [0, 1, 1, 2, 3, 5], f"{got=}"
assert (got := solve(1)) == [0], f"{got=}"
assert (got := solve(2)) == [0, 1], f"{got=}"
assert (got := solve(10)) == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34], f"{got=}"
assert (got := solve(0)) == [], f"{got=}"
assert (got := solve(7)) == [0, 1, 1, 2, 3, 5, 8], f"{got=}"
```
# [Reverse Words in a String](reverse_words_in_a_string_100.py)
Write a function `solve` that reverses the words in a string without reversing
the characters in each word.
## Solution
``` Python
def solve(s):
return " ".join(reversed(s.split()))
```
## Test Cases
``` Python
assert (got := solve("Hello World")) == "World Hello", f"{got=}"
assert (got := solve("The quick brown fox")) == "fox brown quick The", f"{got=}"
assert (got := solve("a")) == "a", f"{got=}"
assert (got := solve("")) == "", f"{got=}"
assert (got := solve("Good morning everyone")) == "everyone morning Good", f"{got=}"
assert (
got := solve("First Second Third Fourth Fifth")
) == "Fifth Fourth Third Second First", f"{got=}"
```
# [Rotate Linked List](rotate_linked_list_101.py)
Write a function `solve` that rotates a linked list to the right by k places.
## Solution
``` Python
def solve(head, k):
if not head or not head.next or not k:
return head
node, size = head, 1
while node.next is not None:
node, size = node.next, size + 1
node.next, k = head, k % size
while size - k:
node, size = node.next, size - 1
head, node.next = node.next, None
return head
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([1, 2, 3, 4, 5]), 2))) == [4, 5, 1, 2, 3], f"{got=}"
assert (got := t(solve(sl([]), 1))) == [], f"{got=}"
assert (got := t(solve(sl([1]), 3))) == [1], f"{got=}"
assert (got := t(solve(sl([1, 2]), 0))) == [1, 2], f"{got=}"
assert (got := t(solve(sl([1, 2, 3]), 5))) == [2, 3, 1], f"{got=}"
assert (got := t(solve(sl([7, 8, 9]), 1))) == [9, 7, 8], f"{got=}"
```
# [Binary Tree Level Order Traversal](binary_tree_level_order_traversal_102.py)
Write a function `solve` that returns the level order traversal of a binary tree.
## Solution
``` Python
from collections import deque
def solve(root):
if not root:
return []
res, q = [], deque([root])
while q:
level = []
for i in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([3, 9, 20, None, None, 15, 7]))) == [
[3],
[9, 20],
[15, 7],
], f"{got=}"
assert (got := solve(bt([]))) == [], f"{got=}"
assert (got := solve(bt([1]))) == [[1]], f"{got=}"
assert (got := solve(bt([1, 2, None, 3]))) == [[1], [2], [3]], f"{got=}"
assert (got := solve(bt([1, None, 2]))) == [[1], [2]], f"{got=}"
assert (got := solve(bt([5, 4, 6, 3]))) == [[5], [4, 6], [3]], f"{got=}"
```
# [Find Peak Element](find_peak_element_103.py)
Write a function `solve` that finds a peak element in an array
(an element greater than its neighbors) and returns its index.
## Solution
``` Python
def solve(nums):
return nums.index(max(nums))
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 1])) == 2, f"{got=}"
assert (got := solve([1, 1, 1, 3, 5, 6, 4])) == 5, f"{got=}"
assert (got := solve([1])) == 0, f"{got=}"
assert (got := solve([2, 1])) == 0, f"{got=}"
assert (got := solve([1, 2])) == 1, f"{got=}"
assert (got := solve([3, 2, 1])) == 0, f"{got=}"
```
# [Move Zeroes](move_zeroes_104.py)
Write a function `solve` that moves all zeroes to the end of an array while
maintaining relative order of non-zero elements.
## Solution
``` Python
def solve(nums):
return [i for i in nums if i] + [0] * nums.count(0)
```
## Test Cases
``` Python
assert (got := solve([0, 1, 0, 3, 12])) == [1, 3, 12, 0, 0], f"{got=}"
assert (got := solve([0])) == [0], f"{got=}"
assert (got := solve([1, 2, 3])) == [1, 2, 3], f"{got=}"
assert (got := solve([0, 0, 1])) == [1, 0, 0], f"{got=}"
assert (got := solve([1, 0, 0])) == [1, 0, 0], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
```
# [Flatten a 2D Vector](flatten_a_2d_vector_105.py)
Write a function `solve` that flattens a 2D vector into a 1D list.
## Solution
``` Python
def solve(vector):
return [i for r in vector for i in r]
```
## Test Cases
``` Python
assert (got := solve([[1, 2], [3], [4, 5, 6]])) == [
1,
2,
3,
4,
5,
6,
], f"{got=}"
assert (got := solve([[]])) == [], f"{got=}"
assert (got := solve([[1]])) == [1], f"{got=}"
assert (got := solve([[1, 2, 3]])) == [1, 2, 3], f"{got=}"
assert (got := solve([[], [4, 5]])) == [4, 5], f"{got=}"
assert (got := solve([[7], [8, 9]])) == [7, 8, 9], f"{got=}"
```
# [Find the Difference of Two Strings](find_the_difference_of_two_strings_106.py)
Write a function `solve` that finds the character that differs between
two strings where one string has one extra character.
## Solution
``` Python
def solve(s, t):
res = 0
for c in s + t:
res ^= ord(c)
return chr(res)
```
## Test Cases
``` Python
assert (got := solve("abcd", "abcde")) == "e", f"{got=}"
assert (got := solve("", "y")) == "y", f"{got=}"
assert (got := solve("a", "aa")) == "a", f"{got=}"
assert (got := solve("xyz", "xyza")) == "a", f"{got=}"
assert (got := solve("hello", "helloo")) == "o", f"{got=}"
assert (got := solve("cat", "cast")) == "s", f"{got=}"
```
# [Find All Anagrams in a String](find_all_anagrams_in_a_string_107.py)
Write a function `solve` that finds all starting indices of anagrams
of a pattern in a string.
## Solution
``` Python
from collections import Counter
def solve(s, p):
sl, pl = len(s), len(p)
if sl < pl:
return []
sc, pc = Counter(s[:pl]), Counter(p)
res = [0] if sc == pc else []
for i in range(sl - pl):
sc[s[pl + i]] += 1
sc[s[i]] -= 1
if sc == pc:
res.append(i + 1)
if sc[s[i]] == 0:
del sc[s[i]]
return res
```
## Test Cases
``` Python
assert (got := solve("cbaebabacd", "abc")) == [0, 6], f"{got=}"
assert (got := solve("abab", "ab")) == [0, 1, 2], f"{got=}"
assert (got := solve("", "")) == [0], f"{got=}"
assert (got := solve("aaa", "aa")) == [0, 1], f"{got=}"
assert (got := solve("abcd", "xyz")) == [], f"{got=}"
assert (got := solve("a", "a")) == [0], f"{got=}"
```
# [Sum of Left Leaves in a Binary Tree](sum_of_left_leaves_in_a_binary_tree_108.py)
Write a function `solve` that finds the sum of all left leaves in a binary tree.
## Solution
``` Python
def solve(root, left=False):
if not root:
return 0
if left and not root.left and not root.right:
return root.val
return solve(root.left, True) + solve(root.right, False)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([3, 9, 20, None, None, 15, 7]))) == 24, f"{got=}"
assert (got := solve(bt([]))) == 0, f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, 5]))) == 4, f"{got=}"
assert (got := solve(bt([1, None, 2]))) == 0, f"{got=}"
assert (got := solve(bt([1, 2]))) == 2, f"{got=}"
assert (got := solve(bt([5, 4, 6, 3]))) == 3, f"{got=}"
```
# [Reverse Vowels in a String](reverse_vowels_in_a_string_109.py)
Write a function `solve` that reverses only the vowels in a string.
## Solution
``` Python
def solve(s):
vs = [c for c in s if c.lower() in "aeiou"]
return "".join(vs.pop() if c.lower() in "aeiou" else c for c in s)
```
## Test Cases
``` Python
assert (got := solve("hello")) == "holle", f"{got=}"
assert (got := solve("leetcode")) == "leotcede", f"{got=}"
assert (got := solve("a")) == "a", f"{got=}"
assert (got := solve("xyz")) == "xyz", f"{got=}"
assert (got := solve("aeiou")) == "uoiea", f"{got=}"
assert (got := solve("")) == "", f"{got=}"
```
# [Intersection of Two Arrays](intersection_of_two_arrays_110.py)
Write a function `solve` that returns the intersection of two arrays as a sorted list.
## Solution
``` Python
def solve(nums1, nums2):
res = []
for n1 in nums1:
for n2 in nums2:
if n1 == n2 and n1 not in res:
res.append(n1)
return res
```
## Test Cases
``` Python
assert (got := solve([1, 2, 2, 1], [2, 2])) == [2], f"{got=}"
assert (got := solve([4, 9, 5], [9, 4, 9, 8, 4])) == [4, 9], f"{got=}"
assert (got := solve([], [])) == [], f"{got=}"
assert (got := solve([1], [1])) == [1], f"{got=}"
assert (got := solve([1, 2], [3, 4])) == [], f"{got=}"
assert (got := solve([2, 2, 2], [2])) == [2], f"{got=}"
```
# [Contains Duplicate](contains_duplicate_111.py)
Write a function `solve` that determines if an array contains any duplicate elements.
## Solution
``` Python
def solve(nums):
return len(nums) > len(set(nums))
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 1])) is True, f"{got=}"
assert (got := solve([1, 2, 3, 4])) is False, f"{got=}"
assert (got := solve([])) is False, f"{got=}"
assert (got := solve([1, 1, 1, 3, 3])) is True, f"{got=}"
assert (got := solve([1])) is False, f"{got=}"
assert (got := solve([0, 0])) is True, f"{got=}"
```
# [Find Disappeared Numbers in an Array](find_disappeared_numbers_in_an_array_112.py)
Write a function `solve` that finds all numbers in the range [1, n]
that do not appear in an array of length n.
## Solution
``` Python
def solve(nums):
return [i for i in range(1, len(nums) + 1) if i not in set(nums)]
```
## Test Cases
``` Python
assert (got := solve([4, 3, 2, 7, 8, 2, 3, 1])) == [5, 6], f"{got=}"
assert (got := solve([1, 1])) == [2], f"{got=}"
assert (got := solve([1, 2, 3])) == [], f"{got=}"
assert (got := solve([2, 2, 2])) == [1, 3], f"{got=}"
assert (got := solve([1])) == [], f"{got=}"
assert (got := solve([5, 4, 3, 2, 1])) == [], f"{got=}"
```
# [First Unique Character in a String](first_unique_character_in_a_string_113.py)
Write a function `solve` that returns the index of the first
non-repeating character in a string, or -1 if none exists.
## Solution
``` Python
def solve(s):
for i, c in enumerate(s):
if s.count(c) == 1:
return i
return -1
```
## Test Cases
``` Python
assert (got := solve("leetcode")) == 0, f"{got=}"
assert (got := solve("loveleetcode")) == 2, f"{got=}"
assert (got := solve("aabb")) == -1, f"{got=}"
assert (got := solve("")) == -1, f"{got=}"
assert (got := solve("z")) == 0, f"{got=}"
assert (got := solve("aaa")) == -1, f"{got=}"
```
# [Excel Sheet Column Title](excel_sheet_column_title_114.py)
Write a function `solve` that converts a positive integer
to its corresponding Excel column title (1-based).
## Solution
``` Python
def solve(n):
return chr(ord("@") + (n - 1) // 26).strip("@") + chr(ord("A") + (n - 1) % 26)
```
## Test Cases
``` Python
assert (got := solve(1)) == "A", f"{got=}"
assert (got := solve(28)) == "AB", f"{got=}"
assert (got := solve(701)) == "ZY", f"{got=}"
assert (got := solve(26)) == "Z", f"{got=}"
assert (got := solve(52)) == "AZ", f"{got=}"
assert (got := solve(27)) == "AA", f"{got=}"
```
# [Isomorphic Strings](isomorphic_strings_115.py)
Write a function `solve` that determines if two strings are isomorphic
(can be mapped one-to-one).
## Solution
``` Python
def solve(s, t):
if len(s) != len(t):
return False
ms, mt = {}, {}
for cs, ct in zip(s, t):
if (cs in ms and ms[cs] != ct) or (ct in mt and mt[ct] != cs):
return False
ms[cs], mt[ct] = ct, cs
return True
```
## Test Cases
``` Python
assert (got := solve("egg", "add")) is True, f"{got=}"
assert (got := solve("foo", "bar")) is False, f"{got=}"
assert (got := solve("paper", "title")) is True, f"{got=}"
assert (got := solve("", "")) is True, f"{got=}"
assert (got := solve("badc", "baba")) is False, f"{got=}"
assert (got := solve("a", "b")) is True, f"{got=}"
```
# [Find Pivot Index](find_pivot_index_116.py)
Write a function `solve` that finds the pivot index where the sum of elements
to the left equals the sum to the right, or -1 if none exists.
## Solution
``` Python
def solve(nums):
for i, _ in enumerate(nums):
if sum(nums[:i]) == sum(nums[i + 1 :]):
return i
return -1
```
## Test Cases
``` Python
assert (got := solve([1, 7, 3, 6, 5, 6])) == 3, f"{got=}"
assert (got := solve([1, 2, 3])) == -1, f"{got=}"
assert (got := solve([2, 1, -1])) == 0, f"{got=}"
assert (got := solve([])) == -1, f"{got=}"
assert (got := solve([0])) == 0, f"{got=}"
assert (got := solve([-1, -1, -1, 0, 1, 1])) == 0, f"{got=}"
```
# [Ransom Note](ransom_note_117.py)
Write a function `solve` that determines if a ransom note can be constructed
from a magazine string.
## Solution
``` Python
from collections import Counter
def solve(ransomNote, magazine):
return Counter(ransomNote) <= Counter(magazine)
```
## Test Cases
``` Python
assert (got := solve("aa", "aab")) is True, f"{got=}"
assert (got := solve("a", "b")) is False, f"{got=}"
assert (got := solve("aa", "ab")) is False, f"{got=}"
assert (got := solve("", "")) is True, f"{got=}"
assert (got := solve("abc", "abccc")) is True, f"{got=}"
assert (got := solve("xyz", "xy")) is False, f"{got=}"
```
# [Find All Numbers Smaller Than Current](fanstc_118.py)
Write a function `solve` that returns an array where each element is the count
of numbers smaller than the current number.
## Solution
``` Python
def solve(nums):
return [sum(i < num for i in nums) for num in nums]
```
## Test Cases
``` Python
assert (got := solve([8, 1, 2, 2, 3])) == [4, 0, 1, 1, 3], f"{got=}"
assert (got := solve([6, 5, 4, 8])) == [2, 1, 0, 3], f"{got=}"
assert (got := solve([7, 7, 7, 7])) == [0, 0, 0, 0], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([1])) == [0], f"{got=}"
assert (got := solve([5, 2, 6, 1])) == [2, 1, 3, 0], f"{got=}"
```
# [Replace Elements with Greatest on Right](rewgon_119.py)
Write a function `solve` that replaces each element with the greatest element
to its right, and the last element with -1.
## Solution
``` Python
def solve(arr):
return [max(arr[i:]) for i in range(1, len(arr))] + [-1] if len(arr) else []
```
## Test Cases
``` Python
assert (got := solve([17, 18, 5, 4, 6, 1])) == [18, 6, 6, 6, 1, -1], f"{got=}"
assert (got := solve([1, 2, 3])) == [3, 3, -1], f"{got=}"
assert (got := solve([4, 3, 2, 1])) == [3, 2, 1, -1], f"{got=}"
assert (got := solve([])) == [], f"{got=}"
assert (got := solve([1])) == [-1], f"{got=}"
assert (got := solve([5, 5, 5])) == [5, 5, -1], f"{got=}"
```
# [Maximum Product of Three Numbers](maximum_product_of_three_numbers_120.py)
Write a function `solve` that finds the maximum product of three numbers in an array.
## Solution
``` Python
def solve(nums):
nums.sort()
(a, b), (x, y, z) = nums[:2], nums[-3:]
return max(a * b * z, x * y * z)
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) == 24, f"{got=}"
assert (got := solve([-4, -3, -2, 1, 60])) == 720, f"{got=}"
assert (got := solve([1, 2, 3])) == 6, f"{got=}"
assert (got := solve([-100, -2, 0, 1])) == 200, f"{got=}"
assert (got := solve([5, 5, 5])) == 125, f"{got=}"
assert (got := solve([-10, -10, 5, 2])) == 500, f"{got=}"
```
# [Check If Sentence Is Pangram](check_if_sentence_is_pangram_121.py)
Write a function `solve` that checks if a sentence is a pangram
(contains every letter of the alphabet at least once).
## Solution
``` Python
def solve(sentence):
return len({i for i in sentence.lower() if i.isalpha()}) == 26
```
## Test Cases
``` Python
assert (got := solve("thequickbrownfoxjumpsoverthelazydog")) is True, f"{got=}"
assert (got := solve("leetcode")) is False, f"{got=}"
assert (got := solve("")) is False, f"{got=}"
assert (got := solve("abcdefghijklmnopqrstuvwxyz")) is True, f"{got=}"
assert (got := solve("hello world")) is False, f"{got=}"
assert (got := solve("the quick brown fox jumps over a lazy dog")) is True, f"{got=}"
```
# [Happy Number](happy_number_122.py)
Write a function `solve` that determines if a number is a happy number
(eventually reaches 1 when replaced by the sum of the square of each digit).
## Solution
``` Python
def solve(n):
while n > 90:
n = sum(int(i) ** 2 for i in str(n))
return n in {1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86}
```
## Test Cases
``` Python
assert (got := solve(19)) is True, f"{got=}"
assert (got := solve(2)) is False, f"{got=}"
assert (got := solve(7)) is True, f"{got=}"
assert (got := solve(1)) is True, f"{got=}"
assert (got := solve(0)) is False, f"{got=}"
assert (got := solve(-1)) is False, f"{got=}"
assert (got := solve(932)) is True, f"{got=}"
assert (got := solve(91)) is True, f"{got=}"
assert (got := solve(6)) is False, f"{got=}"
assert (got := solve(20)) is False, f"{got=}"
```
# [Sum of Digits Until One Digit](sum_of_digits_until_one_digit_123.py)
Write a function `solve` that repeatedly sums the digits of a number until
a single digit is obtained.
## Solution
``` Python
def solve(num):
return (num - 1) % 9 + 1 if num else 0
```
## Test Cases
``` Python
assert (got := solve(16)) == 7, f"{got=}"
assert (got := solve(942)) == 6, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(123)) == 6, f"{got=}"
assert (got := solve(999)) == 9, f"{got=}"
assert (got := solve(10)) == 1, f"{got=}"
```
# [Integer Break](integer_break_124.py)
Write a function `solve` that breaks an integer n (n >= 2) into
the maximum product of its parts.
## Solution
``` Python
def solve(n):
if n < 4:
return n - 1
return [3 ** (n // 3), 4 * (3 ** (n // 3 - 1)), 2 * (3 ** (n // 3))][n % 3]
```
## Test Cases
``` Python
assert (got := solve(10)) == 36, f"{got=}"
assert (got := solve(2)) == 1, f"{got=}"
assert (got := solve(3)) == 2, f"{got=}"
assert (got := solve(4)) == 4, f"{got=}"
assert (got := solve(5)) == 6, f"{got=}"
assert (got := solve(6)) == 9, f"{got=}"
```
# [Leaf Similar Trees](leaf_similar_trees_125.py)
Write a function `solve` that checks if a binary tree has only one leaf node or none.
## Solution
``` Python
def solve(root):
if not root or not root.left and not root.right:
return True
if root.left and root.right:
return False
if root.left:
return solve(root.left)
return solve(root.right)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, 2, 3]))) is False, f"{got=}"
assert (got := solve(bt([1, 2, None]))) is True, f"{got=}"
assert (got := solve(bt([]))) is True, f"{got=}"
assert (got := solve(bt([1]))) is True, f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, None]))) is False, f"{got=}"
assert (got := solve(bt([1, None, 2]))) is True, f"{got=}"
```
# [Rotate Image](rotate_image_126.py)
Write a function `solve` that rotates a square matrix 90 degrees clockwise in-place.
See [15 Matrix Rotation](#matrixrotation)
## Solution
``` Python
from matrix_rotation_015 import solve # noqa: F401
```
# [Swap Nodes in Pairs](swap_nodes_in_pairs_127.py)
Write a function `solve` that swaps every two adjacent nodes in a linked list
and returns its head.
## Solution
``` Python
def solve(head):
if head and head.next:
head.val, head.next.val = head.next.val, head.val
solve(head.next.next)
return head
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([1, 2, 3, 4])))) == [2, 1, 4, 3], f"{got=}"
assert (got := t(solve(sl([])))) == [], f"{got=}"
assert (got := t(solve(sl([1])))) == [1], f"{got=}"
assert (got := t(solve(sl([1, 2, 3])))) == [2, 1, 3], f"{got=}"
assert (got := t(solve(sl([1, 2])))) == [2, 1], f"{got=}"
assert (got := t(solve(sl([5, 6, 7, 8, 9])))) == [6, 5, 8, 7, 9], f"{got=}"
```
# [Sum of Leaf Values](sum_of_leaf_values_128.py)
Write a function `solve` that returns the sum of all leaf node values in a binary tree.
## Solution
``` Python
def solve(root):
if root is None:
return 0
if not root.left and not root.right:
return root.val
return solve(root.left) + solve(root.right)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, 2, 3]))) == 5, f"{got=}"
assert (got := solve(bt([1, 2, None]))) == 2, f"{got=}"
assert (got := solve(bt([]))) == 0, f"{got=}"
assert (got := solve(bt([1]))) == 1, f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, None]))) == 7, f"{got=}"
assert (got := solve(bt([5, None, 6]))) == 6, f"{got=}"
```
# [Jewels and Stones](jewels_and_stones_129.py)
Write a function `solve` that counts how many stones are jewels,
given strings of jewel types and stones.
## Solution
``` Python
def solve(jewels, stones):
return len([i for i in stones if i in set(jewels)])
```
## Test Cases
``` Python
assert (got := solve("aA", "aAAbbbb")) == 3, f"{got=}"
assert (got := solve("z", "ZZ")) == 0, f"{got=}"
assert (got := solve("", "")) == 0, f"{got=}"
assert (got := solve("abc", "abcABC")) == 3, f"{got=}"
assert (got := solve("XY", "xxyy")) == 0, f"{got=}"
assert (got := solve("a", "aaaaaa")) == 6, f"{got=}"
```
# [Defanging an IP Address](defanging_an_ip_address_130.py)
Write a function `solve` that replaces every period in an IP address with '[.]'.
## Solution
``` Python
def solve(address):
return address.replace(".", "[.]")
```
## Test Cases
``` Python
assert (got := solve("1.1.1.1")) == "1[.]1[.]1[.]1", f"{got=}"
assert (got := solve("255.100.50.0")) == "255[.]100[.]50[.]0", f"{got=}"
assert (got := solve("192.168.1.1")) == "192[.]168[.]1[.]1", f"{got=}"
assert (got := solve("10.0.0.1")) == "10[.]0[.]0[.]1", f"{got=}"
assert (got := solve("172.16.254.1")) == "172[.]16[.]254[.]1", f"{got=}"
assert (got := solve("8.8.8.8")) == "8[.]8[.]8[.]8", f"{got=}"
```
# [Number of 1 Bits](number_of_1_bits_131.py)
Write a function `solve` that returns the number of 1 bits
in the binary representation of an unsigned integer.
## Solution
``` Python
def solve(n):
return n.bit_count()
```
## Test Cases
``` Python
assert (got := solve(11)) == 3, f"{got=}"
assert (got := solve(128)) == 1, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(4294967295)) == 32, f"{got=}"
assert (got := solve(7)) == 3, f"{got=}"
assert (got := solve(1)) == 1, f"{got=}"
```
# [Binary Tree Postorder Traversal](binary_tree_postorder_traversal_132.py)
Write a function `solve` that returns the postorder traversal of a binary tree
(left, right, root).
## Solution
``` Python
def solve(root):
if root is None:
return []
return solve(root.left) + solve(root.right) + [root.val]
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, None, 2, 3]))) == [3, 2, 1], f"{got=}"
assert (got := solve(bt([]))) == [], f"{got=}"
assert (got := solve(bt([1]))) == [1], f"{got=}"
assert (got := solve(bt([1, 2, 3, 4, 5]))) == [4, 5, 2, 3, 1], f"{got=}"
assert (got := solve(bt([3, 1, 2]))) == [1, 2, 3], f"{got=}"
assert (got := solve(bt([5, 4, 6, 3]))) == [3, 4, 6, 5], f"{got=}"
```
# [House Robber](house_robber_133.py)
Write a function `solve` that finds the maximum amount of money that can be robbed
from houses without robbing adjacent ones. The houses will be given as a list where
the value you can steal is given as integers in the list.
## Solution
``` Python
def solve(nums):
if not nums:
return 0
old, new = 0, nums[0]
for i in range(1, len(nums)):
old, new = new, max(nums[i] + old, new)
return new
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 1])) == 4, f"{got=}"
assert (got := solve([2, 7, 9, 3, 1])) == 12, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([2, 1, 1, 2])) == 4, f"{got=}"
assert (got := solve([1, 3, 1])) == 3, f"{got=}"
```
# [In the Ocean](in_the_ocean_134.py)
Write a function `solve` that checks if a given string is a valid oceanic coordinate.
The coordinate is valid if it follows the format of a cardinal direction followed by
a degree value, and it must be within the valid ranges for both latitude and longitude,
which are between 0 and 90 degrees for latitude and 0 and 180 degrees for longitude.
## Solution
``` Python
import re
def solve(coord):
c = re.match(r"[NS](\d+)[EW](\d+)", coord)
if c and 0 <= int(c.groups()[0]) <= 90 and 0 <= int(c.groups()[1]) <= 180:
return True
return False
```
## Test Cases
``` Python
assert (got := solve("N45E90")) is True, f"{got=}"
assert (got := solve("S30W120")) is True, f"{got=}"
assert (got := solve("E90N45")) is False, f"{got=}"
assert (got := solve("N0E0")) is True, f"{got=}"
assert (got := solve("N100E200")) is False, f"{got=}"
assert (got := solve("S45W90")) is True, f"{got=}"
```
# [Reverse Bits](reverse_bits_135.py)
Write a function `solve` that reverses the bits of a 32-bit unsigned integer.
## Solution
``` Python
def solve(n):
return int(f"{n:032b}"[::-1], 2)
```
## Test Cases
``` Python
assert (got := solve(43261596)) == 964176192, f"{got=}"
assert (got := solve(0)) == 0, f"{got=}"
assert (got := solve(4294967295)) == 4294967295, f"{got=}"
assert (got := solve(1)) == 2147483648, f"{got=}"
assert (got := solve(123456)) == 38240256, f"{got=}"
assert (got := solve(2147483648)) == 1, f"{got=}"
```
# [Balling Ones](balling_ones_136.py)
Write a function `solve` that counts the number of 1 bits in the binary
representation of an integer.
See [131 Number of 1 Bits](#numberof1bits)
## Solution
``` Python
from number_of_1_bits_131 import solve # noqa: F401
```
# [Delete Node in a Linked List](delete_node_in_a_linked_list_137.py)
Write a function `solve` that deletes a given node (not the tail) from a
singly linked list. Return the haed of the updated linked list.
## Solution
``` Python
def solve(head, n):
if head and head.val == n and not head.next:
return
node = head
while node:
if node.val == n:
node.val, node.next = node.next.val, node.next.next
return head
node = node.next
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([4, 5, 1, 9]), 5))) == [4, 1, 9], f"{got=}"
assert (got := t(solve(sl([4, 5, 1, 9]), 1))) == [4, 5, 9], f"{got=}"
assert (got := t(solve(sl([1, 2, 3]), 2))) == [1, 3], f"{got=}"
assert (got := t(solve(sl([0, 1]), 0))) == [1], f"{got=}"
assert (got := t(solve(sl([1, 2, 3, 4]), 3))) == [1, 2, 4], f"{got=}"
assert (got := t(solve(sl([7, 8, 9]), 8))) == [7, 9], f"{got=}"
assert (got := t(solve(sl([0]), 0))) == [], f"{got=}"
assert (got := t(solve(sl([0]), 1))) == [], f"{got=}"
```
# [Find the Index of the First Occurrence in a String](ftiotfoias_138.py)
Write a function `solve` that returns the index of the first occurrence
of a substring in a string, or -1 if not found.
## Solution
``` Python
def solve(haystack, needle):
return haystack.find(needle)
```
## Test Cases
``` Python
assert (got := solve("sadbutsad", "sad")) == 0, f"{got=}"
assert (got := solve("leetcode", "leeto")) == -1, f"{got=}"
assert (got := solve("", "")) == 0, f"{got=}"
assert (got := solve("hello", "ll")) == 2, f"{got=}"
assert (got := solve("aaaaa", "bba")) == -1, f"{got=}"
assert (got := solve("abc", "c")) == 2, f"{got=}"
```
# [Sum Root to Leaf Numbers](sum_root_to_leaf_numbers_139.py)
Write a function `solve` that sums all numbers
formed by root-to-leaf paths in a binary tree.
## Solution
``` Python
def solve(root, res=0):
if not root:
return 0
res = res * 10 + root.val
if not root.left and not root.right:
return res
return solve(root.left, res) + solve(root.right, res)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, 2, 3]))) == 25, f"{got=}"
assert (got := solve(bt([4, 9, 0, 5, 1]))) == 1026, f"{got=}"
assert (got := solve(bt([]))) == 0, f"{got=}"
assert (got := solve(bt([1]))) == 1, f"{got=}"
assert (got := solve(bt([1, 2]))) == 12, f"{got=}"
assert (got := solve(bt([5, 1, None, 2]))) == 512, f"{got=}"
```
# [Digits Product](digits_product_140.py)
Write a function `solve` that returns the smallest number whose digits
multiply to a given product, or -1 if impossible.
## Solution
``` Python
def solve(product):
if product == 0:
return 10
if product < 10:
return product
result, pos = 0, 0
for d in range(9, 1, -1):
while product % d == 0:
result, product, pos = d * 10**pos + result, product // d, pos + 1
return -1 if product > 1 else result
```
## Test Cases
``` Python
assert (got := solve(12)) == 26, f"{got=}"
assert (got := solve(0)) == 10, f"{got=}"
assert (got := solve(1)) == 1, f"{got=}"
assert (got := solve(19)) == -1, f"{got=}"
assert (got := solve(13)) == -1, f"{got=}"
assert (got := solve(450)) == 2559, f"{got=}"
```
# [Detect Capital](detect_capital_141.py)
Write a function `solve` that checks if a word uses capitalization correctly
(all uppercase, all lowercase, or only first letter uppercase).
## Solution
``` Python
def solve(word):
return word.isupper() or word.islower() or word == word.capitalize()
```
## Test Cases
``` Python
assert (got := solve("USA")) is True, f"{got=}"
assert (got := solve("leetle")) is True, f"{got=}"
assert (got := solve("Google")) is True, f"{got=}"
assert (got := solve("FlaG")) is False, f"{got=}"
assert (got := solve("I")) is True, f"{got=}"
assert (got := solve("mL")) is False, f"{got=}"
```
# [Odd Even Linked List](odd_even_linked_list_142.py)
Write a function `solve` that groups all odd-indexed nodes followed by
even-indexed nodes in a linked list (1-based indexing).
## Solution
``` Python
def solve(head):
if not head:
return
odd = head
even = even_head = head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
```
## Test Cases
``` Python
# Singly Linked List Definition
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sl(ls):
if not ls:
return None
root = node = ListNode(ls[0])
for i in ls[1:]:
node.next = ListNode(i)
node = node.next
return root
def t(x):
r = []
while x:
r.append(x.val)
x = x.next
return r
assert (got := t(solve(sl([1, 2, 3, 4, 5])))) == [1, 3, 5, 2, 4], f"{got=}"
assert (got := t(solve(sl([2, 1, 3, 5, 6, 4, 7])))) == [
2,
3,
6,
7,
1,
5,
4,
], f"{got=}"
assert (got := t(solve(sl([])))) == [], f"{got=}"
assert (got := t(solve(sl([1])))) == [1], f"{got=}"
assert (got := t(solve(sl([1, 2])))) == [1, 2], f"{got=}"
assert (got := t(solve(sl([1, 2, 3])))) == [1, 3, 2], f"{got=}"
```
# [Baseball Game](baseball_game_143.py)
Write a function `solve` that calculates the total score of a baseball game given
operations (integer, +, D, C). An integer n means you record the score. + means
record the sum of the last two scores, D means record the double of the last score,
and C means cancel the last score. Finally, you should sum the scores.
## Solution
``` Python
def solve(operations):
scores = []
for op in operations:
match op:
case "+":
scores.append(scores[-1] + scores[-2])
case "C":
scores.pop()
case "D":
scores.append(scores[-1] * 2)
case _:
scores.append(int(op))
return sum(scores)
```
## Test Cases
``` Python
assert (got := solve(["5", "2", "C", "D", "+"])) == 30, f"{got=}"
assert (got := solve(["5", "-2", "4", "C", "D", "9", "+", "+"])) == 27, f"{got=}"
assert (got := solve(["1"])) == 1, f"{got=}"
assert (got := solve(["1", "C"])) == 0, f"{got=}"
assert (got := solve(["5", "D"])) == 15, f"{got=}"
assert (got := solve(["2", "3", "+"])) == 10, f"{got=}"
```
# [Shuffle Array](shuffle_array_144.py)
Write a function `solve` that shuffles an array by interleaving its first
n elements with its last n elements.
## Solution
``` Python
def solve(nums, n):
return [i for t in zip(nums[:n], nums[n:]) for i in t]
```
## Test Cases
``` Python
assert (got := solve([2, 5, 1, 3, 4, 7], 3)) == [2, 3, 5, 4, 1, 7], f"{got=}"
assert (got := solve([1, 2, 3, 4], 2)) == [1, 3, 2, 4], f"{got=}"
assert (got := solve([1, 1, 2, 2], 2)) == [1, 2, 1, 2], f"{got=}"
assert (got := solve([1, 2], 1)) == [1, 2], f"{got=}"
assert (got := solve([5, 6, 7, 8, 9, 10], 3)) == [5, 8, 6, 9, 7, 10], f"{got=}"
assert (got := solve([1, 3, 5, 7], 2)) == [1, 5, 3, 7], f"{got=}"
```
# [Valid Perfect Square](valid_perfect_square_145.py)
Write a function `solve` that determines if a given number is a perfect square
without using any built-in square root functions.
## Solution
``` Python
def solve(num):
if num <= 1:
return False if num < 0 else True
low, high = 1, num // 2
while low <= high:
middle = (high - low) // 2 + low
if (square := middle * middle) == num:
return True
low, high = (middle + 1, high) if square < num else (low, middle - 1)
return False
```
## Test Cases
``` Python
assert (got := solve(16)) is True, f"{got=}"
assert (got := solve(14)) is False, f"{got=}"
assert (got := solve(1)) is True, f"{got=}"
assert (got := solve(0)) is True, f"{got=}"
assert (got := solve(2147483647)) is False, f"{got=}"
assert (got := solve(808201)) is True, f"{got=}"
assert (got := solve(-808201)) is False, f"{got=}"
```
# [Longest Increasing Subsequence](longest_increasing_subsequence_146.py)
Write a function `solve` that finds the length of the longest strictly increasing
subsequence in an array of integers.
## Solution
``` Python
def solve(nums):
n, ans = len(nums), []
for i in range(n):
if not ans or nums[i] > ans[-1]:
ans.append(nums[i])
else:
low, high = 0, len(ans) - 1
while low < high:
mid = low + (high - low) // 2
low, high = (mid + 1, high) if ans[mid] < nums[i] else (low, mid)
ans[low] = nums[i]
return len(ans)
```
## Test Cases
``` Python
assert (got := solve([10, 9, 2, 5, 3, 7, 101, 18])) == 4, f"{got=}"
assert (got := solve([0, 1, 0, 3, 2, 3])) == 4, f"{got=}"
assert (got := solve([7, 7, 7, 7, 7, 7, 7])) == 1, f"{got=}"
assert (got := solve([])) == 0, f"{got=}"
assert (got := solve([1])) == 1, f"{got=}"
assert (got := solve([4, 10, 4, 3, 8, 9])) == 3, f"{got=}"
```
# [Subarray Sum Equals K](subarray_sum_equals_k_147.py)
Write a function `solve` that finds the total number of subarrays whose sum equals k.
## Solution
``` Python
def solve(nums, k):
prefix_sums, running, total = {0: 1}, 0, 0
for num in nums:
running += num
if running - k in prefix_sums:
total += prefix_sums[running - k]
prefix_sums[running] = prefix_sums.get(running, 0) + 1
return total
```
## Test Cases
``` Python
assert (got := solve([1, 1, 1], 2)) == 2, f"{got=}"
assert (got := solve([1, 2, 3], 3)) == 2, f"{got=}"
assert (got := solve([1], 0)) == 0, f"{got=}"
assert (got := solve([1, -1, 0], 0)) == 3, f"{got=}"
assert (got := solve([3, 4, 7, 2, -3, 1, 4, 2], 7)) == 4, f"{got=}"
assert (got := solve([], 5)) == 0, f"{got=}"
```
# [Number of Islands](number_of_islands_148.py)
Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water),
return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally
or vertically. You may assume all four edges of the grid are all surrounded by water.
## Solution
``` Python
def solve(grid):
def dfs(r, c):
if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1":
grid[r][c] = "0"
for dr, dc in directions:
dfs(r + dr, c + dc)
result, directions = 0, [(0, 1), (0, -1), (1, 0), (-1, 0)]
rows, cols = len(grid), len(grid[0])
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
result += 1
dfs(r, c)
return result
```
## Test Cases
``` Python
assert (
got := solve(
[
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"],
]
)
) == 1, f"{got=}"
assert (
got := solve(
[
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"],
]
)
) == 3, f"{got=}"
assert (got := solve([[]])) == 0, f"{got=}"
assert (got := solve([["1"]])) == 1, f"{got=}"
assert (got := solve([["0"]])) == 0, f"{got=}"
assert (
got := solve(
[
["0", "0", "1", "0", "1", "1"],
["1", "1", "0", "0", "0", "1"],
["0", "1", "0", "1", "1", "0"],
["0", "1", "1", "0", "0", "0"],
["1", "0", "1", "0", "1", "1"],
["1", "0", "1", "0", "1", "0"],
]
)
) == 6, f"{got=}"
```
# [Word Ladder](word_ladder_149.py)
Write a function `solve` that takes two words, begin_word and end_word, and a list
of words word_list. The function should return the length of the shortest
transformation sequence from begin_word to end_word where each transformation
changes exactly one letter. If no such transformation sequence exists, return 0.
## Solution
``` Python
from collections import defaultdict, deque
def solve(begin_word, end_word, word_list):
length, patterns = 1, defaultdict(list)
seen, queue = set([begin_word]), deque([begin_word])
for word in [begin_word] + word_list:
for i in range(len(word)):
patterns[word[:i] + "." + word[i + 1 :]].append(word)
while queue:
for _ in range(len(queue)):
word = queue.popleft()
if word == end_word:
return length
for i in range(len(word)):
for pattern in patterns[word[:i] + "." + word[i + 1 :]]:
if pattern not in seen:
seen.add(pattern)
queue.append(pattern)
length = length + 1
return 0
```
## Test Cases
``` Python
assert (
got := solve("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
) == 5, f"{got=}"
assert (got := solve("hit", "cog", ["hot", "dot", "dog", "lot", "log"])) == 0, f"{got=}"
assert (got := solve("a", "c", ["a", "b", "c"])) == 2, f"{got=}"
assert (got := solve("hot", "dog", ["hot", "dog"])) == 0, f"{got=}"
assert (got := solve("hit", "hit", ["hit"])) == 1, f"{got=}"
assert (
got := solve("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"])
) == 4, f"{got=}"
```
# [Course Schedule](course_schedule_150.py)
Write a function `solve` that takes the number of courses num_courses and an
array of prerequisites prerequisites where prerequisites[i] = [a, b] indicates
that you must take course b before taking course a.
Return true if you can finish all courses, otherwise return false.
## Solution
``` Python
from collections import defaultdict, deque
def solve(num_courses, prerequisites):
graph, pre = defaultdict(list), [0] * num_courses
for c, p in prerequisites:
graph[p].append(c)
pre[c] += 1
todo, done = deque(i for i in pre if i == 0), 0
while todo:
done += 1
for i in graph[todo.popleft()]:
pre[i] -= 1
if pre[i] == 0:
todo.append(i)
return done == num_courses
```
## Test Cases
``` Python
assert (got := solve(2, [[1, 0]])) is True, f"{got=}"
assert (got := solve(2, [[1, 0], [0, 1]])) is False, f"{got=}"
assert (got := solve(3, [[1, 0], [2, 1]])) is True, f"{got=}"
assert (got := solve(4, [[1, 0], [2, 0], [3, 1], [3, 2]])) is True, f"{got=}"
assert (got := solve(3, [[0, 1], [0, 2], [1, 2], [2, 0]])) is False, f"{got=}"
assert (got := solve(1, [])) is True, f"{got=}"
```
# [Find All Permutations of a String](find_all_permutations_of_a_string_151.py)
Write a function `solve` that returns all possible permutations of a string
with unique characters. The permutations can be returned in any order.
## Solution
``` Python
from itertools import permutations
def solve(s):
return ["".join(i) for i in permutations(s)]
```
## Test Cases
``` Python
assert (got := solve("abc")) == [
"abc",
"acb",
"bac",
"bca",
"cab",
"cba",
], f"{got=}"
assert (got := solve("a")) == ["a"], f"{got=}"
assert (got := solve("ab")) == ["ab", "ba"], f"{got=}"
assert (got := solve("")) == [""], f"{got=}"
assert (got := solve("xyz")) == [
"xyz",
"xzy",
"yxz",
"yzx",
"zxy",
"zyx",
], f"{got=}"
assert (got := solve("123")) == [
"123",
"132",
"213",
"231",
"312",
"321",
], f"{got=}"
```
# [Longest Palindromic Subsequence](longest_palindromic_subsequence_152.py)
Write a function `solve` that finds the length of the longest palindromic
subsequence in a string. A subsequence is a sequence that can be derived from
another sequence by deleting some or no elements without changing the order of
the remaining elements.
## Solution
``` Python
def solve(s):
cur, pre = [0] * (n := len(s)), [0] * n
for i in range(n - 1, -1, -1):
cur[i] = 1
for j in range(i + 1, n):
cur[j] = pre[j - 1] + 2 if s[i] == s[j] else max(pre[j], cur[j - 1])
pre = cur[:]
return cur[n - 1] if n else 0
```
## Test Cases
``` Python
assert (got := solve("bbbab")) == 4, f"{got=}"
assert (got := solve("cbbd")) == 2, f"{got=}"
assert (got := solve("a")) == 1, f"{got=}"
assert (got := solve("abcdefgfedcba")) == 13, f"{got=}"
assert (got := solve("")) == 0, f"{got=}"
assert (got := solve("aabaa")) == 5, f"{got=}"
```
# [Find the Celebrity](find_the_celebrity_153.py)
Write a function `solve` that finds the celebrity in a party of n people labeled
from 0 to n-1. A celebrity is someone who is known by everyone but doesn't know
anyone. You are given a helper function `knows(a, b)` which returns true if person
a knows person b, and false otherwise. Your function should return the celebrity's
label if there is exactly one celebrity, or -1 if there is no celebrity.
## Solution
``` Python
def solve(n, knows_data):
# knows_data is a list of [a, b, result] where result is True if a knows b
# This is a simulation of the knows() API - in a real interview, you'd have
# a knows(a, b) function
knows_dict = {(a, b): result for a, b, result in knows_data}
def knows(a, b):
return knows_dict.get((a, b), False)
# Your solution here
return {
0: i
for i in range(n)
if sum(knows(j, i) for j in range(n)) == n - 1
and sum(knows(i, j) for j in range(n)) == 0
}.get(0, -1)
```
## Test Cases
``` Python
assert (
got := solve(
3,
[
[0, 1, True],
[0, 2, True],
[1, 0, False],
[1, 2, True],
[2, 0, False],
[2, 1, False],
],
)
) == 2, f"{got=}"
assert (got := solve(2, [[0, 1, True], [1, 0, True]])) == -1, f"{got=}"
assert (
got := solve(
3,
[
[0, 1, True],
[1, 0, True],
[1, 2, True],
[2, 1, True],
[0, 2, False],
[2, 0, False],
],
)
) == -1, f"{got=}"
assert (
got := solve(
4,
[
[0, 1, True],
[0, 2, True],
[0, 3, True],
[1, 0, False],
[1, 2, True],
[1, 3, True],
[2, 0, False],
[2, 1, False],
[2, 3, False],
[3, 0, False],
[3, 1, False],
[3, 2, True],
],
)
) == 2, f"{got=}"
assert (got := solve(1, [])) == 0, f"{got=}"
assert (
got := solve(
4,
[
[0, 1, True],
[0, 2, True],
[0, 3, True],
[1, 0, False],
[1, 2, True],
[1, 3, True],
[2, 0, False],
[2, 1, False],
[2, 3, True],
[3, 0, False],
[3, 1, False],
[3, 2, False],
],
)
) == 3, f"{got=}"
```
# [Product of Array Except Self](product_of_array_except_self_154.py)
Write a function `solve` that takes an array nums of n integers and returns an
array output such that output[i] is equal to the product of all the elements of
nums except nums[i]. Solve it without using division.
## Solution
``` Python
def solve(nums):
pre, suf = [1] * (n := len(nums)), [1] * n
for i in range(1, n):
pre[i] = nums[i - 1] * pre[i - 1]
for i in range(n - 2, -1, -1):
suf[i] = nums[i + 1] * suf[i + 1]
return [pre[i] * suf[i] for i in range(n)]
```
## Test Cases
``` Python
assert (got := solve([1, 2, 3, 4])) == [24, 12, 8, 6], f"{got=}"
assert (got := solve([0, 0])) == [0, 0], f"{got=}"
assert (got := solve([1, 0])) == [0, 1], f"{got=}"
assert (got := solve([1, 2])) == [2, 1], f"{got=}"
assert (got := solve([5, 9, 2, 10, 1, 3])) == [
540,
300,
1350,
270,
2700,
900,
], f"{got=}"
assert (got := solve([0, 1, 2, 0])) == [0, 0, 0, 0], f"{got=}"
```
# [Decode Ways](decode_ways_155.py)
Write a function `solve` that determines the number of ways to decode a string of
digits. A message containing letters from A-Z can be encoded into numbers by
mapping A to 1, B to 2, ..., Z to 26. For example, the message 'ABC' would be
encoded as '123'. Given a string of digits, return the number of ways to decode it.
## Solution
``` Python
def solve(s):
prev, curr = 0, 1
for i in range(len(s)):
next = 0
if s[i] != "0":
next = curr
if i > 0 and s[i - 1] in "12" and s[i] < "7":
next += prev
prev, curr = curr, next
return curr
```
## Test Cases
``` Python
assert (got := solve("12")) == 2, f"{got=}"
assert (got := solve("226")) == 3, f"{got=}"
assert (got := solve("0")) == 0, f"{got=}"
assert (got := solve("06")) == 0, f"{got=}"
assert (got := solve("10")) == 1, f"{got=}"
assert (got := solve("2101")) == 1, f"{got=}"
```
# [Find the Second Largest Number](find_the_second_largest_number_156.py)
Write a function `solve` that returns the second largest number in a list of
integers. If the list has fewer than two unique numbers, return `None`.
## Solution
``` Python
def solve(nums):
return dict(enumerate(sorted(set(nums))[:-3:-1])).get(1)
```
## Test Cases
``` Python
assert (got := solve([3, 1, 4, 1, 5, 9])) == 5, f"{got=}"
assert (got := solve([1, 1, 1])) is None, f"{got=}"
assert (got := solve([2, 2, 3])) == 2, f"{got=}"
assert (got := solve([10])) is None, f"{got=}"
assert (got := solve([7, 7, 8, 8, 9])) == 8, f"{got=}"
assert (got := solve([5, 4])) == 4, f"{got=}"
```
# [Check Number Sign](check_number_sign_157.py)
Write a function `solve` that takes an integer `n` and returns the string "positive"
if n is greater than 0, "negative" if n is less than 0, and "zero" if n is equal to 0.
## Solution
``` Python
def solve(n):
return "negative" if n < 0 else ("positive" if n > 0 else "zero")
```
## Test Cases
``` Python
assert (got := solve(5)) == "positive", f"{got=}"
assert (got := solve(-3)) == "negative", f"{got=}"
assert (got := solve(0)) == "zero", f"{got=}"
assert (got := solve(100)) == "positive", f"{got=}"
assert (got := solve(-1000)) == "negative", f"{got=}"
assert (got := solve(1)) == "positive", f"{got=}"
```
# [Find the Missing Letter](find_the_missing_letter_158.py)
Write a function `solve` that takes a list of consecutive letters (increasing
order, one missing) and returns the missing letter. The input will always be a
list of single-character strings with exactly one letter missing.
## Solution
``` Python
def solve(ls):
return ({chr(ord(ls[0]) + i) for i in range(len(ls))} - set(ls)).pop()
```
## Test Cases
``` Python
assert (got := solve(["a", "b", "c", "e"])) == "d", f"{got=}"
assert (got := solve(["O", "P", "Q", "S"])) == "R", f"{got=}"
assert (got := solve(["s", "t", "v"])) == "u", f"{got=}"
assert (got := solve(["m", "n", "p"])) == "o", f"{got=}"
assert (got := solve(["A", "B", "D"])) == "C", f"{got=}"
assert (got := solve(["g", "h", "j"])) == "i", f"{got=}"
```
# [Sum of Digits Until One Digit](sum_of_digits_until_one_digit_159.py)
Write a function `solve` that repeatedly adds all the digits of a non-negative
integer until the result has only one digit, and returns that digit.
See [123 Sum of Digits Until One Digit](#sumofdigitsuntilonedigit)
## Solution
``` Python
from sum_of_digits_until_one_digit_123 import solve # noqa: F401
```
# [Find the Intersection Point](find_the_intersection_point_160.py)
Write a function `solve` that takes two lists and returns a list of elements
that appear in both lists, in the order they appear in the first list. Each
element should appear only once in the result.
## Solution
``` Python
def solve(list1, list2):
return list({i: None for i in list1 if i in set(list2)})
```
## Test Cases
``` Python
assert (got := solve([1, 2, 2, 3], [2, 3, 4])) == [2, 3], f"{got=}"
assert (got := solve([5, 6, 7], [7, 8, 9])) == [7], f"{got=}"
assert (got := solve([1, 2, 3], [4, 5, 6])) == [], f"{got=}"
assert (got := solve([1, 1, 1], [1])) == [1], f"{got=}"
assert (got := solve([1, 2, 3, 4], [2, 4, 6, 8])) == [2, 4], f"{got=}"
assert (got := solve([10, 20, 30], [30, 10, 20])) == [10, 20, 30], f"{got=}"
```
# [Valid Mountain Array](valid_mountain_array_161.py)
Write a function `solve` that determines if an array is a valid mountain array.
A valid mountain array has the following properties:
- Length of at least 3 elements
- Elements first strictly increase, then strictly decrease
- There must be at least one element in both increasing and decreasing parts
## Solution
``` Python
def solve(arr):
if (n := len(arr)) < 3:
return False
left, right = 0, n - 1
while left + 1 < n - 1 and arr[left] < arr[left + 1]:
left += 1
while right - 1 > 0 and arr[right] < arr[right - 1]:
right -= 1
return left == right
```
## Test Cases
``` Python
assert (got := solve([0, 3, 2, 1])) is True, f"{got=}"
assert (got := solve([3, 5, 5])) is False, f"{got=}"
assert (got := solve([0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0])) is True, f"{got=}"
assert (got := solve([1, 2, 3])) is False, f"{got=}"
assert (got := solve([3, 2, 1])) is False, f"{got=}"
assert (got := solve([1, 2])) is False, f"{got=}"
```
# [Find Target in Rotated Sorted Array](find_target_in_rotated_sorted_array_162.py)
Write a function `solve` that searches for a target value in a rotated sorted array.
The array was originally sorted in ascending order, then rotated at some pivot.
Return the index if found, otherwise return -1.
## Solution
``` Python
def solve(nums, target):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[0] <= nums[mid]:
if nums[0] <= target <= nums[mid]:
right = mid
else:
left = mid + 1
else:
if nums[mid] < target <= nums[-1]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
```
## Test Cases
``` Python
assert (got := solve([4, 5, 6, 7, 0, 1, 2], 0)) == 4, f"{got=}"
assert (got := solve([4, 5, 6, 7, 0, 1, 2], 3)) == -1, f"{got=}"
assert (got := solve([1], 0)) == -1, f"{got=}"
assert (got := solve([1], 1)) == 0, f"{got=}"
assert (got := solve([1, 3, 5], 3)) == 1, f"{got=}"
assert (got := solve([3, 1], 1)) == 1, f"{got=}"
```
# [Longest Substring with At Most K Distinct Characters](lswamkdc_163.py)
Write a function `solve` that finds the length of the longest substring
that contains at most k distinct characters.
## Solution
``` Python
def solve(s, k):
cs, r, x = {}, 0, 0
for i, c in enumerate(s):
cs[c] = cs.get(c, 0) + 1
while len(cs) > k:
cs[s[x]] = cs.get(s[x], 0) - 1
if cs[s[x]] == 0:
del cs[s[x]]
x += 1
r = max(r, i - x + 1)
return r
```
## Test Cases
``` Python
assert (got := solve("eceba", 2)) == 3, f"{got=}"
assert (got := solve("aa", 1)) == 2, f"{got=}"
assert (got := solve("abcdef", 3)) == 3, f"{got=}"
assert (got := solve("a", 2)) == 1, f"{got=}"
assert (got := solve("", 1)) == 0, f"{got=}"
assert (got := solve("abcabc", 2)) == 2, f"{got=}"
```
# [Design Phone Directory](design_phone_directory_164.py)
Write a function `solve` that simulates a phone directory with operations: get
next available number, check if number is available, and release a number.
Given a list of operations, return the results.
Operations: ["get", "check", "release"]
## Solution
``` Python
def solve(n, operations):
results, numbers = [], list(range(n - 1, -1, -1))
for op in operations:
match op:
case ["get"]:
results.append(numbers.pop() if numbers else -1)
case ["check", x]:
results.append(x in numbers)
case ["release", x]:
results.append(numbers.append(x) if x not in numbers else None)
return results
```
## Test Cases
``` Python
assert (
got := solve(
3,
[
["get"],
["get"],
["check", 2],
["get"],
["check", 2],
["release", 2],
["check", 2],
],
)
) == [0, 1, True, 2, False, None, True], f"{got=}"
assert (got := solve(1, [["get"], ["get"], ["release", 0], ["get"]])) == [
0,
-1,
None,
0,
], f"{got=}"
assert (got := solve(2, [["check", 0], ["get"], ["check", 0], ["release", 0]])) == [
True,
0,
False,
None,
], f"{got=}"
assert (got := solve(1, [["check", 0], ["check", 1]])) == [
True,
False,
], f"{got=}"
assert (got := solve(5, [["get"], ["get"], ["get"], ["get"], ["get"], ["get"]])) == [
0,
1,
2,
3,
4,
-1,
], f"{got=}"
assert (got := solve(2, [["release", 0], ["get"], ["get"], ["get"]])) == [
None,
0,
1,
-1,
], f"{got=}"
```
# [Meeting Rooms](meeting_rooms_165.py)
Write a function `solve` that determines if a person can attend all meetings
given their time intervals. Each interval is [start_time, end_time].
## Solution
``` Python
def solve(intervals):
intervals.sort()
for i in range(len(intervals) - 1):
if intervals[i][1] > intervals[i + 1][0]:
return False
return True
```
## Test Cases
``` Python
assert (got := solve([[0, 30], [5, 10], [15, 20]])) is False, f"{got=}"
assert (got := solve([[7, 10], [2, 4]])) is True, f"{got=}"
assert (got := solve([])) is True, f"{got=}"
assert (got := solve([[1, 5]])) is True, f"{got=}"
assert (got := solve([[1, 4], [4, 5]])) is True, f"{got=}"
assert (got := solve([[1, 4], [2, 3]])) is False, f"{got=}"
```
# [Shortest Word Distance](shortest_word_distance_166.py)
Write a function `solve` that finds the shortest distance between two words in a
list of words. Distance is the absolute difference between their indices.
## Solution
``` Python
def solve(word1, word2, words):
index1 = index2 = -1
shortest_distance = float("inf")
for index, word in enumerate(words):
if word == word1:
index1 = index
if word == word2:
index2 = index
if index1 != -1 and index2 != -1:
distance = abs(index1 - index2)
shortest_distance = min(shortest_distance, distance)
return shortest_distance
```
## Test Cases
``` Python
assert (
got := solve(
"coding",
"practice",
["practice", "makes", "perfect", "coding", "makes"],
)
) == 3, f"{got=}"
assert (
got := solve("makes", "coding", ["practice", "makes", "perfect", "coding", "makes"])
) == 1, f"{got=}"
assert (got := solve("a", "c", ["a", "b", "c"])) == 2, f"{got=}"
assert (got := solve("a", "b", ["a", "c", "b", "a"])) == 1, f"{got=}"
assert (
got := solve("practice", "perfect", ["practice", "makes", "perfect"])
) == 2, f"{got=}"
assert (got := solve("hello", "world", ["hello", "world", "hello"])) == 1, f"{got=}"
```
# [Palindromic Substrings](palindromic_substrings_167.py)
Write a function `solve` that counts the number of palindromic substrings in a
string. A substring is palindromic if it reads the same backward as forward.
## Solution
``` Python
def solve(s):
n, r = len(s), 0
for i in range(n):
b, a = i, i + 1
while b >= 0 and a < n and s[b] == s[a]:
r, b, a = r + 1, b - 1, a + 1
for i in range(n):
b, a = i - 1, i + 1
while b >= 0 and a < n and s[b] == s[a]:
r, b, a = r + 1, b - 1, a + 1
return n + r
```
## Test Cases
``` Python
assert (got := solve("abc")) == 3, f"{got=}"
assert (got := solve("aaa")) == 6, f"{got=}"
assert (got := solve("racecar")) == 10, f"{got=}"
assert (got := solve("a")) == 1, f"{got=}"
assert (got := solve("")) == 0, f"{got=}"
assert (got := solve("abccba")) == 9, f"{got=}"
```
# [Largest Rectangle in Histogram](largest_rectangle_in_histogram_168.py)
Write a function `solve` that finds the area of the largest rectangle that can
be formed in a histogram represented by an array of heights.
## Solution
``` Python
def solve(heights):
n, s, r = len(heights), [], 0
for i in range(n):
while s and heights[s[-1]] >= heights[i]:
r = max(r, heights[s.pop()] * (i if not s else i - s[-1] - 1))
s.append(i)
while s:
r = max(r, heights[s.pop()] * (n if not s else n - s[-1] - 1))
return r
```
## Test Cases
``` Python
assert (got := solve([2, 1, 5, 6, 2, 3])) == 10, f"{got=}"
assert (got := solve([2, 4])) == 4, f"{got=}"
assert (got := solve([1, 1, 1, 1])) == 4, f"{got=}"
assert (got := solve([5, 4, 3, 2, 1])) == 9, f"{got=}"
assert (got := solve([1, 2, 3, 4, 5])) == 9, f"{got=}"
assert (got := solve([6, 2, 5, 4, 5, 1, 6])) == 12, f"{got=}"
```
# [Word Pattern](word_pattern_169.py)
Write a function `solve` that determines if a string follows a given pattern.
Each letter in the pattern corresponds to exactly one unique word in the string.
## Solution
``` Python
def solve(pattern, s):
return (
len(set(pattern)) == len(set(ss := s.split()))
and " ".join(dict(zip(pattern, ss))[i] for i in pattern) == s
)
```
## Test Cases
``` Python
assert (got := solve("abba", "dog cat cat dog")) is True, f"{got=}"
assert (got := solve("abba", "dog cat cat fish")) is False, f"{got=}"
assert (got := solve("aaaa", "dog cat cat dog")) is False, f"{got=}"
assert (got := solve("abba", "dog dog dog dog")) is False, f"{got=}"
assert (got := solve("abc", "dog cat fish")) is True, f"{got=}"
assert (got := solve("a", "hello")) is True, f"{got=}"
```
# [Binary Tree Maximum Path Sum](binary_tree_maximum_path_sum_170.py)
Write a function `solve` that finds the maximum sum of any path in a binary tree.
A path is defined as any sequence of nodes from some starting node to any node
in the tree along the parent-child connections.
## Solution
``` Python
def solve(root):
def traverse(node):
nonlocal res
if node is None:
return 0
left, right = max(0, traverse(node.left)), max(0, traverse(node.right))
res = max(res, left + right + node.val)
return node.val + max(left, right)
res = root.val
traverse(root)
return res
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, 2, 3]))) == 6, f"{got=}"
assert (got := solve(bt([-10, 9, 20, None, None, 15, 7]))) == 42, f"{got=}"
assert (got := solve(bt([5]))) == 5, f"{got=}"
assert (got := solve(bt([-3]))) == -3, f"{got=}"
assert (got := solve(bt([1, -2, -3, 1, 3, -2, None, -1]))) == 3, f"{got=}"
assert (got := solve(bt([2, -1, -2]))) == 2, f"{got=}"
```
# [Count Character Types](count_character_types_171.py)
Write a function `solve` that counts different types of characters in a string.
Return a dictionary/object with counts for: vowels, consonants, digits, and spaces.
Note: Vowels are a, e, i, o, u (case insensitive).
## Solution
``` Python
def solve(s):
d = dict(vowels=0, consonants=0, digits=0, spaces=0)
for c in s:
if c.lower() in "aeiou":
d["vowels"] += 1
elif c.isalpha():
d["consonants"] += 1
elif c.isdecimal():
d["digits"] += 1
else:
d["spaces"] += 1
return d
```
## Test Cases
``` Python
assert (got := solve("Hello World 123")) == {
"vowels": 3,
"consonants": 7,
"digits": 3,
"spaces": 2,
}, f"{got=}"
assert (got := solve("")) == {
"consonants": 0,
"digits": 0,
"spaces": 0,
"vowels": 0,
}, f"{got=}"
assert (got := solve("AEIOU")) == {
"consonants": 0,
"digits": 0,
"spaces": 0,
"vowels": 5,
}, f"{got=}"
assert (got := solve("bcdfg")) == {
"consonants": 5,
"digits": 0,
"spaces": 0,
"vowels": 0,
}, f"{got=}"
assert (got := solve("12345")) == {
"consonants": 0,
"digits": 5,
"spaces": 0,
"vowels": 0,
}, f"{got=}"
assert (got := solve(" ")) == {
"consonants": 0,
"digits": 0,
"spaces": 3,
"vowels": 0,
}, f"{got=}"
```
# [Remove Elements from Array](remove_elements_from_array_172.py)
Write a function `solve` that removes all instances of a given value from an
array and returns the modified array.
## Solution
``` Python
def solve(nums, val):
return [i for i in nums if i != val]
```
## Test Cases
``` Python
assert (got := solve([3, 2, 2, 3], 3)) == [2, 2], f"{got=}"
assert (got := solve([0, 1, 2, 2, 3, 0, 4, 2], 2)) == [
0,
1,
3,
0,
4,
], f"{got=}"
assert (got := solve([], 1)) == [], f"{got=}"
assert (got := solve([1, 1, 1], 1)) == [], f"{got=}"
assert (got := solve([1, 2, 3], 4)) == [1, 2, 3], f"{got=}"
assert (got := solve([5], 5)) == [], f"{got=}"
```
# [Check if Array is Arithmetic Progression](ciaiap_173.py)
Write a function `solve` that checks if an array can be rearranged to form an
arithmetic progression. An arithmetic progression is a sequence where the
difference between consecutive terms is constant.
## Solution
``` Python
def solve(arr):
if len(arr) > 2:
arr.sort()
delta = arr[1] - arr[0]
for i in range(1, len(arr) - 1):
if arr[i + 1] != arr[i] + delta:
return False
return True
```
## Test Cases
``` Python
assert (got := solve([3, 5, 1])) is True, f"{got=}"
assert (got := solve([1, 2, 4])) is False, f"{got=}"
assert (got := solve([1, 1, 1])) is True, f"{got=}"
assert (got := solve([0])) is True, f"{got=}"
assert (got := solve([5, 1, 3])) is True, f"{got=}"
assert (got := solve([2, 4, 6, 8])) is True, f"{got=}"
```
# [Valid Phone Number](valid_phone_number_174.py)
Write a function `solve` that validates if a string is a valid US phone number.
Valid formats are:
- (123) 456-7890
- 123-456-7890
- 123.456.7890
- 1234567890
## Solution
``` Python
def solve(phone):
return len([i for i in phone if i.isdecimal()]) == 10
```
## Test Cases
``` Python
assert (got := solve("(123) 456-7890")) is True, f"{got=}"
assert (got := solve("123-456-7890")) is True, f"{got=}"
assert (got := solve("123.456.7890")) is True, f"{got=}"
assert (got := solve("1234567890")) is True, f"{got=}"
assert (got := solve("123-45-6789")) is False, f"{got=}"
assert (got := solve("12345")) is False, f"{got=}"
```
# [Calculate Median of Array](calculate_median_of_array_175.py)
Write a function `solve` that calculates the median of an array of numbers.
The median is the middle value when numbers are sorted. For even-length arrays,
return the average of the two middle values.
## Solution
``` Python
import statistics
def solve(nums):
return statistics.median(nums)
```
## Test Cases
``` Python
assert (got := solve([3, 1, 2])) == 2, f"{got=}"
assert (got := solve([1, 2, 3, 4])) == 2.5, f"{got=}"
assert (got := solve([5])) == 5, f"{got=}"
assert (got := solve([1, 2])) == 1.5, f"{got=}"
assert (got := solve([7, 9, 3, 5])) == 6, f"{got=}"
assert (got := solve([10, 20, 30, 40, 50])) == 30, f"{got=}"
```
# [Check if Binary Tree is Symmetric](check_if_binary_tree_is_symmetric_176.py)
Write a function `solve` that checks if a binary tree is symmetric around its
center. The tree is represented as a list where None represents a missing node.
## Solution
``` Python
def solve(root):
def is_symmetric(left, right):
if not left and not right:
return True
if not left or not right or left.val != right.val:
return False
return is_symmetric(left.left, right.right) and is_symmetric(
left.right, right.left
)
return not root or is_symmetric(root.left, root.right)
```
## Test Cases
``` Python
# Binary Tree Definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bt(items, index=0):
if len(items) <= 0 or len(items) <= index:
return None
elif items[index] is None:
items.insert(2 * index + 1, None)
items.insert(2 * index + 2, None)
return None
node = TreeNode(items[index])
node.left = bt(items, 2 * index + 1)
node.right = bt(items, 2 * index + 2)
return node
assert (got := solve(bt([1, 2, 2, 3, 4, 4, 3]))) is True, f"{got=}"
assert (got := solve(bt([1, 2, 2, None, 3, None, 3]))) is False, f"{got=}"
assert (got := solve(bt([1]))) is True, f"{got=}"
assert (got := solve(bt([]))) is True, f"{got=}"
assert (got := solve(bt([1, 2, 3]))) is False, f"{got=}"
assert (got := solve(bt([1, 2, 2]))) is True, f"{got=}"
```
# [Implement Stack Using Queues](implement_stack_using_queues_177.py)
Write a function `solve` that simulates stack operations using queue operations.
Given a list of operations, return the results. Operations are:
- ["push", x]: Push x to stack
- ["pop"]: Remove and return top element
- ["top"]: Return top element without removing
- ["empty"]: Return true if stack is empty
## Solution
``` Python
def solve(operations):
results, queue = [], []
for op in operations:
match op:
case ["push", x]:
results.append(queue.append(x))
case ["pop"]:
results.append(queue.pop())
case ["top"]:
results.append(queue[-1])
case ["empty"]:
results.append(not queue)
return results
```
## Test Cases
``` Python
assert (got := solve([["push", 1], ["push", 2], ["top"], ["pop"], ["empty"]])) == [
None,
None,
2,
2,
False,
], f"{got=}"
assert (got := solve([["empty"]])) == [True], f"{got=}"
assert (got := solve([["push", 5], ["top"], ["pop"], ["empty"]])) == [
None,
5,
5,
True,
], f"{got=}"
assert (got := solve([["push", 1], ["push", 2], ["push", 3], ["pop"], ["pop"]])) == [
None,
None,
None,
3,
2,
], f"{got=}"
assert (got := solve([["push", 10], ["empty"], ["top"]])) == [
None,
False,
10,
], f"{got=}"
assert (got := solve([["push", 7], ["push", 8], ["pop"], ["top"]])) == [
None,
None,
8,
7,
], f"{got=}"
```
!!!BWL: THE BEER-WARE LICENSE (Revision 42)
Carlo~~@~~Miron~~.IT~~ wrote this file. As long as you retain this notice
you can do whatever you want with this stuff. If we meet some day, and
you think this stuff is worth it, you can buy me a beer in return. —㎝