Practice

Math

Data Structures

Practice

Array

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell

Example 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0

Constraints

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Kadane's Algorithm	Finds the maximum subarray sum in an array, requires two variables, min_price and max_profit, to iteratively update and track the maximum sum ending at the current position and the overall maximum sum, respectively	Time: O(n): iterates through the array of stock prices once Space: O(1): no extra space is used	def maxProfit(prices): min_price = prices[0] max_profit = 0 for price in prices[1:]: max_profit = max(max_profit, price - min_price) min_price = min(min_price, price) return max_profit

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49

Example 2

Input: height = [1,1]
Output: 1

Constraints

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Two-Pointer	Starts wide, moves inward. Moving pointers explores potentially higher areas	Time: O(n): iterates through the array Space: O(1): no extra space is used	def maxArea(height): left = 0 right = len(height) - 1 maxArea = 0 while left < right: currentArea = min(height[left], height[right]) * (right - left) maxArea = max(maxArea, currentArea) if height[left] < height[right]: left += 1 else: right -= 1 return maxArea

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1

Input: nums = [1,2,3,1]
Output: true

Example 2

Input: nums = [1,2,3,4]
Output: false

Example 3

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Constraints

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Brute-Force	Compares each element with every other element in the array to check for duplicates	Time: O(n²): traverse the list containing n elements exactly n² times Space: O(1): space required does not depend on the size of the input array, so only constant space is used	def containsDuplicate(nums): for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): if nums[i] == nums[j]: return True return False
Sorting	Sorts the array in ascending order and then checks for adjacent elements that are the same	Time: O(n log n): sort the list containing n elements in O(n log n) Space: O(1): no extra space is used	def containsDuplicate(nums): nums.sort() for i in range(1, len(nums)): if nums[i] == nums[i - 1]: return True return False
Hash Set	Use a hash set to store encountered elements. Iterate through the array, checking if an element is already in the set	Time: O(n): traverse the list containing n elements exactly once Space: O(n): the extra space required depends on the number of items stored in the hash set, which stores at most n elements	def containsDuplicate(nums): seen = set() for num in nums: if num in seen: return True seen.add(num) return False
Hash Map	Use a hash map to store the elements as keys and their counts as values. Duplicate element is found if its count >= 1	Time: O(n): traverse the list containing n elements exactly once Space: O(n): the extra space required depends on the number of items stored in the hash map, which stores at most n elements	def containsDuplicate(nums): seen = {} for num in nums: if num in seen and seen[num] >= 1: return True seen[num] = seen.get(num, 0) + 1 return False

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
• Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

Given the sorted rotated array nums of unique elements, return the minimum element of this array

Example 1

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times

Example 2

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times

Example 3

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times

Constraints

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique
• nums is sorted and rotated between 1 and n times

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Binary Search	In each iteration of the while loop, the search space is halved	Time: O(log n): time grows logarithmically with the input size Space: O(1): no extra space is used	def findMin(self, nums): left, right = 0, len(nums)-1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]

Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product

Example 1

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6

Example 2

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray

Constraints

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Dynamic Programming	DP sub-problem is to find the maximum and minimum products for contiguous sub-arrays from the 0th to the current element. Maintaining the minimum product is crucial because negative elements can transform the current product into a greater value when multiplied by the previous minimum product	Time: O(n): scan the array once Space: O(1): no extra space is used	def maxProduct(nums): curMax, curMin = 1, 1 res = nums[0] for num in nums: vals = (num, num * curMax, n * curMin) curMax, curMin = max(vals), min(vals) res = max(res, curMax) return res

Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6

Example 2

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Dynamic Programming	Find the largest sum of consecutive elements by tracking current and maximum sums while iterating and reset current sum if negative	Time: O(n):linear, processes each element of the array exactly once in a single loop Space: O(1): no extra space is used	def maxSubArray(nums): maxSum = nums[0] currentSum = nums[0] for num in nums[1:]: currentSum = max(num, currentSum + num) maxSum = max(maxSum, currentSum) return maxSum

Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer

Example 1

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Dynamic Programming	Calculate all the products to the left and right of any given element just once and reuse those calculations	Time: O(n): linear, processes each element of the array exactly once Space: O(n): the extra space required depends on the size of the input array	def productExceptSelf(self, nums: List[int]) -> List[int]: products = [1] * len(nums) for i in range(1, len(nums)): products[i] = products[i-1] * nums[i-1] right = nums[-1] for i in range(len(nums) - 2, -1, -1): products[i] *= right right *= nums[i] return products

Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3

Input: nums = [1], target = 0
Output: -1

Constraints

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique
• nums is an ascending array that is possibly rotated
• -104 <= target <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Binary Search	nums array [17, 18, 19, 0, 1, 2, 3]. If target is 18 then [17, 18, 19, inf, inf, inf, inf]. If target is 2 then [-inf, -inf, -inf, 0, 1, 2, 3]. Then use binary search	Time: O(log n): time grows logarithmically with the input size Space: O(1): no extra space is used	def search(nums, target): left, right = 0, len(nums) while left < right: mid = (left + right) // 2 if (nums[mid] < nums[0]) == (target < nums[0]): num = nums[mid] else: num = float('-inf') if target < nums[0] else float('inf') if num == target: return mid if num < target: left = mid + 1 elif num > target: right = mid return -1

2Sum (Two Sum)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109

Only one valid answer exists

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Brute Force	Loop through each element x and find if there is another value that equals to target - x	Time: O(n^2): For each element, we try to find it's complement by looping through the rest of the array which takes O(n) time Space: O(1): The space required does not depend on the size of the input array, so only constant space is used	twoSum(nums, target): for i from 0 to nums.length: for j from i + 1 to nums.length: if nums[j] == target - nums[i]: return [i, j]
Two-pass Hash Table	Using hash table reduces lookup from O(n) to nearly constant O(1) time. A hash table efficiently maps array elements to their indices. We iterate through the array, storing elements and their indices. Then, we check if each element's complement exists in the hash table. If so, we've found a pair	Time: O(n): We traverse the list containing n elements exactly twice. Since the hash table reduces the lookup time to O(1), the overall time complexity is O(n) Space: O(n): The extra space required depends on the number of items stored in the hash table, which stores exactly n elements	twoSum(nums, target): hashmap = {} for i from 0 to nums.length: hashmap[nums[i]] = i for i from 0 to nums.length: complement = target - nums[i] if complement in hashmap and hashmap[complement] != i: return [i, hashmap[complement]]
One-pass Hash Table	Check for complements while building the hash table. If a complement is found, we've located the pair and can stop immediately	Time: O(n): We traverse the list containing n elements only once. Each lookup in the table costs only O(1) time Space: O(n): The extra space required depends on the number of items stored in the hash table, which stores at most n elements	twoSum(nums, target): hashmap = {} for i from 0 to nums.length: complement = target - nums[i] if complement in hashmap: return [i, hashmap[complement]] hashmap[nums[i]] = i

3Sum (Three Sum)

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
The distinct triplets are [-1,0,1] and [-1,-1,2]
Notice that the order of the output and the order of the triplets does not matter

Example 2

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0

Example 3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0

Constraints

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
Two Pointer		Time: :</li> <li><b>Space</b>: :	def threeSum(nums): res = [] nums.sort() for current in range(len(nums)): # Skip duplicate if current > 0 and nums[current] == nums[current - 1]: continue left = current + 1 right = len(nums) - 1 while left < right: sum = nums[current] + nums[left] + nums[right] if sum > 0: right -= 1 elif sum < 0: left += 1 else: res.append([nums[current], nums[left], nums[right]]) left += 1 # Skip duplicate for the left pointer while left <· right and nums[left] == nums[left - 1]: left += 1 return res

Binary

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i

Example 1

Input: n = 2
Output: [0,1,1]
Explanation:

• 0 --> 0
• 1 --> 1
• 2 --> 10

Example 2

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:

• 0 --> 0
• 1 --> 1
• 2 --> 10
• 3 --> 11
• 4 --> 100
• 5 --> 101

Constraints

• 0 <= n <= 105

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array

Example 1

Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums

Example 2

Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums

Example 3

Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums

Constraints

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Number of 1 Bits

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight)

Example 1

Input: n = 11
Output: 3
Explanation: The input binary string 1011 has a total of three set bits

Example 2

Input: n = 128
Output: 1
Explanation: The input binary string 10000000 has a total of one set bit

Example 3

Input: n = 2147483645
Output: 30
Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits

Constraints

• 1 <= n <= 231 - 1

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Reverse Bits

Reverse bits of a given 32 bits unsigned integer

Note

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825

Example 1

Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000

Example 2

Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111

Constraints

• The input must be a binary string of length 32

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -

Example 1

Input: a = 1, b = 2
Output: 3

Example 2

Input: a = 2, b = 3
Output: 5

Constraints

• -1000 <= a, b <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Dynamic Programming

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?

Example 1

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

• 1 step + 1 step
• 2 steps

Example 2

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

• 1 step + 1 step + 1 step
• 1 step + 2 steps
• 2 steps + 1 step

Constraints

• 1 <= n <= 45

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

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.

Example 1

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2

Input: coins = [2], amount = 3
Output: -1

Example 3

Input: coins = [1], amount = 0
Output: 0

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Combination Sum

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

Example 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:

• 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times
• 7 is a candidate, and 7 = 7
• These are the only two combinations

Example 2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3

Input: candidates = [2], target = 1
Output: []

Constraints

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct
• 1 <= target <= 40

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Decode Ways

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

• "1" -> 'A'
• "2" -> 'B'
• ...
• "25" -> 'Y'
• "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (2 and 5 vs 25). For example, 11106 can be decoded into:

• AAJF with the grouping (1, 1, 10, 6)
• KJF with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because 06 is not a valid code (only 6 is valid)

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

Example 1

Input: s = 12
Output: 2
Explanation: 12 could be decoded as AB (1 2) or L (12)

Example 2

Input: s = 226
Output: 3
Explanation: 226 could be decoded as BZ (2 26), VF (22 6), or BBF (2 2 6)

Example 3

Input: s = 06
Output: 0
Explanation: 06 cannot be mapped to F because of the leading zero (6 is different from 06). In this case, the string is not a valid encoding, so return 0

Constraints

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s)

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4

Example 2

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police

Example 1

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses

Example 2

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4

Example 3

Input: nums = [1,2,3]
Output: 3

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise

Example 1

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index

Example 2

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index

Constraints

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, ace is a subsequence of abcde. A common subsequence of two strings is a subsequence that is common to both strings.

Example 1

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is ace and its length is 3

Example 2

Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is abc and its length is 3

Example 3

Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0

Constraints

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence

Example 1

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4

Example 2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner

Example 1

Input: m = 3, n = 7
Output: 28

Example 2

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

• Right -> Down -> Down
• Down -> Down -> Right
• Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because applepenapple can be segmented as apple pen apple. Note that you are allowed to reuse a dictionary word

Example 2

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters
• All the strings of wordDict are unique

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Graph

Alien Dictionary

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language. Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned

Example 1

Input: N = 5, K = 4, dict = {"baa","abcd","abca","cab","cad"}
Output: 1
Explanation: Here order of characters is 'b', 'd', 'a', 'c' Note that words are sorted and in the given language "baa" comes before "abcd", therefore 'b' is before 'a' in output. Similarly we can find other orders

Example 2

Input: N = 3, K = 3, dict = {"caa","aaa","aab"}
Output: 1
Explanation: Here order of characters is 'c', 'a', 'b' Note that words are sorted and in the given language "caa" comes before "aaa", therefore 'c' is before 'a' in output. Similarly we can find other orders

Constraints

• 1 ≤ N, M ≤ 300
• 1 ≤ K ≤ 26
• 1 ≤ Length of words ≤ 50

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Clone Graph

Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list. An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph. The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.

• 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4)
• 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3)
• 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4)
• 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3)

Example 2

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors

Example 3

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes

Constraints

• The number of nodes in the graph is in the range [0, 100]
• 1 <= Node.val <= 100
• Node.val is unique for each node
• There are no repeated edges and no self-loops in the graph
• The Graph is connected and all nodes can be visited starting from the given node

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Course Schedule

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] = [$a_i$, $b_i$] indicates that you must take course $b_i$ first if you want to take course $a_i$. 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.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Graph Valid Tree

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges

Example 1

Input: n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2

Input: n = 5, edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

Example 1

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Note: You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges

Example 1

0        3
|        |
1 - 2    4

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2

Example 2

0       4
|       |
1 - 2 - 3

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 1

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Number of Islands

Given an m x n 2D binary grid 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.

Example 1

Input:

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

Output: 1

Example 2

Input:

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return a 2D list of grid coordinates result where result[i] = [$r_i$, $c_i$] denotes that rain water can flow from cell ($r_i$, $c_i$) to both the Pacific and Atlantic oceans.

Example 1

$$\begin{vmatrix} 1 & 2 & 2 & 3 & (5) \\ 3 & 2 & 3 & (4) & (4) \\ 2 & 4 & (5) & 3 & 1 \\ (6) & (7) & 1 & 4 & 5 \\ (5) & 1 & 1 & 2 & 4 \end{vmatrix}$$

Input:

heights = [
  [1,2,2,3,5],
  [3,2,3,4,4],
  [2,4,5,3,1],
  [6,7,1,4,5],
  [5,1,1,2,4]
]

Output:

[
  [0,4],
  [1,3],
  [1,4],
  [2,2],
  [3,0],
  [3,1],
  [4,0]
]

Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:

[0,4]: [0,4] -> Pacific Ocean
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
       [4,0] -> Atlantic Ocean

Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans

Example 2

Input: heights = [[1]] Output: [[0,0]] Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Heap

Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values

• For example, for arr = [2,3,4], the median is 3
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object
• void addNum(int num) adds the integer num from the data stream to the data structure
• double findMedian() returns the median of all elements so far. Answers within $10^{-5}$ of the actual answer will be accepted

Example 1

Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"], [[], [1], [2], [], [3], []]
Output: [null, null, null, 1.5, null, 2.0]

Explanation:

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints

• -105 <= num <= 105
• There will be at least one element in the data structure before calling findMedian

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Merge K Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it

Example 1

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:

[
  1->4->5,
  1->3->4,
  2->6
]

merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2

Input: lists = []
Output: []

Example 3

Input: lists = [[]]
Output: []

Constraints

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order
• The sum of lists[i].length will not exceed $10^4$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

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

Example 1

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2

Input: nums = [1], k = 1
Output: [1]

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array]
• It is guaranteed that the answer is unique

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Interval

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [$start_i$, $end_i$] represent the start and the end of the $i^{th}$ interval and intervals is sorted in ascending order by $start_i$. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by $start_i$ and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion. Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10]

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by $start_i$ in ascending order
• newInterval.length == 2
• 0 <= start <= end <= 105

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] ($e_i$ > $s_i$), determine if a person could attend all meetings

Example 1

Input: [[0,30],[5,10],[15,20]]
Output: false

Example 2

Input: [[7,10],[2,4]]
Output: true

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] ($e_i$ > $s_i$), find the minimum number of conference rooms required

Example 1

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2

Input: [[7,10],[2,4]]
Output: 1

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Merge Intervals

Given an array of intervals where intervals[i] = [$start_i$, $end_i$], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping

Constraints

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Non-overlapping Intervals

Given an array of intervals where intervals[i] = [$start_i$, $end_i$], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping

Example 3

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping

Constraints

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• $-5 * 10^4 <= start_i <\ end_i <= 5 * 10^4$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Linked List

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed)

Example 2

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node

Example 3

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list

Constraints

• The number of the nodes in the list is in the range [0, 104]
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Merge K Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are:

[
  1->4->5,
  1->3->4,
  2->6
]

merging them into one sorted list: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Example 2

Input: lists = [] Output: []

Example 3

Input: lists = [[]] Output: []

Constraints

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order
• The sum of lists[i].length will not exceed $10^4$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2

Input: list1 = [], list2 = []
Output: []

Example 3

Input: list1 = [], list2 = [0]
Output: [0]

Constraints

• The number of nodes in both lists is in the range [0, 50]
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Remove Nth Node From End Of List

Given the head of a linked list, remove the $n^{th}$ node from the end of the list and return its head.

Example 1

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2

Input: head = [1], n = 1
Output: []

Example 3

Input: head = [1,2], n = 1
Output: [1]

Constraints

• The number of nodes in the list is sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Reorder List

You are given the head of a singly linked-list. The list can be represented as: $L_0 → L_1 → … → L_{n - 1} → L_n$ Reorder the list to be on the following form: $L_0 → L_n → L_1 → L_{n - 1} → L_2 → L_{n - 2} → …$ You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2

**Input: head = [1,2,3,4,5]
**Output: [1,5,2,4,3]

Constraints

• The number of nodes in the list is in the range [1, 5 * $10^4$]
• 1 <= Node.val <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Reverse a Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2

Input: head = [1,2]
Output: [2,1]

Example 3

Input: head = []
Output: []

Constraints

• The number of nodes in the list is the range [0, 5000]
• -5000 <= Node.val <= 5000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Matrix

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1

$$\begin{vmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{vmatrix} \rArr \begin{vmatrix} 7 & 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \end{vmatrix}$$

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2

$$\begin{vmatrix} 5 & 1 & 9 & 11 \\ 2 & 4 & 8 & 10 \\ 13 & 3 & 6 & 7 \\ 15 & 14 & 12 & 16 \end{vmatrix} \rArr \begin{vmatrix} 15 & 13 & 2 & 5 \\ 14 & 3 & 4 & 1 \\ 12 & 6 & 8 & 9 \\ 16 & 7 & 10 & 11 \end{vmatrix}$$

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Example 1

$$\begin{vmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{vmatrix} \rArr \begin{vmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{vmatrix}$$

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2

$$\begin{vmatrix} 0 & 1 & 2 & 0 \\ 3 & 4 & 5 & 2 \\ 1 & 3 & 1 & 5 \end{vmatrix} \rArr \begin{vmatrix} 0 & 0 & 0 & 0 \\ 0 & 4 & 5 & 0 \\ 0 & 3 & 1 & 0 \end{vmatrix}$$

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• $-2^{31} <= matrix[i][j] <= 2^{31} - 1$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1

$$\begin{vmatrix} 1→ & 2→ & 3↓ \\ 4→ & 5 & 6↓ \\ 7↑ & ←8 & ←9 \end{vmatrix}$$

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2

$$\begin{vmatrix} 1→ & 2→ & 3→ & 4↓ \\ 5→ & 6→ & 7 & 8↓ \\ 9↑ & ←10 & ←11 & ←12 \end{vmatrix}$$

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1

$$\begin{vmatrix} [A] & [B] & [C] & E \\ S & F & [C] & S \\ A & [D] & [E] & E \end{vmatrix}$$

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2

$$\begin{vmatrix} A & B & C & E \\ S & F & C & [S] \\ A & D & [E] & [E] \end{vmatrix}$$

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3

$$\begin{vmatrix} A & B & C & E \\ S & F & C & S \\ A & D & E & E \end{vmatrix}$$

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

String

Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement encode and decode

Example 1

Input: ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation: One possible encode method is: lint:;code:;love:;you

Example 2

Input: ["we", "say", ":", "yes"]
Output: ["we", "say", ":", "yes"]
Explanation: One possible encode method is: we:;say:;:::;yes

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

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.

Example 1

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2

Input: strs = [""]
Output: [[""]]

Example 3

Input: strs = ["a"]
Output: [["a"]]

Constraints

• $1 <= strs.length <= 10^4$
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1

Input: s = "babad"
Output: bab
Explanation: "aba" is also a valid answer

Example 2

Input: s = "cbbd"
Output: bb

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa

Example 2

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.

Constraints

• $1 <= s.length <= 10^5$
• s consists of only uppercase English letters
• 0 <= k <= s.length

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3

Example 2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1

Example 3

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring

Constraints

• $<= s.length <= 5 * 10^4$
• s consists of English letters, digits, symbols and spaces

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: BANC
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t

Example 2

Input: s = "a", t = "a"
Output: a
Explanation: The entire string s is the minimum window

Example 3

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string

Constraints

• m == s.length
• n == t.length
• $1 <= m, n <= 10^5$
• s and t consist of uppercase and lowercase English letters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Palindromic Substrings

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Example 1

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c"

Example 2

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa"

Constraints

• 1 <= s.length <= 1000
• s consists of lowercase English letters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

Input: s = "rat", t = "car"
Output: false

Constraints

• $1 <= s.length, t.length <= 5 * 10^4$
• s and t consist of lowercase English letters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome

Example 2

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome

Example 3

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome

Constraints

• $1 <= s.length <= 2 * 10^5$
• s consists only of printable ASCII characters

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Valid Parentheses

Given a string s containing just the characters ( ) [ ] { }, determine if the input string is valid. An input string is valid if:

• Open brackets must be closed by the same type of brackets
• Open brackets must be closed in the correct order
• Every close bracket has a corresponding open bracket of the same type

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "()[]{}"
Output: true

Example 3

Input: s = "(]"
Output: false

Constraints

• $1 <= s.length <= 10^4$
• s consists of parentheses only ( ) [ ] { }

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Tree

Add and Search Word

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class:

• WordDictionary() Initializes the object
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter

Example

Input: ["WordDictionary","addWord","addWord","addWord","search","search","search","search"], [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output: [null,null,null,null,false,true,true,true] Explanation:

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters
• word in search consist of '.' or lowercase English letters
• There will be at most 2 dots in word for search queries
• At most $10^4$ calls will be made to addWord and search

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level)

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1]
Output: [[1]]

Example 3

Input: root = []
Output: []

Constraints

• The number of nodes in the tree is in the range [0, 2000]
• -1000 <= Node.val <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6

Example 2

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42

Constraints

• The number of nodes in the tree is in the range $[1, 3 * 10^4]$
• -1000 <= Node.val <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

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.

Example 1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values
• Each value of inorder also appears in preorder
• preorder is guaranteed to be the preorder traversal of the tree
• inorder is guaranteed to be the inorder traversal of the tree

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Implement Trie (Prefix Tree)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object
• void insert(String word) Inserts the string word into the trie
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise

Example 1

Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"], [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, true, false, true, null, true]
Explanation:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters
• At most $3 * 10^4$ calls in total will be made to insert, search, and startsWith

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Invert/Flip Binary Tree

Given the root of a binary tree, invert the tree, and return its root

Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2

Input: root = [2,1,3]
Output: [2,3,1]

Example 3

Input: root = []
Output: []

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the $k^{th}$ smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints

• The number of nodes in the tree is n
• $1 <= k <= n <= 10^4$
• $0 <= Node.val <= 10^4$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Lowest Common Ancestor of BST

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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)"

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition

Example 3

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints

• The number of nodes in the tree is in the range $[2, 10^5]$
• $-10^9 <= Node.val <= 10^9$
• All Node.val are unique
• p != q
• p and q will exist in the BST

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2

Input: root = [1,null,2]
Output: 2

Constraints

• The number of nodes in the tree is in the range $[0, 10^4]$
• -100 <= Node.val <= 100

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints

• The number of nodes in both trees is in the range [0, 100]
• $-10^4 <= Node.val <= 10^4$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example 1

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2

Input: root = []
Output: []

Constraints

• The number of nodes in the tree is in the range $[0, 10^4]$
• -1000 <= Node.val <= 1000

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Constraints

• The number of nodes in the root tree is in the range [1, 2000]
• The number of nodes in the subRoot tree is in the range [1, 1000]
• $-10^4 <= root.val <= 10^4$
• $-10^4 <= subRoot.val <= 10^4$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key
• The right subtree of a node contains only nodes with keys greater than the node's key
• Both the left and right subtrees must also be binary search trees

Example 1

Input: root = [2,1,3]
Output: true

Example 2

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4

Constraints

• The number of nodes in the tree is in the range $[1, 10^4]$
• $-2^{31} <= Node.val <= 2^{31} - 1$

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1

$$\begin{vmatrix} (o) & (a) & a & n \\ e & [t] & [a] & [e] \\ i & (h) & k & r \\ i & f & l & v \end{vmatrix}$$

Input:

board = [
  ["o","a","a","n"],
  ["e","t","a","e"],
  ["i","h","k","r"],
  ["i","f","l","v"]
],
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Example 2

$$\begin{vmatrix} a & b \\ c & d \end{vmatrix}$$

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter
• $1 <= words.length <= 3 * 10^4$
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters
• All the strings of words are unique

---

Practice

Approach	Algorithm	Complexity Analysis	Implementation
		Time: :</li> <li><b>Space</b>: :

Common Patterns