The leetcode API Reference¶
Routines for working with leetcode practice
The two modules inside of this package are packed with useful features:
mock_testFor unit test, this module uses unit testing framework to supports test automation, sharing of setup and shutdown code for tests.
solutionThis module provides a Solution object that is the implementation corresponding to each of quizs.
solution_designThis module provides a Solution Design object that is the implementation corresponding to design quizs.
The “mocktest” module¶
Use the SolutionCase class to represent unit testing framework
- class leetcode.mocktest.SolutionCase(methodName='runTest')[source]¶
A
SolutionCaseobject is the unittest module (dummy component).This module can construct and run tests by using assertEqual(a, b) assert methods to check for and report failures.
If the unittest unit testing framework is correct, then the script produces an output that looks like this:
---------------------------------------------------------------------- Ran 2 tests in 1.314s
- test_lengthOfLongestSubstring()[source]¶
Longest Substring Without Repeating Characters docstring for lengthOfLongestSubstring
- test_minimumCardPickup()[source]¶
Minimum Consecutive Cards to Pick Up docstring for minimumCardPickup
- test_originalDigits()[source]¶
Reconstruct Original Digits from English docstring for originalDigits
The “solution” module¶
Use the Solution class to represent Leedcode problems
- class leetcode.impl.solution.Solution[source]¶
A
solutionobject is the leetcode quiz moduleThis module is to implementate the leetcode problems
- WildcardisMatch(s: str, p: str) bool[source]¶
Wildcard Matching (Hard)
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’ where:
‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).
- Parameters:
s (str) – input string
p (str) – pattern
- Returns:
whether or not input staring and pattern are matched
- Return type:
bool
- appendCharacters(s: str, t: str) int[source]¶
Append Characters to String to Make Subsequence
You are given two strings s and t consisting of only lowercase English letters.
Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s
A subsequence is a string that can be derived from anothers string by deleting some or no characters without changing the order of the remaining characters
- Parameters:
s (str) – string consisting of only lowercase
t (str) – string consisting of only lowercase
- Returns:
the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s
- Return type:
int
- arrayNesting(nums: List[int]) int[source]¶
565. Array Nesting (Medium) You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].
You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], … } subjected to the following rule:
The first element in s[k] starts with the selection of the element nums[k] of index = k. The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on. We stop adding right before a duplicate element occurs in s[k].
Return the longest length of a set s[k].
- Parameters:
nums (List[int]) – integer array nums of length n
- Returns:
the longest length of a set s[k]
- Return type:
int
- buildArray(nums: List[int]) List[int][source]¶
Build Array from Permutationn (Easy)
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.
A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).
- Parameters:
nums (List[int]) – a zero-based permutation nums
- Returns:
build an array of the same length where asn[i] = nums[nums[i]] (zero-based permutation)
- Return type:
List[int]
- buildTree(preorder: List[int], inorder: List[int]) Optional[TreeNode][source]¶
Construct Binary Tree from Preorder and Inorder Traversal
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
- Parameters:
preorder (List[int]) – preorder binary tree
inorder (List[int]) – inorder binary tree
- Returns:
Construct binary tree
- Return type:
Optional[TreeNode]
- canFinish(numCourses: int, prerequisites: List[List[int]]) bool[source]¶
Course Schedule (Medium)
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
- Parameters:
numCourses (int) – total of number courses you have to take
prerequisites (List[List[int]]) – array prerequisites
- Returns:
whether or not you can finish all courses.
- Return type:
bool
- climbStairs(n: int) int[source]¶
Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
- Parameters:
n (int) – take n steps
- Returns:
how many distinct ways can climb to the top
- Return type:
int
- coinChange(coins: List[int], amount: int) int[source]¶
Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
- Parameters:
param (List[int]) – an integer array coins
- Returns:
the fewest number of coins that you need to make up that amount
- Return type:
int
- combinationSum(candidates: List[int], target: int) List[List[int]][source]¶
Combination Sum (Medium)
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
- Parameters:
candidates (List[int]) – distinct integer candidates
- Returns:
a list of all unique combinations of candidates where the chosed numbers sum to target
- Return type:
List[List[int]]
- combinationSum2(candidates: List[int], target: int) List[List[int]][source]¶
Combination Sum II (Medium)
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
- Parameters:
param (List[int]) – a collection of candidate numbers
target (int) – a target number
- Returns:
all unique combinations in candidates where the candidates numbers sum to target
- Return type:
List[List[int]]
- Raises:
e – Description
- containDuplicate(nums: List[int]) bool[source]¶
Contains Duplicate docstring for containDuplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
- Parameters:
List[int] (List[int]) – an integer array nums
- Returns:
Whether or not any value appears at least twice in the array
- Return type:
bool
- convertToTitle(columnNumber: int) str[source]¶
Excel Sheet Column Title (Medium)
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
- Parameters:
columnNumber (int) – Execel sheet
- Returns:
its corresponding column title
- Return type:
int
- countSubarrays(nums: List[int], k: int) int[source]¶
Count Subarrays With Median K
You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k.
Return the number of non-empty subarrays in nums that have a median equal to k.
Note: - The median of an array is the middle element after sorting the array in ascending order. If the array is of even length, the median is the left middle element. - For example, the median of [2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4. - A subarray is a contiguous part of an array.
- Parameters:
nums (List[int]) – an array nums of size n consisting of distinct integers from 1 to n
- Returns:
the number of non-empty subarrays in nums that have a median equal to k
- Return type:
int
- criticalConnections(n: int, connections: List[List[int]]) List[List[int]][source]¶
Critical Connections in a Network (HARD)
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some servers unable to reach some other server.
Return all critical connections in the network in any order.
- Parameters:
connections (List[List[int]]) – Undirected server-to-server connections forming a network
- Returns:
all critical connections in the network in any order
- Return type:
List[List[int]]
- dailyTemperatures(temperatures: List[int]) List[int][source]¶
Daily Temperatures (Medium)
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
- Parameters:
temperatures (List[int]) – an array of integers temperatures
- Returns:
an array is the number of days you have to wait after the ith day to get warmer temperature.
- Return type:
List[int]
- dayOfTheWeek(day: int, month: int, year: int) str[source]¶
Day of the Week
Given a date, return the corresponding day of the week for that date. The input is given as three integers representing the day, month and year respectively.
Return the answer as one of the following values {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}.
- Parameters:
day (int) – the day
month (int) – the month
year (int) – the year
- Returns:
the corresponding day of the week for that date
- Return type:
str
- dayOfYear(date: str) int[source]¶
Day of the Year
Given a string date representing a Gregorian calendar date formatted as YYYY-MM-DD, return the day number of the year.
- Parameters:
date (str) – stringg date
- Returns:
the day number of the year
- Return type:
int
- daysBetweenDates(date1: str, date2: str) int[source]¶
Number of Days Between Two Dates
Write a program to count the number of days between two dates.
The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.
- Parameters:
date1 (str) – the date 1
date2 (str) – the date 2
- Returns:
the number of days between two dates
- Return type:
int
- findCircleNum(isConnected: List[List[int]]) int[source]¶
Number of Provinces (Medium)
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
- Parameters:
isConnected (List[List[int]]) – a province is a group of directly or indirectly connected cities and no other cities outside of the group
- Returns:
the total number of provinces
- Return type:
int
- findKthLargest(nums: List[int], k: int) int[source]¶
Kth Largest Element in an Array (Medium)
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
You must solve it in O(n) time complexity.
- Parameters:
nums (List[int]) – an integer array nums
k (int) – an integer
- Returns:
the kth largest element
- Return type:
intn
- findMedianSortedArrays(nums1: List[int], nums2: List[int]) float[source]¶
Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
- Parameters:
nums1 (List[int]) – sorted array
nums2 (List[int]) – sorted array
- Returns:
the median of the two sorted arrays
- Return type:
float
- findMin(nums: List[int]) int[source]¶
Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times.
- Parameters:
nums (List[int]) – sorted rotated array of unique elements
- Returns:
the minimum element of this array
- Return type:
int
- findPeakElement(nums: List[int]) int[source]¶
Find Peak Element (Medium)
A peak element is an element that is strictly greater than its neighbors.
Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞.
You must write an algorithm that runs in O(log n) time.
- Parameters:
nums (int) – integer array
- Returns:
peak element
- Return type:
int
- firstUniqChar(s: str) int[source]¶
First Unique Character in a String
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
- Parameters:
s (str) – string
- Returns:
the first non-repeating character
- Return type:
Type
- Raises:
e – Description
- floodFill(image: List[List[int]], sr: int, sc: int, color: int) List[List[int]][source]¶
Flood Fill (Easy)
An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.
You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].
To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.
Return the modified image after performing the flood fill.
- Parameters:
image (List[List[int]]) – integer grid image represents the pixel value of the image
sr (int) – source x-index
sc (int) – source y-index
color (int) – color of all of the aforementioned pixels color
- Returns:
the modified image after performing the flood fill
- Return type:
List[List[int]]
- getSum(a: int, b: int) int[source]¶
Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -
- Parameters:
a (int) – integer
b (int) – integer
- Returns:
the sum of the two integers
- Return type:
int
- groupAnagrams(strs: List[str]) List[List[str]][source]¶
Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
- Parameters:
strs (List[str]) – array of strings
- Returns:
the answer in any order
- Return type:
List[List[str]]
- halvesAreAlike(s: str) bool[source]¶
Determine if String Halves Are Alike docstring for halvesAreAlike (Easy)
You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.
Two strings are alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’).
Notice that s contains uppercase and lowercase letters.
Return true if a and b are alike. Otherwise, return false.
- Parameters:
s (str) – string
- Returns:
Determine if string halves are alike (the same number of vowels)
- Return type:
bool
- hasCycle(head: Optional[ListNode]) bool[source]¶
Linked List Cycle (Easy)
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
- Parameters:
head (Optional[List[ListNode]]) – head of a linked list
- Returns:
whether or not there is a cycle in the linked list
- Return type:
bool
- hasPathSum(root: Optional[TreeNode], targetSum: int) bool[source]¶
Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
- Parameters:
root (Optional[TreeNode]) – the root of a binary tree
targetSum (int) – target Sum
- Returns:
if the tree has a root-to-leaf path that adding up all the values along the path equals targetSum
- Return type:
bool
- isIsomorphic(s: str, t: str) bool[source]¶
Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
- Parameters:
s (str) – string
:param t; string :type t; str
- Returns:
if two string are isomorphic
- Return type:
bool
- isMatch(s: str, p: str) bool[source]¶
Regular Expression Matching (HARD)
Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:
‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).
- Parameters:
s (string) – input string
p (string) – pattern character
- Returns:
whehter the matching pattern cover the entire input string
- Return type:
bool
- isPalindrome(s: str) bool[source]¶
Valid Palindrome (Easy)
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
- Parameters:
s (str) – a string
- Returns:
whether or not a string is palindrome
- Return type:
bool
- isPalindromeNum(x: int) bool[source]¶
9. Parlindrome Number (Easy) Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.
For example, 121 is a palindrome while 123 is not.
- Parameters:
x (int) – an integer
- Returns:
whether or not an integer is palindrome
- Return type:
bool
- isPathCrossing(path: str) bool[source]¶
Path Crossing
Given a string path, where path[i] = ‘N’, ‘S’, ‘E’ or ‘W’, each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.
Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.
- Parameters:
path (str) – a string path, where path[i] = ‘N’, ‘S’, ‘E’, or ‘W’
- Returns:
wheher or not the path crosses itself at any point
- Return type:
bool
- isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) bool[source]¶
Same Tree (Easy)
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
- Parameters:
p (Optional[TreeNode]) – binary tree
q (Optional[TreeNode]) – binary tree
- Returns:
Whether two binary trees are considered the same
- Return type:
bool
- isValid(s: str) bool[source]¶
Valid Parentheses
Given a string s containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.
- Parameters:
s (str) – string containing just characters
- Returns:
determine if the input string is valid
- Return type:
bool
- isValidSudoku(board: List[List[str]]) bool[source]¶
Valid Sudoku (Medium)
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.
- Parameters:
board (List[List[str]]) – Sudoku board
- Returns:
Determine if Sudoku board is valid
- Return type:
bool
- judgeCircle(moves: str) bool[source]¶
Robot Return to Origin (Easy)
There is a robot starting at the position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
You are given a string moves that represents the move sequence of the robot where moves[i] represents its ith move. Valid moves are ‘R’ (right), ‘L’ (left), ‘U’ (up), and ‘D’ (down).
Return true if the robot returns to the origin after it finishes all of its moves, or false otherwise.
Note: The way that the robot is “facing” is irrelevant. ‘R’ will always make the robot move to the right once, ‘L’ will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.
- Parameters:
moves (str) – the represents the move sequence of the robot
- Returns:
whether or not the robot returns to the origin after it finishes all of its moves
- Return type:
bool
- kClosest(points: List[List[int]], k: int) List[List[int]][source]¶
K Closest Points to Origin (Medium)
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
- Parameters:
points (List[List[int]]) – an array of points represents a point on the X-Y plane
k (int) – k closest points to the origin (0, 0)
- Returns:
unique closest points to the origin
- Return type:
List[List[int]]
- kSmallestPairs(nums1: List[int], nums2: List[int], k: int) List[List[int]][source]¶
Find K Pairs with Smallest Sums (Medium)
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u, v) which consists of one element from the first array and one element from the second array.
Return the k pairs (u1, v1), (u2, v2), …, (uk, vk) with the smallest sums.
- Parameters:
num1 – integer array sorted in ascending order
nums2 (List[int]) – integer array sorted in ascending order
- Returns:
the k pair (u1, v1), (u2, v2). …, (uk, vk)
- Return type:
List[List[int]]
- lengthOfLIS(nums: List[int]) int[source]¶
Longest Increasing Subsequence (Medium)
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [0, 3, 6, 7] is a subsequence of the array [0,3,1,6,2,2,7].
- Parameters:
nums (List[int]) – array nums
- Returns:
the longest strictly increasing subsequence
- Return type:
int
- lengthOfLastWord(s: str) int[source]¶
Length of Last Word (Easy)
Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal substring consisting of non-space characters only.
- Parameters:
s (str) – string consisting of words and spaces
- Returns:
the length if the last word in the string
- Return type:
int
- lengthOfLongestSubstring(s: str) int[source]¶
Longest Substring Without Repeating Characters (Medium)
Given a string s, find the length of the longest substring without repeating characters.
- Parameters:
s (str) – string
- Returns:
the length of the longest substring without repeating characters
- Return type:
int
- longestCommonPrefix(strs: List[str]) str[source]¶
Longest Common Prefix (Easy)
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
- Parameters:
strs (List[str]) – array of strings
- Returns:
the longest common prefix string amongst an array of strings
- Return type:
str
- longestNiceSubstring(s: str) str[source]¶
Longest Nice Substring (Easy)
A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase.
For example, “abABB” is nice because ‘A’ and ‘a’ appear, and ‘B’ and ‘b’ appear. However, “abA” is not because ‘b’ appears, but ‘B’ does not.
Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence.
If there are none, return an empty string.
- Parameters:
s (str) – string
- Returns:
the longest substring
- Return type:
str
- longestStrChain(words: List[str]) int[source]¶
Longest String Chain (Medium)
You are given an array of words where each word consists of lowercase English letters.
wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.
For example, “abc” is a predecessor of “abac”, while “cba” is not a predecessor of “bcad”.
A word chain is a sequence of words [word1, word2, …, wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.
Return the length of the longest possible word chain with words chosen from the given list of words.
- Parameters:
words (List[str]) – an array of words where each word consists of lowercase English letters.
- Returns:
the length of the longest possible word chain with words choosen from the given list of words
- Return type:
int
- lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) TreeNode[source]¶
Lowest Common Ancestor of a Binary Search Tree (Easy)
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
- Parameters:
root (Optional[TreeNode]) – binary search tree
p (Optional[TreeNode]) – Tree node
q (Optional[TreeNode]) – Tree node
- Returns:
the lowest common ancestor of two given nodes in the BST
- Return type:
Optional[TreeNode]
- majorityElement(nums: List[int]) int[source]¶
Majority Element (Easy)
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
- Parameters:
nums (List[int]) – array nums
- Returns:
the majority element
- Return type:
int
- maxEvents(events: List[List[int]]) int[source]¶
Maximum Number of Events That Can Be Attended
You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d.
Return the maximum number of events you can attend.
- Parameters:
events (List[List[int]]) – an array of events
- Returns:
the maximum number of events you can attend
- Return type:
int
- maxLength(arr: List[str]) int[source]¶
Maximum Length of a Concatencated String with Unique Characters (Medium)
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters that has unique characters.
A subsequence is an array that can be derived from another array of by deleting some or no elements without changing the order of the remaining elements.
- Parameters:
arr (List[str]) – array of strings
- Returns:
the maximum possible length of subsequence
- Return type:
int
- maxProfit(prices: List[int]) int[source]¶
Best Time to Buy and Sell Stock (Easy)
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
- Parameters:
prices (List[int]) – integer array prices
- Returns:
maximum profit you can achieve from this transaction
- Return type:
int
- maxProfitII(prices: List[int]) int[source]¶
Best Time to Buy and Sell Stock II docstring for maxProfit (Medium)
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
- Parameters:
prices (List[int]) – integer array prices
- Returns:
the maximum profit you can achieve
- Return type:
int
- maxProfitIV(k: int, prices: List[int]) int[source]¶
Best Time to Buy and Sell Stock IV (HARD)
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
- Parameters:
prices (List[int]) – the price of a given stock
- Returns:
the maximum profit you can achieve
- Return type:
int
- maxProfitwithfee(prices: List[int], fee: int) int[source]¶
Best Time to Buy and Sell Stock with Transaction Fee (Medium)
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
- param prices:
integer array prices
- type prices:
Lint[int]
- param fee:
transaction fee
- type fee:
int
- return:
the maximum profit you can achieve
- rtype:
int
- maxSubArray(nums: List[int]) int[source]¶
Maximum Subarray (Easy)
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
- Parameters:
nums (List[int]) – integer array
- Returns:
the contiguous subarray
- Return type:
int
- mergeKLists(lists: List[Optional[ListNode]]) Optional[ListNode][source]¶
Merge k Sorted Lists (Hard)
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
- Parameters:
lists (List[Optional[ListNode]]) – an array of k linked-lists lists
- Returns:
merge all the linked-lists into one sored linked-list
- Return type:
Optional[ListNode]
- mergeTrees(root1: Optional[TreeNode], root2: Optional[TreeNode]) Optional[TreeNode][source]¶
Merge Two Binary Trees
- mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) Optional[ListNode][source]¶
Merge Two Sorted Lists
- minDeletionSize(strs: List[str]) int[source]¶
Delete Columns to Make Sorted (Easy)
You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid. For example, strs = [“abc”, “bce”, “cae”] can be arranged as:
abc bce cae
You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 (‘a’, ‘b’, ‘c’) and 2 (‘c’, ‘e’, ‘e’) are sorted while column 1 (‘b’, ‘c’, ‘a’) is not, so you would delete column 1.
Return the number of columns that you will delete.
- Parameters:
strs (List[str]) – array of n string
- Returns:
the number of columns that you will delete
- Return type:
int
- minNumberOfSemesters(n: int, dependencies: List[List[int]], k: int) int[source]¶
Parallel Courses II (HARD)
You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei. Also, you are given the integer k.
In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking.
Return the minimum number of semesters needed to take all courses. The testcases will be generated such that it is possible to take every course.
- Parameters:
n (int) – courses
dependencies (List[List[int]]) – prerequisite relationship between course prevCoursei and course nextCoursei has to be taken before course nextCoursi
k (int) – take at most k courses
- Returns:
minimum number of semesters needed to take all courses
- Return type:
int
- minPathSum(grid: List[List[int]]) int[source]¶
Minimum Path Sum (Medium)
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
- Parameters:
grid (List[List[int]]) – m x n grid filled with non-negative numbers
- Returns:
minimizes the sum of all numbers along its path
- Return type:
int
- minSwaps(nums: List[int]) int[source]¶
Minimum Swaps to Group All 1’s Together II (Medium)
A swap is defined as taking two distinct positions in an array and swapping the values in them.
A circular array is defined as an array where we consider the first element and the last element to be adjacent.
Given a binary circular array nums, return the minimum number of swaps required to group all 1’s present in the array together at any location.
- Parameters:
nums (Lint[int]) – circular array
- Returns:
the minimum number of swaps required to group all 1’s present in the array together at any location
- Return type:
int
- mincostTickets(days: List[int], costs: List[int]) int[source]¶
Minimum Cost For Tickets (Medium)
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three different ways:
a 1-day pass is sold for costs[0] dollars,
a 7-day pass is sold for costs[1] dollars, and
a 30-day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel.
Return the minimum number of dollars you need to travel every day in the given list of days.
- Parameters:
days (List[int]) – the days of the year in which you will travel are given as an integer array days
- Returns:
the minimum number of dollars you need to travel every day in the given list of days
- Return type:
int
- minimumCardPickup(cards: List[int]) int[source]¶
Minimum Consecutive Cards to Pick Up
You are give an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.
Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.
- Parameters:
cards (List[int]) – integer array cards
- Returns:
the minimum number of consecutive cards
- Return type:
int
- minimumLines(stockPrices: List[List[int]]) int[source]¶
Minimum Lines to Represent a Line Chart (Medium)
You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:
Return the minimum number of lines needed to represent the line chart.
- Parameters:
stockPrices (List[List[int]]) – 2D integer array stockPrices
- Returns:
the minimum number of lines needed to represent the line chart
- Return type:
int
- moveZeroes(nums: List[int]) List[int][source]¶
Move Zeroes docstring for fname (Easy)
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
- Parameters:
nums (List[int]) – integer array nums
- Returns:
integer array nums that being move all o’s to the end of it while maintaing the relative order of the non-zero elements
- Return type:
List[int]
- myAtoi(s: str) int[source]¶
String to Integer (atoi) (Medium)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is ‘-’ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
Return the integer as the final result.
- Parameters:
s (str) – a string
- Returns:
a 32-bit signed integer
- Return type:
int
- myPow(x: float, n: int) float[source]¶
Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
- Parameters:
x (float) – the number
n (int) – power
- Returns:
calculates x raised to the power n
- Return type:
float
- nextGreaterElement(nums1: List[int], nums2: List[int]) List[int][source]¶
Next Greater Element I (Easy)
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
- Parameters:
nums1 (List[int]) – integer arrays
nums2 (List[int]) – integer arrays
- Returns:
an array is the next greater element determined by nums1 and nums2
- Return type:
Line[int]
- nextGreaterElementsII(nums: List[int]) List[int][source]¶
Next Greater Element II (Medium)
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.
- Parameters:
nums (List[int]) – circular integer array
- Returns:
the next greater number for every element in nums
- Return type:
List[int]
- numDecodings(s: str) int[source]¶
Decode Ways (Medium)
A message containing letters from A-Z can be encoded into numbers using the following mapping:
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:
“AAJF” with the grouping (1 1 10 6) “KJF” with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
- Parameters:
s (str) – string containing only digits
- Returns:
the number of ways to decode it
- Return type:
int
- originalDigits(s: str) str[source]¶
Reconstruct Original Digits from English (Medium)
Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.
- Parameters:
s (str) – string containing an out-of-order English
- Returns:
the digits in ascending order
- Return type:
str
- pivotIndex(nums: List[int]) int[source]¶
Find Pivot Index
Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index’s right.
If the index is on the left edge of the array. then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.
- Parameters:
nums (List[int]) – an array of integers
- Returns:
the leftmost pivot index
- Return type:
int
- pivotInteger(n: int) int[source]¶
Find the Pivot Integer
Given a positive integer n, find the pivot integer x such that:
The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.
Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.
- Parameters:
n (int) – a positive integer n
- Returns:
the pivot integer
- Return type:
int
- reformatDate(date: str) str[source]¶
Reformat Date
Given a date string in the form Day Month Year, where: - Day is in the set {“1st”, “2nd”, “3rd”, “4th”, …, “30th”, “31st”}. - Month is in the set {“Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”}. - Year is in the range [1900, 2100].
Convert the date string to the format YYYY-MM-DD, where: - YYYY denotes the 4 digit year. - MM denotes the 2 digit month. - DD denotes the 2 digit day.
- Parameters:
date (str) – a date string in the form Day Month Year
- Returns:
the date string to the format YYYY-MM-DD
- Return type:
str
- removeNodes(head: Optional[ListNode]) Optional[ListNode][source]¶
Remove Nodes From Linked List
You are given the head of a linked list.
Remove every node which has a node with a strictly greater value anywhere to the right side of it.
Return the head of the modified linkde list.
- Parameters:
head (Optional[ListNode]) – the head od linked list
- Returns:
the head of the modified linked list
- Return type:
Optional[ListNode]
- removeNthFromEnd(head: Optional[ListNode], n: int) Optional[ListNode][source]¶
Remove Nth Node From End of List
- romanToInt(s: str) int[source]¶
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. (Easy)
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simple X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not III. Instead, the number four is written as IV. Because the one is before the five we substract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where substraction used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90
C can be placed before D (500) and M (1000) to make 400 and 900
Given a roman numeral, convert it to an integer.
- Parameters:
s (string) – Roman numeral
- Returns:
integer
- Return type:
int
- runningSum(nums: List[int]) List[int][source]¶
Running Sum of 1d Array (Easy)
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
- Parameters:
nums (List[int]) – an array nums
- Returns:
sum of an array as runningSum[i] = sum(nums[0]…nums[i])
- Return type:
List[int]
- search(nums: List[int], target: int) int[source]¶
Binary Search (Easy)
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
- Parameters:
nums (List[int]) – an array of integers
target (int) – integer target
- Returns:
index of target
- Return type:
int
- searchRange(nums: List[int], target: int) List[int][source]¶
Find First and Last Position of Element in Sorted Array (Medium)
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
- Parameters:
nums (List[int]) – array of integers
- Returns:
the starting and ending position of a given target value
- Return type:
List[int]
- shortestDistance(grid: List[List[int]]) int[source]¶
Shortest Distance from All Buildings
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down left, and right. You are given a 2D grid of values 0, 1, 2, where:
Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
- Parameters:
grid (List[List[int]]) – 2D grid
- Returns:
the shortest distance from all buildings
- Return type:
int
- simplifyPath(path: str) str[source]¶
Simplify Path (Medium)
Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.
The canonical path should have the following format:
The path starts with a single slash ‘/’. Any two directories are separated by a single slash ‘/’. The path does not end with a trailing ‘/’. The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘.’ or double period ‘..’)
Return the simplified canonical path.
- Parameters:
path (str) – an absolute path to a file or directory in a Uinx-style file system
- Returns:
canonical path
- Return type:
str
- strongPasswordChecker(password: str) int[source]¶
Strong Password Checker (HARD)
A password is considered strong if the below conditions are all met:
It has at least 6 characters and at most 20 characters. It contains at least one lowercase letter, at least one uppercase letter, and at least one digit. It does not contain three repeating characters in a row (i.e., “…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met). Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
Insert one character to password, Delete one character from password, or Replace one character of password with another character.
- Parameters:
password (str) – password
- Returns:
the minimum number of steps required to make password strong
- Return type:
int
- subsets(nums: List[int]) List[List[int]][source]¶
Subsets (Medium)
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
- Parameters:
param (List[int]) – integer array nums of unique elements
- Returns:
all possible subsets (the power set)
- Return type:
List[List[int]]
- threeSum(nums: List[int]) List[List[int]][source]¶
3Sum (Medium)
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
- Parameters:
nums (List[int]) – integer array nums
- Returns:
all the triplets
- Return type:
List[List[int]]
- topKFrequent(nums: List[int], k: int) List[int][source]¶
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order
:param : integer array :type : int
- Returns:
the k most frequent elements
- Return type:
List[int]
- totalStrength(strength: List[int]) int[source]¶
Sum of Total Strength of Wizards (Hard)
As the ruler of a kingdom, you have an army of wizards at your command.
You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the ith wizard.
For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:
The strength of the weakest wizard in the group.
The total of all the individual strengths of the wizards in the group.
Return the sum of the total strengths of all contiguous groups of wizards.
Since the answer may be very large, return it modulo 109 + 7.
A subarray is a contiguous non-empty sequence of elements within an array.
- Parameters:
strength (Lint[int]) – integer array strength
- Returns:
the sum of the total strengths of all contiguous groups of wizards
- Return type:
int
- twoSum(nums: List[int], target: int) List[int][source]¶
Two Sum (Easy)
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
- Parameters:
num (List[int]) – array of integers
target (int) – integer target
- Returns:
indices of the two numbers such that they add up to target
- Return type:
List[int]
- wordPattern(pattern: str, s: str) bool[source]¶
Word Pattern (Easy)
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between letter in pattern and a non-empty word in s.
- Parameters:
pattern (str) – pattern
s (str) – non-empty word
- Returns:
if there is a bijection between a letter in pattern and a non-empty word in s
- Return type:
bool
The “solution_design” module¶
Use the Solution class to represent Leedcode problems - design