LeetCode problems
Contents
- 1 About
- 2 LeetCode Problem Set - Top Interview 150 - Solved in Python
- 2.1 Array / String
- 2.1.1 (88) Merge Sorted Array (Easy) Solved
- 2.1.2 (27) Remove Element (Easy) Solved
- 2.1.3 (26) Remove Duplicates from Sorted Array (Easy) Solved (+)
- 2.1.4 (80) Remove Duplicates from Sorted Array II (Medium) Solved
- 2.1.5 (169) Majority Element (Easy) Solved (+)
- 2.1.6 (189) Rotate Array (Medium) Solved
- 2.1.7 (121) Best Time to Buy and Sell Stock (Easy) Solved
- 2.1.8 (122) Best Time to Buy and Sell Stock II (Medium) Solved
- 2.1.9 (55) Jump Game (Medium) Solved
- 2.1.10 (45) Jump Game II (Medium) Solved
- 2.1.11 (274) H-Index (Medium) Solved
- 2.1.12 (380) Insert Delete GetRandom O(1) (Medium) Solved
- 2.1.13 (238) Product of Array Except Self (Medium) Solved
- 2.1.14 (134) Gas Station (Medium) Medium
- 2.1.15 (135) Candy (Hard) Solved
- 2.1.16 (42) Trapping Rain Water (Hard) Complete
- 2.1.17 (13) Roman to Integer (Easy) Solved
- 2.1.18 (12) Integer to Roman (Medium) Solved
- 2.1.19 (58) Length of Last Word (Easy) Solved
- 2.1.20 (14) Longest Common Prefix (Easy) Solved
- 2.1.21 (151) Reverse Words in a String (Medium) Solved
- 2.1.22 (6) Zigzag Conversion (Medium) Completed
- 2.1.23 (28) Find the Index of the First Occurrence in a String (Easy) Completed
- 2.1.24 (68) Text Justification (Hard) Solved
- 2.2 Two Pointers
- 2.3 Sliding Window
- 2.4 Matrix
- 2.5 Hashmap
- 2.5.1 (383) Ransom Note (Easy) Solved
- 2.5.2 (205) Isomorphic Strings (Easy) Solved
- 2.5.3 (290) Word Pattern (Easy) Solved
- 2.5.4 (242) Valid Anagram (Easy) Solution
- 2.5.5 (49) Group Anagrams (Medium) Solved
- 2.5.6 (49) Two Sum (Easy) Solved
- 2.5.7 (202) Happy Number (Easy) Solved
- 2.5.8 (219) Contains Duplicate II (Easy) Solved
- 2.5.9 (128) Longest Consecutive Sequence (Medium) NOT SOLVED ❌
- 2.6 Intervals
- 2.7 Stack
- 2.8 Linked List
- 2.8.1 (141) Linked List Cycle (Easy) Solved
- 2.8.2 (2) Add Two Numbers (Medium) Solved
- 2.8.3 (21) Merge Two Sorted Lists (Easy) Solved
- 2.8.4 (138) Copy List with Random Pointer (Medium) NOT SOLVED ❌
- 2.8.5 (92) Reverse Linked List II (Medium) NOT SOLVED ❌
- 2.8.6 (25) Reverse Nodes in k-Group (Hard) NOT SOLVED ❌
- 2.8.7 (19) Remove Nth Node From End of List (Medium) Solved
- 2.8.8 (82) Remove Duplicates from Sorted List II (Medium) Solved
- 2.8.9 (61) Rotate List (Medium) Solved
- 2.8.10 (86) Partition List (Medium) NOT SOLVED ❌
- 2.8.11 (146) LRU Cache (Medium) Solved*
- 2.9 Binary Tree General
- 2.9.1 (104) Maximum Depth of Binary Tree (Easy) Solved
- 2.9.2 (100) Same Tree (Easy) Solved
- 2.9.3 (226) Invert Binary Tree (Easy) Solved
- 2.9.4 (101) Symmetric Tree (Easy) Solved
- 2.9.5 (105) Construct Binary Tree from Preorder and Inorder Traversal (Medium) NOT SOLVED ❌
- 2.9.6 (106) Construct Binary Tree from Inorder and Postorder Traversal (Medium) NOT SOLVED ❌
- 2.9.7 (117) Populating Next Right Pointers in Each Node II (Medium) NOT SOLVED ❌
- 2.9.8 (114) Flatten Binary Tree to Linked List (Medium) NOT SOLVED ❌
- 2.9.9 (112) Path Sum (Easy) Solved
- 2.9.10 (129) Sum Root to Leaf Numbers (Medium) Solved
- 2.9.11 (124) Binary Tree Maximum Path Sum (Hard) Solved
- 2.9.12 (173) Binary Search Tree Iterator (Medium) NOT SOLVED ❌
- 2.9.13 (222) Count Complete Tree Nodes (Easy) Solved
- 2.9.14 (236) Lowest Common Ancestor of a Binary Tree (Medium) Solved
- 2.10 Binary Tree BFS
- 2.11 Binary Search Tree
- 2.12 Graph General
- 2.13 Graph BFS
- 2.14 Trie
- 2.15 Backtracking
- 2.15.1 (17) Letter Combinations of a Phone Number (Medium) NOT SOLVED ❌
- 2.15.2 (77) Combinations (Medium) NOT SOLVED ❌
- 2.15.3 (46) Permutations (Medium) NOT SOLVED ❌
- 2.15.4 (39) Combination Sum (Medium) NOT SOLVED ❌
- 2.15.5 (52) N-Queens II (Hard) NOT SOLVED ❌
- 2.15.6 (22) Generate Parentheses (Medium) NOT SOLVED ❌
- 2.15.7 (79) Word Search (Medium) NOT SOLVED ❌
- 2.16 Divide & Conquer
- 2.17 Kadane's Algorithm
- 2.18 Binary Search
- 2.18.1 (35) Search Insert Position (Easy) Solved
- 2.18.2 (74) Search a 2D Matrix (Medium) Solved
- 2.18.3 (162) Find Peak Element (Medium) Solved
- 2.18.4 (33) Search in Rotated Sorted Array (Medium) NOT SOLVED ❌
- 2.18.5 (43) Find First and Last Position of Element in Sorted Array (Medium) NOT SOLVED ❌
- 2.18.6 (153) Find Minimum in https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150 Sorted Array (Medium) NOT SOLVED ❌
- 2.18.7 (4) Median of Two Sorted Arrays (Hard) NOT SOLVED ❌
- 2.19 Heap
- 2.20 Bit Manipulation
- 2.21 Math
- 2.22 1D DP
- 2.23 Multidimensional DP
- 2.23.1 (120) Triangle (Medium) NOT SOLVED ❌
- 2.23.2 (64) Minimum Path Sum (Medium) NOT SOLVED ❌
- 2.23.3 (63) Unique Paths II (Medium) NOT SOLVED ❌
- 2.23.4 (5) Longest Palindromic Substring (Medium) NOT SOLVED ❌
- 2.23.5 (97) Interleaving String (Medium) NOT SOLVED ❌
- 2.23.6 (72) Edit Distance (Medium) NOT SOLVED ❌
- 2.23.7 (123) Best Time to Buy and Sell Stock III (Hard) NOT SOLVED ❌
- 2.23.8 (188) Best Time to Buy and Sell Stock IV (Hard) NOT SOLVED ❌
- 2.23.9 (221) Maximal Square (Medium) NOT SOLVED ❌
- 2.1 Array / String
- 3 See Also
- 4 Links
About
LeetCode (leetcode.com) is a digital platform that specializes in delivering coding exercises and interview prep materials for software professionals and aspiring developers. It features a variety of coding problems and algorithmic challenges designed for hands-on coding practice. The platform has become a go-to resource for individuals preparing for technical interviews and participating in coding contests.
Their sets of problems are excellent and interactive - you code the solution in their UI and hit run to see if it passes test cases. On this page, I've typed out some solutions.
DISCLAIMER: I only had time to solve a few of the many problems, and not all will be optimal. If you want optimal I suggest you pay for a LeetCode subscription *or* simply ask ChatGPT and 9/10 it will produce an optimal working solution. I checked in some cases and even when I was close to optimal, ChatGPT inspired me to reduce code lines.
LeetCode Problem Set - Top Interview 150 - Solved in Python
These are the "Top Interview 150" questions with some answers. I think I finished about 55% of them (83/150) - maybe one day I'll get time and reason to finish the others.
Array / String
(88) Merge Sorted Array (Easy) Solved
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example:
- Input:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
- Output:
[1,2,2,3,5,6]
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
if m == 0 and n > 0:
for i, num2 in enumerate(nums2):
nums1[i] = num2
return
i = len(nums1) - 1 # End of nums1 where we move next biggest value.
i1 = m - 1
i2 = n - 1
while i >= 0:
# print('i=', i)
if i2 < 0:
return
if i1 < 0:
for x in range(0, i2 + 1):
nums1[x] = nums2[x]
return
if nums2[i2] >= nums1[i1]:
nums1[i] = nums2[i2]
i2 -= 1
else:
nums1[i] = nums1[i1]
i1 -= 1
i -= 1 |
(27) Remove Element (Easy) Solved
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums that are not equal to val.
Consider the number of elements in nums that are not equal to val be k, to get accepted, you need to do the following things:
- Change the array nums such that the first k elements of nums contain elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Example:
- Input:
nums = [3,2,2,3], val = 3
- Output:
2, nums = [2,2,_,_]
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = len(nums) - 1
end = i
while i >= 0:
curr_val = nums[i]
if curr_val == val:
if end != i:
# Swap:
nums[i], nums[end] = nums[end], nums[i]
end -= 1
nums.pop()
i -= 1 |
(26) Remove Duplicates from Sorted Array (Easy) Solved (+)
Given an integer array nums sorted in non-decreasing order, remove the duplicates in place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Example:
- Input:
nums = [1,1,2]
- Output:
output = [1,2,_]
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
unique_idx = 0
for i in range(1, len(nums)):
if nums[i] != nums[unique_idx]:
unique_idx += 1
if i != unique_idx:
nums[unique_idx] = nums[i]
nums = nums[0:unique_idx]
return unique_idx + 1 |
class Solution {
public:
// [1,2,2,3,3,3,4] -> [1,2,3,4]
// *
// [1,1,2] -> [1,2]
// ^
// unique_idx = 0; i = 0
int removeDuplicates(vector<int>& nums) {
int unique_idx = 0;
for(int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[unique_idx]) {
unique_idx++;
}
if (i != unique_idx) {
nums[unique_idx] = nums[i];
}
}
nums.resize(unique_idx + 1);
return unique_idx + 1;
}
}; |
(80) Remove Duplicates from Sorted Array II (Medium) Solved
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Example:
- Input:
nums = [1,1,1,2,2,3]
- Output:
5, nums = [1,1,2,2,3,_]
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <= 2:
return len(nums)
fixed_idx = 2 # Last index of corrected array.
for i in range(2, len(nums)):
if nums[i] == nums[fixed_idx-2]:
continue
else:
nums[fixed_idx] = nums[i]
fixed_idx += 1
return fixed_idx |
(169) Majority Element (Easy) Solved (+)
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example:
- Input:
nums = [3,2,3]
- Output:
3
class Solution(object):
def majorityElement(self, nums):
# Edge cases:
if len(nums) == 1:
return nums[0]
# Normal case:
nums.sort()
occurances = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
occurances += 1
if occurances >= len(nums) / 2:
return nums[i]
else:
occurance = 1
return -1 # No majority case |
# Boyer-Moore Voting Algorithm Trick:
# 1. Maintain a count of our current candidate for majority element.
# 2. Iterate through the list, and for each number:
# - If our count is 0: set current candidate to the current number.
# - If number is our current candidate: increment count.
# - If number is not current candidate: decrement count.
# 3. Given that a majority element exists in the array, our
# candidate will eventually be the majority element.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate, count = nums[0], 1
for num in nums[1:]:
if count == 0: # We have a new candidate.
candidate = num
count = 1
elif candidate == num:
count += 1
else:
count -= 1
return candidate |
(189) Rotate Array (Medium) Solved
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example:
- Input:
nums = [1,2,3,4,5,6,7], k = 3
- Output:
[5,6,7,1,2,3,4]
Uses a "reversing" trick.
void reverse_array_range(vector<int>& nums, int start, int end) {
int swap_range = (end + 1 - start) / 2;
for (int i = 0; i < swap_range; i++) {
std::swap(nums[start + i], nums[end - i]);
}
}
class Solution {
public:
// Example: nums = [1,2,3,4,5,6,7], k = 3 -> [5,6,7,1,2,3,4]
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
if (k == 0) {
return;
}
// Perform reversing trick:
reverse_array_range(nums, 0, n - 1);
reverse_array_range(nums, 0, k - 1);
reverse_array_range(nums, k, n - 1);
}
}; |
(121) Best Time to Buy and Sell Stock (Easy) Solved
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:
- Input:
prices = [7,1,5,3,6,4]
- Output:
5
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Buy lowest, sell highest.
curr_max = -sys.maxsize
curr_min = sys.maxsize
biggest_gain = -sys.maxsize
# prices = [7,1,5,3,6,4] -> 5 (6-1)
for price in prices:
if price < curr_min:
curr_min = price
curr_max = price
curr_max = max(curr_max, price)
biggest_gain = max(biggest_gain, curr_max - curr_min)
return biggest_gain |
(122) Best Time to Buy and Sell Stock II (Medium) Solved
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.
Example:
- Input:
prices = [7,1,5,3,6,4]
- Output:
7
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
# Buy low, sell high - always sell before a drop (easy).
total_profit = 0 # Running total profit.
for i in range(1, len(prices)):
profit = prices[i] - prices[i-1]
if profit > 0:
total_profit += profit
return total_profit |
(55) Jump Game (Medium) Solved
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:
- Input:
nums = [2,3,1,1,4]
- Output:
true
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums) == 0:
return False
if len(nums) == 1: # TODO(noske): Try remove.
return True
# [2,3,1,1,4] -> true. idx: 0 > 1 > last.
# [3,2,1,0,4] -> false. cannot get past idx 3.
reachable = [False] * len(nums)
reachable[0] = True
for i in range(len(nums)):
if not reachable[i]:
return False
jump = nums[i]
for j in range(i+1, i+1+jump):
# TODO: Optimize: should start from end return when true
# as app prior cells will already be true.
reachable[j] = True
if j == len(reachable) - 1:
return True
return reachable[len(reachable) - 1] |
(45) Jump Game II (Medium) Solved
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example:
- Input:
nums = [2,3,1,1,4]
- Output:
2
MAX_INT = 9000 # sys.maxsize
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
# [2,3,1,1,4] -> 2 .... from idx 0->1 ... 1->last
min_jumps = [MAX_INT] * len(nums)
min_jumps[0] = 0
for i in range(len(nums) - 1):
jump_range = nums[i]
new_min_jump = min_jumps[i] + 1
for j in range(i+1, min(i+1+jump_range, len(min_jumps))):
min_jumps[j] = min(min_jumps[j], new_min_jump)
return min_jumps[-1] |
# The problem can be solved more efficiently using a greedy algorithm.
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return 0
jumps = 0
current_jump_end = 0
farthest = 0
for i in range(n - 1): # We don't need to jump from the last position.
# Always try to jump as far as possible
farthest = max(farthest, i + nums[i])
# If we've come to the end of the current jump,
# increment our jump count and update our endpoint
if i == current_jump_end:
jumps += 1
current_jump_end = farthest
# If farthest has already reached or exceeded the last index
if farthest >= n - 1:
break
return jumps |
(274) H-Index (Medium) Solved
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
Example:
- Input:
citations = [3,0,6,1,5]
- Output:
3
class Solution:
def hIndex(self, citations: List[int]) -> int:
if not citations:
return 0
num_papers = len(citations)
citation_freq = [0] * (num_papers + 1)
for x in citations:
if x == 0:
continue
if x > num_papers:
x = num_papers
citation_freq[x] += 1
prev_freq = 0
for x in range(num_papers, -1, -1):
citation_freq[x] += prev_freq
if citation_freq[x] >= x:
return x
prev_freq = citation_freq[x]
return 0 |
To solve this problem in good runtime without extra storage, we can sort the citations array and then linearly search for the h-index. The idea is to leverage the sorted order to efficiently determine the number of papers that have at least i citations.
class Solution:
def hIndex(self, citations: List[int]) -> int:
citations.sort(reverse=True)
h = 0
for i, citation in enumerate(citations):
if citation >= i + 1:
h = i + 1
else:
break
return h |
(380) Insert Delete GetRandom O(1) (Medium) Solved
Implement the RandomizedSet class:
- RandomizedSet() Initializes the RandomizedSet object.
- bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
- bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
- int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
Example:
- Input:
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
- Output:
[null, true, false, true, 2, true, false, 2]
import random
class RandomizedSet:
def __init__(self):
self.my_set = set()
self.my_array = []
def insert(self, val: int) -> bool:
if val in self.my_set:
return False
self.my_set.add(val)
self.my_array.append(val)
return True
def remove(self, val: int) -> bool:
if not val in self.my_set:
return False
self.my_set.remove(val)
self.my_array.remove(val)
return True
def getRandom(self) -> int:
return random.choice(self.my_array)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom() |
(238) Product of Array Except Self (Medium) Solved
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example:
- Input:
nums = [-1,1,0,-3,3]
- Output:
[0,0,9,0,0]
Example:
- Input:
nums =[1,2,3,4]
- Output:
[24,12,8,6]
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
if not nums:
return []
new_array = [0] * len(nums)
# Calculate total product:
total_product = 1
num_zeros = 0
for num in nums:
if num != 0:
total_product *= num
else:
num_zeros += 1
if num_zeros > 1: # If two zeros, everything will be 0.
return new_array
for i, num in enumerate(nums):
if num == 0:
if num_zeros == 1: # For [1, 0, 3] case.
new_array[i] = total_product
else:
if num_zeros == 0: # For [1, 2, 3] case.
new_array[i] = int(total_product // num)
return new_array |
(134) Gas Station (Medium) Medium
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
Example:
- Input:
gas = [1,2,3,4,5], cost = [3,4,5,1,2]
- Output:
3
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# Sanity check:
if len(gas) != len(cost):
return -1
STATIONS = len(gas)
tank = 0
start_idx = 0
for i in range(STATIONS * 2):
if tank < 0: # Last section was net loss.
start_idx = i
tank = 0
tank += gas[i % STATIONS] - cost[i % STATIONS]
if i >= start_idx + STATIONS:
return (i % STATIONS)
return -1 |
(135) Candy (Hard) Solved
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.
Example:
- Input:
ratings = [1,0,2]
- Output:
5
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
# Every child should have at least one candy:
candies = [1] * n
# Traverse the ratings from left to right:
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# Traverse the ratings from right to left:
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
candies[i] = candies[i + 1] + 1
return sum(candies) |
(42) Trapping Rain Water (Hard) Complete
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example:
- Input:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
- Output:
6
# Spoiler... this approach is not optimal - it's overkill.
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n <= 2:
return 0
filled = [False] * n # If this block was filled over.
# 2D array with heights (to sort on) and x position (index in height).
sorted_heights = []
for x, y in enumerate(height):
sorted_heights.append((y, x))
# Create one version prioritizing furthest right blocks,
# and the other furthest left:
sorted_heights = sorted(sorted_heights, key = lambda x: (x[0], x[1]), reverse=True)
sorted_heights_left = sorted(sorted_heights, key = lambda x: (x[0], -x[1]), reverse=True)
# Print everything:
print(sorted_heights)
print(sorted_heights_left)
print(f'n = ${n}\nSOLUTION:')
# Start at the highest point and look to the right:
prev_y = sorted_heights[0][0]
prev_x = sorted_heights[0][1]
volume_filled = 0
for i in range(1, n):
y = sorted_heights[i][0]
x = sorted_heights[i][1]
if filled[x] == True: # Skip if block already filled.
continue
if x - prev_x >= 2: # Move to the right.
print(f'RIGHT SPAN ${prev_x}[${prev_y}] > ${x}[${y}]')
filled[x] = True
for idx in range(prev_x + 1, x):
plus = max(y - height[idx], 0)
volume_filled += plus
filled[idx] = True
print(f' - plus (${plus}) ${idx} [${height[idx]}] .... vol=${volume_filled}')
prev_y = y
prev_x = x
# Start again at highest points and look left:
prev_y = sorted_heights[0][0]
prev_x = sorted_heights[0][1] # Same starting point.
for i in range(0, n):
y = sorted_heights_left[i][0]
x = sorted_heights_left[i][1]
if filled[x] == True: # Skip if block already filled.
continue
if prev_x - x >= 2: # Move to the left.
print(f'LEFT SPAN ${prev_x}[${prev_y}] > ${x}[${y}]')
filled[x] = True
for idx in range(prev_x - 1, x, -1):
plus = max(y - height[idx], 0)
volume_filled += plus
print(f' - plus (${plus}) ${idx} [${height[idx]}] .... vol=${volume_filled}')
filled[idx] = True
prev_y = y
prev_x = x
return volume_filled |
# The faster two-pointer approach...
# This approach will take advantage of the fact that the water trapped
# at any position depends on the minimum of the highest bars on the left
# and right of that position.
#
# | _
# | _ | |_ _
# | _ | |# # #| | |#| |_
# | | |#| | |#| | | | | | |
# +-----------------------+
# height = [0,1,0,2,1,0,1,3,2,1,2,1] -> 6
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n = len(height)
left, right = 0, n - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if height[left] < height[right]:
left += 1
left_max = max(left_max, height[left])
water += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right]
return water |
(13) Roman to Integer (Easy) Solved
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
- Symbol Values:
I=1, V=5, X=10, L=50, C=100, D=500, M=1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- 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.
Example:
- Input:
s = "MCMXCIV"
- Output:
1994
class Solution:
def romanToInt(self, s: str) -> int:
roman_char_to_int = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
#. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
#. 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IIX', 'X'
#.
#. 'XXVII' -> 1+1+5+10+10 = 27
#. 'XDM' -> 1000-500-100 = 400
running_total = 0
ahead_val = 0 # Value of the char in front of the current.
for i in range(len(s) - 1, -1, -1): # Backwards order.
curr_char = s[i]
curr_val = roman_char_to_int[curr_char]
if ahead_val >= 0 and ahead_val > curr_val:
running_total -= curr_val
else:
running_total += curr_val
ahead_val = curr_val
return running_total |
def romanToInt(s):
roman_to_int = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
total = 0
prev_value = 0
for c in s: # Search forwards.
current_value = roman_to_int[c]
if current_value > prev_value:
total += current_value - 2 * prev_value # Subtract previous value twice because it was added before.
else:
total += current_value
prev_value = current_value
return total |
(12) Integer to Roman (Medium) Solved
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
- Symbol Value
- I 1
- V 5
- X 10
- L 50
- C 100
- D 500
- M 1000
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- 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 an integer, convert it to a roman numeral.
Example:
- Input:
num = 1994
- Output:
"MCMXCIV"
class Solution:
def intToRoman(self, num: int) -> str:
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
roman = ""
for i in range(len(values)):
while num >= values[i]:
roman += symbols[i]
num -= values[i]
return roman |
ROMAN_VALUES = [
'I', # 1.
'V', # 5.
'X', # 10.
'L', # 50.
'C', # 100.
'D', # 500.
'M', # 1000.
'-', '-'
]
def get_roman_char(remainder: int, base_10: int) -> str:
base_10_offset = base_10 * 2
roman_1 = ROMAN_VALUES[base_10_offset]
roman_5 = ROMAN_VALUES[base_10_offset + 1]
roman_10 = ROMAN_VALUES[base_10_offset + 2]
if remainder == 0:
return ''
if remainder == 1:
return roman_1
elif remainder == 2:
return roman_1 + roman_1
elif remainder == 3:
return roman_1 + roman_1 + roman_1
elif remainder == 4:
return roman_1 + roman_5
if remainder == 5:
return roman_5
elif remainder == 6:
return roman_5 + roman_1
elif remainder == 7:
return roman_5 + roman_1 + roman_1
elif remainder == 8:
return roman_5 + roman_1 + roman_1 + roman_1
elif remainder == 9:
return roman_1 + roman_10
class Solution:
def intToRoman(self, num: int) -> str:
roman = ''
base_10 = 0
while num > 0:
remainder = num % 10
roman = get_roman_char(remainder, base_10) + roman
num = int((num - remainder) / 10)
base_10 += 1
return roman |
(58) Length of Last Word (Easy) Solved
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.
Example:
- Input:
"luffy is still joyboy"
- Output:
6
class Solution:
def lengthOfLastWord(self, s: str) -> int:
last_non_digit_idx = -1
i = len(s) - 1
while i >= 0:
if s[i] == ' ':
if last_non_digit_idx > -1:
return last_non_digit_idx - i
elif last_non_digit_idx == -1:
last_non_digit_idx = i
i -= 1
return last_non_digit_idx + 1 # If -1 returns 0. |
It might defeat the purpose of the exercise, but turns out this is run faster using some build-in string functions in a single line of code...
class Solution:
def lengthOfLastWord(self, s: str) -> int:
return len(s.rstrip().split(' ')[-1]) |
(14) Longest Common Prefix (Easy) Solved
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 ("").
Example:
- Input:
strs = ["flower","flow","flight"]
- Output:
"fl"
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ''
i = 0
while True:
letter = ''
for word in strs:
if i >= len(word):
return word
if letter == '':
letter = word[i]
elif word[i] != letter:
return word[:i]
i += 1
return '' |
(151) Reverse Words in a String (Medium) Solved
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example:
- Input:
s = "a good example"
- Output:
"example good a"
class Solution:
def reverseWords(self, s: str) -> str:
new_words = []
end_word = -1 # Index for the end of a word... -1 means not found.
for i in range(len(s) - 1, -1, -1): # Search backwards.
letter = s[i]
if end_word == -1: # If end of word not found:
if letter != ' ': # Non-space means:
end_word = i # End of word found.
else: # Else:
if letter == ' ': # Space means: add new word
new_words.append(s[i+1:end_word+1])
end_word = -1
if end_word >= 0:
new_words.append(s[0:end_word+1])
return ' '.join(new_words)
# LESS CODE, MORE SPACE:
# words = s.split(' ')
# final_words = []
# for i in range(len(words) - 1, -1, -1):
# word = words[i]
# if word != '':
# final_words.append(word)
# return ' '.join(final_words) |
(6) Zigzag Conversion (Medium) Completed
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows);
Example:
- Input:
s = "PAYPALISHIRING", numRows = 3
- Output:
"PAHNAPLSIIGYIR"
# When we visualize the zigzag pattern
#
# 01234567890123
# * * * --> PINalsigYAHRPI
# * * * * *
# * * * *
# * *
# PaYPAlIsHIRiNg
#
# We realize that each "zig" or "zag" has a length of numRows + (numRows - 2).
# With this we can place characters in their appropriate position.
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or len(s) <= numRows:
return s
# Initialize rows:
rows = [''] * numRows
curRow = 0
direction = -1
for char in s:
rows[curRow] += char
# Change direction if at the top or bottom:
if curRow == 0 or curRow == numRows - 1:
direction *= -1
curRow += direction
return ''.join(rows) |
(28) Find the Index of the First Occurrence in a String (Easy) Completed
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example:
- Input:
haystack = "sadbutsad", needle = "sad"
- Output:
0
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# Easy/cheat solution:
# return haystack.find(needle)
# Loop solution:
for i in range(len(haystack) - len(needle) + 1):
for j in range(len(needle)):
if haystack[i + j] != needle[j]:
break
if j >= len(needle) - 1:
return i
return -1 |
(68) Text Justification (Hard) Solved
Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed maxWidth. The input array words contain at least one word.
Example:
- Input:
words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
- Output:
[ "This is an", "example of text", "justification. "]
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
result = [] # Result to return (array of lines).
current = [] # Words for the next line.
num_of_letters = 0 # Total letters in line so far.
for word in words:
if num_of_letters + len(word) + len(current) > maxWidth:
for i in range(maxWidth - num_of_letters):
current[i % (len(current) - 1 or 1)] += ' '
result.append(''.join(current))
current = []
num_of_letters = 0
current += [word]
num_of_letters += len(word)
result.append(' '.join(current).ljust(maxWidth, ' '))
return result |
Two Pointers
(125) Valid Palindrome (Easy) Solved
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:
- Input:
s = "A man, a plan, a canal: Panama"
- Output:
true
def is_letter(x: str) -> bool:
# It is faster to use python's built-in "isalnum()",
# but I just wanted to show how to do it in code.
return (
('a' <= x <= 'z') or # I've used chained comparisons (x < y < z).
('A' <= x <= 'Z') or
('0' <= x <= '9'))
class Solution:
def isPalindrome(self, s: str) -> bool:
i = 0
j = len(s) - 1
while i < j:
if not is_letter(s[i]):
i += 1
continue
if not is_letter(s[j]):
j -= 1
continue
# Both are letters:
elif s[i].upper() == s[j].upper():
i += 1
j -= 1
else:
return False
return True |
(392) Is Subsequence (Easy) Solved
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
Example:
- Input:
s = "abc", t = "ahbgdc"
- Output:
true
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0:
return True
i = 0
j = 0
while i < len(t):
if t[i] == s[j]:
j += 1
if j >= len(s):
return True
i += 1
return False |
(167) Two Sum II - Input Array Is Sorted (Medium) Solved
Given a 1-indexed array of integer numbers that are already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.
Return the indices of the two numbers, index1, and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example:
- Input:
numbers = [2,7,11,15], target = 9
- Output:
[1,2]
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # One indexed.
elif current_sum < target:
left += 1
else:
right -= 1
return [] |
(11) Container With Most Water (Medium) Solved
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:
- Input:
height = [1,8,6,2,5,4,8,3,7]
- Output:
49
class Solution:
def maxArea(self, height: List[int]) -> int:
if not height:
return 0
l, r = 0, len(height) - 1
max_area = 0
while l < r:
area = (r - l) * min(height[l], height[r])
max_area = max(max_area, area)
if height[l] < height[r]:
l += 1
else:
r -= 1
return max_area |
(15) 3Sum (Medium) Solved
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:
- Input:
nums = [-1,0,1,2,-1,-4]
- Output:
[[-1,-1,2],[-1,0,1]]
class Solution(object):
def threeSum(self, nums):
if not nums:
return []
nums.sort()
results = []
for i in range(0, len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # Skip duplicates for i.
continue
# Two pointer search inwards to find any pairs that sum with i to give 0.
l, r = i + 1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
# If the sum is zero, add the triplet.
if total == 0:
results.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: # Skip duplicates for l.
l += 1
while l < r and nums[r] == nums[r-1]: # Skip duplicates for r.
r -= 1
l += 1
r -= 1
elif total < 0:
l += 1
else:
r -= 1
return results |
Sliding Window
(209) Minimum Size Subarray Sum (Medium) Solved
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to the target. If there is no such subarray, return 0 instead.
Example:
- Input:
target = 7, nums = [2,3,1,2,4,3]
- Output:
2
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if not nums:
return 0
i, j = 0, 0 # Sliding window
total = 0
min_length = float('inf')
while j < len(nums):
total += nums[j]
while total >= target:
min_length = min(min_length, j - i + 1)
total -= nums[i]
i += 1
j += 1
return min_length if min_length < float('inf') else 0 |
(3) Longest Substring Without Repeating Characters (Medium) Solved
Given a string s, find the length of the longest substring without repeating characters.
Example:
- Input:
s = "abcabcbb"
- Output:
3
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
unique_chars = set()
i, j = 0, 0 # Sliding window (start and end idx).
max_unique_len = 0
while j < len(s):
char = s[j]
if char in unique_chars:
unique_chars.remove(s[i])
i += 1
else:
max_unique_len = max(max_unique_len, j - i + 1)
unique_chars.add(char)
j += 1
return max_unique_len |
(30) Substring with Concatenation of All Words (Hard) NOT SOLVED ❌
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated substring in s' is a substring that contains all the strings of any permutation of words concatenated.
For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example:
- Input:
s = "barfoothefoobarman", words = ["foo","bar"]
- Output:
[0,9]
(76) Minimum Window Substring (Hard) NOT SOLVED ❌
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 "".
The testcases will be generated such that the answer is unique.
Example:
- Input:
s = "ADOBECODEBANC", t = "ABC"
- Output:
"BANC"
Matrix
(36) Valid Sudoku (Medium) Solved
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.
Example:
- Input:
board = \
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
- Output:
true
SIDE = 9
BOX_SIDE = 3
BOXES_PER_SIDE = 3
def cell(board: List[List[str]], x:int, y:int):
return board[y][x]
def value_already_appears(val: str, occurrences: list[int]) -> bool:
if val == '.':
return False
idx: int = ord(val) - ord('1')
if occurrences[idx] >= 1:
return True
else:
occurrences[idx] = 1
return False
def reset_occurrences(occurrences: list[int]) -> None:
for i in range (len(occurrences)):
occurrences[i] = 0
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
occurrences: list[int] = [0] * SIDE
# For each column:
for x in range(SIDE):
reset_occurrences(occurrences)
for y in range(SIDE):
if value_already_appears(cell(board, x, y), occurrences):
return False
# For each row:
for y in range(SIDE):
reset_occurrences(occurrences)
for x in range(SIDE):
if value_already_appears(cell(board, x, y), occurrences):
return False
# For each box:
for x_box in range(BOXES_PER_SIDE):
for y_box in range(BOXES_PER_SIDE):
reset_occurrences(occurrences)
for x_offset in range(BOX_SIDE):
for y_offset in range(BOX_SIDE):
x = x_box * BOX_SIDE + x_offset
y = y_box * BOX_SIDE + y_offset
if value_already_appears(cell(board, x, y), occurrences):
return False
return True |
(54) Spiral Matrix (Medium) Solved
Given an m x n matrix, return all elements of the matrix in spiral order.
Example:
- Input:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
- Output:
[1,2,3,6,9,8,7,4,5]
NUM_DIRECTIONS = 4
def is_inside(x:int, y:int, x_min:int,
y_min:int, x_max:int, y_max:int) -> bool:
return (x_min < x < x_max) and (y_min < y < y_max)
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
"""Return items in a clockwise spiral, starting at 0,0."""
if not matrix or len(matrix) == 0:
return []
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
x_min = -1
y_min = -1
x_max = WIDTH
y_max = HEIGHT
curr_direction = 0
spiral = []
idx = [0, 0] # Current position.
new_cell = True
while True:
# Append cells to spiral (if new):
x = idx[0] # Looking for new position.
y = idx[1] # Looking for new position.
if new_cell:
spiral.append(matrix[y][x])
new_cell = False
# Progress forwards:
if curr_direction == 0: # Left.
x += 1
if curr_direction == 1: # Down.
y += 1
if curr_direction == 2: # Right.
x -= 1
if curr_direction == 3: # Up.
y -= 1
# Check if new cell is inside:
inside = is_inside(x, y, x_min, y_min, x_max, y_max)
# Advance to this new cell, else change directions:
if inside:
idx = [x, y]
new_cell = True
else:
if curr_direction == 0: # Left. -> y_min += 1
y_min += 1
if curr_direction == 1: # Down. -> x_max -= 1
x_max -= 1
if curr_direction == 2: # Right. -> y_max -= 1
y_max -= 1
if curr_direction == 3: # Up. -> x_min += 1
x_min += 1
curr_direction = (curr_direction + 1) % NUM_DIRECTIONS
if y_min >= y_max -1 and x_min >= x_max - 1:
break
return spiral |
A variation where we go all the way along each direction with a separate loop.
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
"""Return items in a clockwise spiral, starting at 0,0."""
if not matrix or len(matrix) == 0:
return []
m, n = len(matrix), len(matrix[0])
top, bottom, left, right = 0, m-1, 0, n-1
result = []
while left <= right and top <= bottom:
# Traverse left to right:
for j in range(left, right+1):
result.append(matrix[top][j])
top += 1
# Traverse top to bottom:
for i in range(top, bottom+1):
result.append(matrix[i][right])
right -= 1
# Traverse right to left (ensure top is not greater than bottom):
if top <= bottom:
for j in range(right, left-1, -1):
result.append(matrix[bottom][j])
bottom -= 1
# Traverse bottom to top (ensure left is not greater than right):
if left <= right:
for i in range(bottom, top-1, -1):
result.append(matrix[i][left])
left += 1
return result |
(48) Rotate Image (Medium) Solved
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:
- Input:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
- Output:
[[7,4,1],[8,5,2],[9,6,3]]
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
if not matrix or len(matrix) == 0:
return
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
# Part that repeats (bit to rotate):
HALF_WIDTH = int((WIDTH + 1) / 2)
HALF_HEIGHT = int((HEIGHT) / 2)
for y in range (HALF_HEIGHT):
for x in range (HALF_WIDTH):
x_max = WIDTH - x - 1
y_max = HEIGHT - y - 1
matrix[y][x], matrix[x][y_max], matrix[y_max][x_max], matrix[x_max][y] = (
matrix[x_max][y], matrix[y][x], matrix[x][y_max], matrix[y_max][x_max]
) |
(73) Set Matrix Zeroes (Medium) Solved
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:
- Input:
matrix = [[1,1,1],[1,0,1],[1,1,1]]
- Output:
[[1,0,1],[0,0,0],[1,0,1]]
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
if not matrix:
return
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
cols_to_zero = set()
rows_to_zero = set()
# If row is zeroed out > we can break.
for y in range(HEIGHT):
for x in range(WIDTH):
if matrix[y][x] == 0:
cols_to_zero.add(x)
rows_to_zero.add(y)
for x in cols_to_zero:
for y in range(HEIGHT):
matrix[y][x] = 0
for y in rows_to_zero:
for x in range(WIDTH):
matrix[y][x] = 0 |
(289) Game of Life (Medium) Solved
According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Any live cell with fewer than two live neighbors dies as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
Example:
- Input:
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
- Output:
[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
def num_living_neighbors(board: list[list[int]], x: int, y: int, w: int, h: int) -> int:
living = 0
for y_offset in range(max(0, y-1), min(y+1, h - 1)+1):
for x_offset in range(max(0, x-1), min(x+1, w - 1)+1):
# print(' ', x_offset, y_offset)
if board[y_offset][x_offset] % 2 == 1:
if (y_offset != y or x_offset != x):
living += 1
return living
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
if not board or len(board) == 0:
return
HEIGHT = len(board)
WIDTH = len(board[0])
# Determine changes:
# KEY:
# 0 = was dead > stay dead.
# 1 = was live > stay live.
# 2 = was dead > now LIVE.
# 3 = was live > now DEAD.
for y in range (HEIGHT):
for x in range (WIDTH):
live = board[y][x]
living_neighbors = num_living_neighbors(board, x, y, WIDTH, HEIGHT)
if live:
if living_neighbors < 2: # Under-population.
board[y][x] = 3 # Dies.
elif living_neighbors > 3: # Over-population.
board[y][x] = 3 # Dies.
# else:
# board[y][x] = 1 # Stay alive.
else:
if living_neighbors == 3: # Repoduction.
board[y][x] = 2 # Ressurected.
# Apply changes:
for y in range (HEIGHT):
for x in range (WIDTH):
if board[y][x] >= 2:
board[y][x] = (board[y][x] + 1) % 2 |
Hashmap
(383) Ransom Note (Easy) Solved
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in the magazine can only be used once in ransomNote.
Example:
- Input:
ransomNote = "aa", magazine = "aab"
- Output:
true
def create_letter_freq_dict(text: str) -> dict[str,int]:
freq = {}
for letter in text:
if letter not in freq:
freq[letter] = 0
freq[letter] += 1
return freq
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
randsome_freq = create_letter_freq_dict(ransomNote)
magazine_freq = create_letter_freq_dict(magazine)
# TODO(noske): Actually we could just iterate magazine and
# subtract from `randsome_freq` with each new letter needed.
for letter, freq in randsome_freq.items():
if letter not in magazine_freq:
return False
if magazine_freq[letter] < freq:
return False
return True |
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# Create a dictionary to store occurrence counts of characters in magazine
mag_char_count = {}
for char in magazine:
mag_char_count[char] = mag_char_count.get(char, 0) + 1
# Check if ransom note can be constructed from the magazine
for char in ransomNote:
# If char not in magazine or its count has exhausted, return False
if char not in mag_char_count or mag_char_count[char] == 0:
return False
mag_char_count[char] -= 1
return True |
(205) Isomorphic Strings (Easy) Solved
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
Example:
- Input:
s = "egg", t = "add"
- Output:
true
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_to_t_mapping = {}
t_to_s_mapping = {}
for s_letter, t_letter in zip(s, t): # NOTE: zip is a special operator.
if s_letter in s_to_t_mapping:
if s_to_t_mapping[s_letter] != t_letter:
return False
else:
s_to_t_mapping[s_letter] = t_letter
if t_letter in t_to_s_mapping:
if t_to_s_mapping[t_letter] != s_letter:
return False
else:
t_to_s_mapping[t_letter] = s_letter
return True |
(290) Word Pattern (Easy) Solved
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
Example:
- Input:
pattern = "aaaa", s = "dog cat cat dog"
- Output:
false
# pattern = "abba", s = "dog cat cat dog" -> True
#
# PSUEDO:
# Break apart s: [dog, cat, cat, dog]
# Iterate both arrays and
# create dict for pattern to s: { a:'dog', b:'cat' }
# > if contradicts, then return false.
#
# Create dict for both arrays {'dog': 0, 'cat': 1}
# resolve to array: [0,1,1,0]
# Check both arrays are equal.
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split()
if len(words) != len(pattern):
return False
letter_map = {}
word_map = {}
for i in range(len(words)):
word = words[i]
letter = pattern[i]
if letter in letter_map:
if letter_map[letter] != word:
return False
else:
letter_map[letter] = word
if word in word_map:
if word_map[word] != letter:
return False
else:
word_map[word] = letter
return True |
(242) Valid Anagram (Easy) Solution
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:
- Input:
s = "anagram", t = "nagaram"
- Output:
true
def get_char_frequency(s: str) -> dict:
"""Return a dictionary representing the frequency of characters in the string."""
char_count = {}
for char in s:
char_count[char] = char_count.get(char, 0) + 1
return char_count
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
return get_char_frequency(s) == get_char_frequency(t) |
from collections import Counter
class Solution:
def isAnagram(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
# Testing the function with given examples:
print(isAnagram("anagram", "nagaram")) # Output: True
print(isAnagram("rat", "car")) # Output: False |
(49) Group Anagrams (Medium) Solved
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:
- Input:
strs = ["eat","tea","tan","ate","nat","bat"]
- Output:
[["bat"],["nat","tan"],["ate","eat","tea"]]
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
sorted_strs = {}
for i, word in enumerate(strs):
chars = []
for l in word:
chars.append(l)
chars.sort()
sorted_str = ''.join(chars)
if not sorted_str in sorted_strs:
sorted_strs[sorted_str] = []
sorted_strs[sorted_str].append(word)
# print(sorted_strs)
result = []
for _, words_arr in sorted_strs.items():
result.append(words_arr)
return result |
(49) Two Sum (Easy) Solved
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:
- Input:
strs = ["eat","tea","tan","ate","nat","bat"]
- Output:
[["bat"],["nat","tan"],["ate","eat","tea"]]
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
sorted_strs = {}
for i, word in enumerate(strs):
chars = []
for l in word:
chars.append(l)
chars.sort()
sorted_str = ''.join(chars)
if not sorted_str in sorted_strs:
sorted_strs[sorted_str] = []
sorted_strs[sorted_str].append(word)
# print(sorted_strs)
result = []
for _, words_arr in sorted_strs.items():
result.append(words_arr)
return result |
(202) Happy Number (Easy) Solved
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.
Example:
- Input:
n = 19
- Output:
true # Explanation: 1^2 + 9^2 = 82, 8^2 + 2^2 = 68, 6^2 + 8^2 = 100, 1^2 + 0^2 + 0^2 = 1
MAX_ITERATIONS = 100
def num_to_digit_array(n: int) -> list[int]:
arr = []
while n > 0:
last_digit = n % 10
n = int(n / 10)
arr.append(last_digit)
arr.reverse()
return arr
def sum_of_squares(arr: list[int]) -> int:
total = 0
for x in arr:
total += x * x
return total
class Solution:
def isHappy(self, n: int) -> bool:
first_square = 0
for i in range(MAX_ITERATIONS):
arr = num_to_digit_array(n)
n = sum_of_squares(arr)
if n == 1: # Exit if 1 (happy number found).
return True
if first_square == 0: # Set first square just once.
first_square = n
elif n == first_square: # Exit if looped back to first square.
return False
return False |
We could also use the Floyd's cycle-finding algorithm (also known as the "tortoise and the hare" algorithm) to detect if there's a cycle. The idea is to transform the number repeatedly using the rule given, and do this transformation at two speeds - one "fast" and one "slow". If there's a cycle (i.e., the number isn't happy), the two speeds will eventually produce the same number. While checking the sum of squares of digits, if we ever encounter the number 1, it's a happy number. Here's how you can implement it:
def get_next(n):
"""Get the next number according to the rule."""
total_sum = 0
while n > 0:
n, digit = divmod(n, 10)
total_sum += digit ** 2
return total_sum
class Solution(object):
def isHappy(self, n):
# Using Floyd's Cycle-Finding Algorithm
slow, fast = n, get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1
# Testing the function with given examples:
# print(isHappy(19)) # Output: True
# print(isHappy(2)) # Output: False |
(219) Contains Duplicate II (Easy) Solved
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example:
- Input:
nums = [1,2,3,1], k = 3
- Output:
true
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
num_to_max_idx = {} # A map of number values to the max index.
for i, num in enumerate(nums):
if num in num_to_max_idx:
if abs(i - num_to_max_idx[num]) <= k:
return True
num_to_max_idx[num] = i
return False |
(128) Longest Consecutive Sequence (Medium) NOT SOLVED ❌
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:
- 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.
Intervals
(228) Summary Ranges (Easy) Solved
You are given a sorted unique integer array nums.
A range [a,b] is the set of all integers from a to b (inclusive).
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
Each range [a,b] in the list should be output as:
- "a->b" if a != b
- "a" if a == b
Example:
- Input:
nums = [0,1,2,4,5,7]
- Output:
["0->2","4->5","7"] # The ranges are: [0,2] --> "0->2"
def range_to_string(start: int, end: int) -> str:
if start == end:
return str(start)
else:
return str(start) + '->' + str(end)
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
if not nums or len(nums) == 0:
return []
arr = []
start_idx = 0
i = 0
while True:
i += 1
if i >= len(nums):
arr.append(range_to_string(nums[start_idx], nums[i - 1]))
break
if nums[i] != nums[i-1] + 1:
arr.append(range_to_string(nums[start_idx], nums[i - 1]))
start_idx = i
return arr |
(56) Merge Intervals (Medium) Solved
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example:
- Input:
intervals = [[1,3],[2,6],[8,10],[15,18]]
- Output:
[[1,6],[8,10],[15,18]] # Since intervals [1,3] and [2,6] overlap, merge them into [1,6]
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
if len(intervals) == 1:
return intervals
print('intervals=', intervals)
intervals = sorted(intervals, key=lambda interval: interval[0])
print('AFTER SORTING=', intervals)
results = [intervals[0]] # Stack.
for i in range(1, len(intervals)):
if results[-1][1] >= intervals[i][0]:
if results[-1][1] < intervals[i][1]:
results[-1][1] = intervals[i][1]
else:
results.append(intervals[i])
return(results) |
(57) Insert Interval (Medium) Solved
You are given an array of non-overlapping intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. 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 starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Example:
- Input:
intervals = [[1,3],[6,9]], newInterval = [2,5]
- Output:
[[1,5],[6,9]]
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
result = []
for interval in intervals:
# If current interval is completely before newInterval:
if interval[1] < newInterval[0]:
result.append(interval)
# If current interval is completely after newInterval:
elif interval[0] > newInterval[1]:
result.append(newInterval)
newInterval = interval # Replace to mean next interval.
# If there's an overlap:
else:
newInterval[0] = min(newInterval[0], interval[0])
newInterval[1] = max(newInterval[1], interval[1])
result.append(newInterval)
return result |
(452) Minimum Number of Arrows to Burst Balloons (Medium) Solved
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
Example:
- Input:
points = [[10,16],[2,8],[1,6],[7,12]]
- Output:
2
Stack
(20) Valid Parentheses (Easy) Solved
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.
Example:
- Input:
s = "()[]{}"
- Output:
true # But would be false for anything like: "(]".
class Solution:
def isValid(self, s: str) -> bool:
# '()[]{}' -> true
bracket_matches = {
')': '(',
']': '[',
'}': '{',
} # Note: Try chr(ord(bracket) - 1) > does not work for all these.
brackets_stack = []
for bracket in s:
if bracket in bracket_matches:
bracket_match = bracket_matches[bracket]
if not brackets_stack or brackets_stack.pop() != bracket_match:
return False
else:
brackets_stack.append(bracket)
return len(brackets_stack) == 0 |
(71) Simplify Path (Medium) Solved
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.
Example:
- Input:
path = "/home//foo/"
- Output:
"/home/foo" # In the canonical path, multiple consecutive slashes are replaced by a single one.
class Solution:
def simplifyPath(self, path: str) -> str:
folders = path.split('/')
final_folders = []
for folder in folders:
if folder == '..':
if len(final_folders) > 0:
final_folders.pop()
elif folder == '.' or folder == '':
continue
else:
final_folders.append(folder)
return '/' + '/'.join(final_folders) |
(155) Min Stack (Medium) ) SolvedSolved*
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
- MinStack() initializes the stack object.
- void push(int val) pushes the element val onto the stack.
- void pop() removes the element on the top of the stack.
- int top() gets the top element of the stack.
- int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example:
- Input:
["MinStack","push","push","push","getMin","pop","top","getMin"] ... [[],[-2],[0],[-3],[],[],[],[]]
- Output:
[null,null,null,null,-3,null,0,-2]
class MinStack:
def __init__(self):
self.mainStack = [] # To store all the elements.
self.minStack = [] # To keep track of the minimum at each state.
def push(self, val: int) -> None:
self.mainStack.append(val)
# If the minStack is empty or the current value is less than or
# equal to the top of minStack, push the current value onto minStack
if not self.minStack or val <= self.minStack[-1]:
self.minStack.append(val)
def pop(self) -> None:
if not self.mainStack:
return
# If the top of mainStack is equal to the top of minStack,
# pop from minStack as well.
if self.mainStack[-1] == self.minStack[-1]:
self.minStack.pop()
self.mainStack.pop()
def top(self) -> int:
if not self.mainStack:
return -1
return self.mainStack[-1]
def getMin(self) -> int:
if not self.minStack:
return -1
return self.minStack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin() |
(150) Evaluate Reverse Polish Notation (Medium) NOT SOLVED ❌
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
- The valid operators are '+', '-', '*', and '/'.
- Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
Example:
- Input:
tokens = ["2","1","+","3","*"]
- Output:
9 # Explanation: ((2 + 1) * 3) = 9
(224) Basic Calculator (Hard) NOT SOLVED ❌
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function that evaluates strings as mathematical expressions, such as eval().
Example:
- Input:
s = "(1+(4+5+2)-3)+(6+8)"
- Output:
23
Linked List
(141) Linked List Cycle (Easy) Solved
Given head, the head of a linked list, determines 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 the 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:
- 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).
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head == None:
return False
prev_nodes_set = set()
n = head
while n.next:
prev_nodes_set.add(n)
n = n.next
if n in prev_nodes_set:
return True
return False |
(2) Add Two Numbers (Medium) Solved
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
- Input:
l1 = [2,4,3], l2 = [5,6,4]
- Output:
[7,0,8]. # Explanation: 342 + 465 = 807.
def get_value(n: Optional[ListNode]) -> int:
if n == None:
return None
return n.val
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
new_list_head = None
prev_node = None
carry_over = 0
while l1 or l2 or carry_over:
next_digit = carry_over
if l1:
next_digit += l1.val
l1 = l1.next
if l2:
next_digit += l2.val
l2 = l2.next
carry_over = next_digit // 10
next_digit = next_digit % 10
new_node = ListNode(next_digit)
if not new_list_head:
new_list_head = new_node
else:
prev_node.next = new_node
prev_node = new_node
return new_list_head |
(21) Merge Two Sorted Lists (Easy) Solved
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:
- Input:
list1 = [1,2,4], list2 = [1,3,4]
- Output:
[1,1,2,3,4,4]
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode],
list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1 and not list2:
return None
l1 = list1
l2 = list2
new_list_head = None
new_node = None
pre_node = None
while l1 or l2:
if not l1:
new_node = ListNode(l2.val)
l2 = l2.next
elif not l2:
new_node = ListNode(l1.val)
l1 = l1.next
elif l1.val < l2.val:
new_node = ListNode(l1.val)
l1 = l1.next
else:
new_node = ListNode(l2.val)
l2 = l2.next
if new_list_head == None:
new_list_head = new_node
else:
prev_node.next = new_node
prev_node = new_node
return new_list_head |
(138) Copy List with Random Pointer (Medium) NOT SOLVED ❌
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
Example:
- Input:
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
- Output:
[[7,null],[13,0],[11,4],[10,2],[1,0]]
(92) Reverse Linked List II (Medium) NOT SOLVED ❌
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Example:
- Input:
head = [1,2,3,4,5], left = 2, right = 4
- Output:
[1,4,3,2,5]
(25) Reverse Nodes in k-Group (Hard) NOT SOLVED ❌
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example:
- Input:
head = [1,2,3,4,5], k = 2
- Output:
[2,1,4,3,5]
(19) Remove Nth Node From End of List (Medium) Solved
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example:
- Input:
head = [1,2,3,4,5], n = 2
- Output:
[1,2,3,5]
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if head is None:
return head
# Create a dummy node that precedes the head.
dummy = ListNode(-1)
dummy.next = head
first = dummy # To move "n" spots ahead of "second".
second = dummy
for _ in range(n + 1):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next |
(82) Remove Duplicates from Sorted List II (Medium) Solved
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example:
- Input:
head = [1,2,3,3,4,4,5]
- Output:
[1,2,5]
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-999) # Value that doesn't match first element.
dummy.next = head
prev = dummy
current = head
while current:
# Check if current node is the start of a sequence of duplicates:
if current.next and current.val == current.next.val:
# Skip all the duplicates:
while current.next and current.val == current.next.val:
current = current.next
# After skipping all duplicates, link previous node to the next distinct node.
prev.next = current.next
else:
prev = current
current = current.next
return dummy.next |
(61) Rotate List (Medium) Solved
Given the head of a linked list, rotate the list to the right by k places.
Example:
- Input:
head = [1,2,3,4,5], k = 2
- Output:
[4,5,1,2,3]
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None or k == 0:
return head
# Detemine length:
end_node = head
length = 1
while end_node.next:
end_node = end_node.next
length += 1
new_start_idx = length - (k % length)
end_node.next = head # Make it loop.
# Locate new end node:
new_end_node = head
for _ in range(new_start_idx - 1):
new_end_node = new_end_node.next
new_head = new_end_node.next
new_end_node.next = None
return new_head |
(86) Partition List (Medium) NOT SOLVED ❌
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
- Input:
head = [1,4,3,2,5,2], x = 3
- Output:
[1,2,2,4,3,5]
(146) LRU Cache (Medium) Solved*
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example:
- Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
- Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]
class ListNode:
# Double linked.
def __init__(self, key=0, val=0, prev=None, next=None):
self.key = key
self.val = val
self.prev = prev
self.next = next
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.d = {}
self.head = None
self.tail = None
def _remove(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
def _add_to_tail(self, node):
if self.tail:
self.tail.next = node
node.prev = self.tail
node.next = None
self.tail = node
else:
self.head = self.tail = node
def get(self, key: int) -> int:
if key not in self.d:
return -1
node = self.d[key]
self._remove(node)
self._add_to_tail(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.d:
self._remove(self.d[key])
node = ListNode(key, value)
self._add_to_tail(node)
self.d[key] = node
if len(self.d) > self.capacity:
to_remove = self.head
self._remove(to_remove)
del self.d[to_remove.key]
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value) |
Binary Tree General
(104) Maximum Depth of Binary Tree (Easy) Solved
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:
- Input:
root = [3,9,20,null,null,15,7]
- Output:
3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def max_depth(n: TreeNode) -> int:
"""Return max depth."""
if n == None:
return 0
left_depth = max_depth(n.left) + 1
right_depth = max_depth(n.right) + 1
return max(left_depth, right_depth)
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
return max_depth(root) |
(100) Same Tree (Easy) Solved
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:
- Input:
p = [1,2,3], q = [1,2,3]
- Output:
true
def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
if p == None and q == None:
return True
if p == None or q == None:
return False
if p.val != q.val:
return False
return (is_same_tree(p.left, q.left) and
is_same_tree(p.right, q.right))
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return is_same_tree(p, q) |
(226) Invert Binary Tree (Easy) Solved
Given the root of a binary tree, invert the tree, and return its root.
Example:
- Input:
root = [4,2,7,1,3,6,9]
- Output:
[4,7,2,9,6,3,1]
def invert_tree(n: Optional[TreeNode]):
if not n:
return
n.left, n.right = n.right, n.left
invert_tree(n.left)
invert_tree(n.right)
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
invert_tree(root)
return root |
(101) Symmetric Tree (Easy) Solved
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example:
- Input:
root = [1,2,2,3,4,4,3]
- Output:
true
def are_symmetric(left: Optional[TreeNode], right: Optional[TreeNode]):
has_left = left != None
has_right = right != None
if has_left != has_right:
return False
if not has_left and not has_right:
return True
return (
left.val == right.val and
are_symmetric(left.left, right.right) and
are_symmetric(left.right, right.left))
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return are_symmetric(root.left, root.right) |
(105) Construct Binary Tree from Preorder and Inorder Traversal (Medium) NOT SOLVED ❌
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:
- Input:
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
- Output:
[3,9,20,null,null,15,7]
(106) Construct Binary Tree from Inorder and Postorder Traversal (Medium) NOT SOLVED ❌
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example:
- Input:
inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
- Output:
[3,9,20,null,null,15,7]
(117) Populating Next Right Pointers in Each Node II (Medium) NOT SOLVED ❌
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example:
- Input:
root = [1,2,3,4,5,null,7]
- Output:
[1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
(114) Flatten Binary Tree to Linked List (Medium) NOT SOLVED ❌
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Example:
- Input:
root = [1,2,5,3,4,null,6]
- Output:
[1,null,2,null,3,null,4,null,5,null,6]
(112) Path Sum (Easy) Solved
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.
Example:
- Input:
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
- Output:
true
def has_path_sum(n: Optional[TreeNode], target_sum: int, curr_sum: int) -> bool:
if n == None:
return False
curr_sum += n.val
if not n.left and not n.right:
return curr_sum == target_sum
return (has_path_sum(n.left, target_sum, curr_sum) or
has_path_sum(n.right, target_sum, curr_sum))
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
return has_path_sum(root, targetSum, 0) |
(129) Sum Root to Leaf Numbers (Medium) Solved
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123. Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example:
- Input:
root = [1,2,3]
- Output:
25
def sum_leaves(node: Optional[TreeNode], num: int) -> int:
if not node:
return 0
num = (num * 10) + node.val
if node.left == None and node.right == None:
return num
return (sum_leaves(node.left, num) +
sum_leaves(node.right, num))
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return sum_leaves(root, 0) |
(124) Binary Tree Maximum Path Sum (Hard) Solved
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:
- Input:
root = [1,2,3]
- Output:
6
(173) Binary Search Tree Iterator (Medium) NOT SOLVED ❌
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):
BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.
You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.
Example:
- Input:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
- Output:
[null, 3, 7, true, 9, true, 15, true, 20, false]
(222) Count Complete Tree Nodes (Easy) Solved
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example:
- Input:
[1,2,3,4,5,6]
- Output:
6
def leaf_exists(root: Optional[TreeNode], max_depth: int, last_level_idx: int) -> bool:
n = root
depth = 0
while n:
depth += 1
mid = pow(2, max_depth - depth) / 2
if last_level_idx < mid:
n = n.left
else:
n = n.right
last_level_idx -= mid
return depth == max_depth
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
# Navigate left side to determine tree depth:
n = root
max_depth = 0
while n:
max_depth += 1
n = n.left
max_nodes_for_given_depth = pow(2, max_depth) - 1
# Do binary searches down to the last level to find
# where last last node exists:
low, high = 0, pow(2, max_depth - 1) - 1
last_exists_idx = -1
prev_mid = -1
while low <= high:
mid = (low + high) // 2
exists = leaf_exists(root, max_depth, mid)
if exists:
low = mid + 1
else:
high = mid - 1
return pow(2, max_depth - 1) + low - 1 |
(236) Lowest Common Ancestor of a Binary Tree (Medium) Solved
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
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:
- Input:
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
- Output:
3
Binary Tree BFS
(199) Binary Tree Right Side View (Medium) NOT SOLVED ❌
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
- Input:
root = [1,2,3,null,5,null,4]
- Output:
[1,3,4]
(637) Average of Levels in Binary Tree (Easy) NOT SOLVED ❌
Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.
Example:
- Input:
root = [3,9,20,null,null,15,7]
- Output:
[3.00000,14.50000,11.00000]
from collections import deque
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
queue = deque()
queue.append(root)
results = []
while queue:
nodes_this_level = len(queue)
sum_for_level = 0
for i in range(nodes_this_level):
n = queue.popleft()
if not n:
continue
sum_for_level += n.val
if n.left:
queue.append(n.left)
if n.right:
queue.append(n.right)
results.append(sum_for_level / nodes_this_level)
return results |
(102) Binary Tree Level Order Traversal (Medium) NOT SOLVED ❌
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:
- Input:
root = [3,9,20,null,null,15,7]
- Output:
[[3],[9,20],[15,7]]
(102) Binary Tree Zigzag Level Order Traversal (Medium) NOT SOLVED ❌
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example:
- Input:
root = [3,9,20,null,null,15,7]
- Output:
[[3],[20,9],[15,7]]
Binary Search Tree
(530) Minimum Absolute Difference in BST (Easy) Solved
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example:
- Input:
root = [4,2,6,1,3]
- Output:
1
MAX_DIFF = float('inf')
def bst_to_sorted_arr(n: Optional[TreeNode], arr: list[int]) -> None:
if n:
bst_to_sorted_arr(n.left, arr)
arr.append(n.val)
bst_to_sorted_arr(n.right, arr)
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
arr = []
bst_to_sorted_arr(root, arr)
min_diff = float('inf')
for i in range(1, len(arr)):
min_diff = min(min_diff, arr[i] - arr[i-1])
return min_diff |
(230) Kth Smallest Element in a BST (Medium) NOT SOLVED ❌
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Example:
- Input:
root = [3,1,4,null,2], k = 1
- Output:
1
(98) Validate Binary Search Tree (Medium) NOT SOLVED ❌
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:
- Input:
root = [2,1,3]
- Output:
true
Graph General
(200) Number of Islands (Medium) Solved
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:
- Input:
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
- Output:
1
def sink_island_recursive(grid: list[list[int]], x: int, y: int, w: int, h: int) -> None:
# End case - off grid:
if (x < 0 or x >= w) or (y < 0 or y >= h):
return
# End case - already ocean:
if grid[y][x] == '0':
return
# Recursive case (is part of island):
grid[y][x] = '0'
sink_island_recursive(grid, x+1, y, w, h)
sink_island_recursive(grid, x-1, y, w, h)
sink_island_recursive(grid, x, y+1, w, h)
sink_island_recursive(grid, x, y-1, w, h)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if len(grid) == 0 or len(grid[0]) == 0:
return 0
HEIGHT = len(grid)
WIDTH = len(grid[0])
num_island = 0
for y in range(HEIGHT):
for x in range(WIDTH):
if(grid[y][x] == '1'):
num_island += 1
sink_island_recursive(grid, x, y, WIDTH, HEIGHT)
return num_island |
(130) Surrounded Regions (Medium) Solved
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
- Input:
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
- Output:
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
h, w = len(board), len(board[0])
# KEY:
# 'o' = connected to edge.
def recursive_expand_area(x: int, y: int):
"""Expands from edge cell to mark all connected as '0'."""
if x < 0 or x >= w or y < 0 or y >= h:
return
if board[y][x] == 'O':
board[y][x] = 'o'
recursive_expand_area(x + 1, y) # Right.
recursive_expand_area(x - 1, y) # Left.
recursive_expand_area(x, y + 1) # Down.
recursive_expand_area(x, y - 1) # Up.
# STEP 1.A: Check left and right edges:
for y in range(0, h):
if board[y][0] == 'O':
recursive_expand_area(0, y)
if board[y][w - 1] == 'O':
recursive_expand_area(w - 1, y)
# STEP 1.A: Check top and bottom edges:
for x in range(0, w):
if board[0][x] == 'O':
recursive_expand_area(x, 0)
if board[h - 1][x] == 'O':
recursive_expand_area(x, h - 1)
# STEP 2: For any found island to leave on, turn to `O':
for y in range(h):
for x in range(w):
if board[y][x] == 'O':
board[y][x] = 'X'
elif board[y][x] == 'o':
board[y][x] = 'O'
return |
(133) Clone Graph (Medium) NOT SOLVED ❌
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.
class Node {
public int val; public List<Node> neighbors;
}
Test case format:
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:
- Input:
adjList = [[2,4],[1,3],[2,4],[1,3]]
- Output:
[[2,4],[1,3],[2,4],[1,3]]
(399) Evaluate Division (Medium) NOT SOLVED ❌
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.
Example:
- Input:
equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
- Output:
[6.00000,0.50000,-1.00000,1.00000,-1.00000]
(207) Course Schedule (Medium) NOT SOLVED ❌
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.
Example:
- Input:
numCourses = 2, prerequisites = 1,0
- Output:
true
(210) Course Schedule II (Medium) NOT SOLVED ❌
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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example:
- Input:
numCourses = 2, prerequisites = 1,0
- Output:
[0,1]
Graph BFS
(909) Snakes and Ladders (Medium) Solved
You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.
You start on square 1 of the board. In each move, starting from square curr, do the following:
Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)]. This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board. If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach the square n2. A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.
Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.
For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4. Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.
Example:
- Input:
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
- Output:
4
MAX_MOVES = 1000
DICE_VALUES = 6
class Cell:
def __init__(self, move_to_square: int):
self.min_moves: int = MAX_MOVES
self.move_to_idx: int = move_to_square - 1
if move_to_square == -1:
self.move_to_idx = -1
class Game:
"""Snakes and ladders game grid."""
def __init__(self, grid: list[list[int]]):
self.cells = []
self.indexes_to_check = []
WIDTH = len(grid)
HEIGHT = len(grid[0])
# Flatten the funny ordering of cells into a single array of cells
# so we can think about it as a 1D array, not 2D.
for y_virtual in range(HEIGHT):
for x_virtual in range(WIDTH):
y = HEIGHT - 1 - y_virtual
x = x_virtual
if y_virtual % 2 == 1:
x = WIDTH - 1 - x_virtual
self.cells.append(Cell(grid[y][x]))
self.num_cells = WIDTH * HEIGHT
def determine_min_moves(self) -> int:
self.cells[0].min_moves = 0
self.indexes_to_check = [0]
while len(self.indexes_to_check) > 0:
idx = self.indexes_to_check.pop()
min_moves = self.cells[idx].min_moves + 1
if min_moves >= MAX_MOVES:
continue
for v in range(1, DICE_VALUES + 1):
improvement, new_idx = self.set_cell_at_idx(idx + v, min_moves)
# TODO(anoske): Not all of these need to be checked.
# ... if we can get to cell 3 and cell 6 in 1 move, why check cell 3?
if improvement:
self.indexes_to_check.append(new_idx)
min_total_moves = self.cells[self.num_cells - 1].min_moves
if min_total_moves == MAX_MOVES:
min_total_moves = -1
return min_total_moves
def set_cell_at_idx(self, idx: int, min_moves: int) -> (bool, int):
"""Set the cell or its snake/ladder destination.
Returns:
True if new min moves for the landed upon cell.
Index of cell landed upon (might be after a snake or ladder).
"""
if idx >= len(self.cells):
return False, idx
if self.cells[idx].move_to_idx != -1:
idx = self.cells[idx].move_to_idx
if min_moves < self.cells[idx].min_moves:
self.cells[idx].min_moves = min_moves
return True, idx
return False, idx
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
if not board or len(board) == 0 or len(board[0]) == 0:
return -1
game = Game(board)
return game.determine_min_moves() |
(433) Minimum Genetic Mutation (Medium) NOT SOLVED ❌
A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.
Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.
For example, "AACCGGTT" --> "AACCGGTA" is one mutation. There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.
Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.
Note that the starting point is assumed to be valid, so it might not be included in the bank.
Example:
- Input:
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
- Output:
1
(127) Word Ladder (Hard) NOT SOLVED ❌
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Example:
- Input:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
- Output:
5
Trie
(208) Implement Trie (Prefix Tree) (Medium) Solved
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:
- Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
- Output:
[null, null, true, false, true, null, true]
NUM_LETTERS = 26
def letter_to_idx(letter: str) -> int:
return ord(letter.lower()) - ord('a')
class TreeNode:
def __init__(self, letter: str, end_word: bool):
self.end_word = end_word
self.child = None # Lazy initialization.
def init_child(self) -> None:
self.child = [None] * NUM_LETTERS
class Trie:
def __init__(self):
self.head_node = TreeNode('-', False)
def insert(self, word: str) -> None:
n = self.head_node
for i, letter in enumerate(word):
end_word = i == len(word) - 1
idx = letter_to_idx(letter)
if n.child == None:
n.init_child()
if n.child[idx] == None:
n.child[idx] = TreeNode(letter, end_word)
print('letter=', letter, ' idx=', idx, ' end_word=', end_word)
elif end_word:
n.child[idx].end_word = True
n = n.child[idx]
def search(self, word: str) -> bool:
n = self.head_node
for i, letter in enumerate(word):
end_word = i == len(word) - 1
idx = letter_to_idx(letter)
if n.child == None or n.child[idx] == None:
return False
elif end_word:
return n.child[idx].end_word
n = n.child[idx]
return False
def startsWith(self, prefix: str) -> bool:
n = self.head_node
for i, letter in enumerate(prefix):
end_word = i == len(prefix) - 1
idx = letter_to_idx(letter)
if n.child == None or n.child[idx] == None:
return False
elif end_word:
return True
n = n.child[idx]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix) |
(211) Design Add and Search Words Data Structure (Medium) NOT SOLVED ❌
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]
(212) Word Search II (Hard) NOT SOLVED ❌
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:
- Input:
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
- Output:
["eat","oath"]
Backtracking
(17) Letter Combinations of a Phone Number (Medium) NOT SOLVED ❌
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
- Input:
digits = "23"
- Output:
["ad","ae","af","bd","be","bf","cd","ce","cf"]
DIGITS_MAPPING = [
'abc', # 2.
'def', # 3.
'ghi', # 4.
'jkl', # 5.
'mno', # 6.
'pqrs', # 7.
'tuv', # 8.
'wxyz' # 9.
]
def indexes_plus_one(indexes: list[int], digit_number_mappings: list[str], stack_letters: list[str]) -> bool:
"""Adds one to indexes (in place) as if it were a number.
Returns:
True if added, false if overflow."""
for i in range(len(indexes) - 1, -1, -1):
indexes[i] += 1
if indexes[i] >= len(digit_number_mappings[i]):
indexes[i] = 0
stack_letters[i] = digit_number_mappings[i][indexes[i]]
else:
# print(' - i=', i, ' indexes[i]=', indexes[i] )
stack_letters[i] = digit_number_mappings[i][indexes[i]]
return True
return False
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digit_number_mappings = []
indexes = [0] * len(digits)
stack_letters = []
for digit in digits:
mapping_idx = ord(digit) - ord('2')
digit_number_mappings.append(DIGITS_MAPPING[mapping_idx])
stack_letters.append(DIGITS_MAPPING[mapping_idx][0])
# Print intermediate structures:
# print('digit_number_mappings = ', digit_number_mappings)
# print('indexes = ', indexes)
# print('stack_letters = ', stack_letters, '\n\n')
combinations = []
combinations.append( ''.join(stack_letters) )
while indexes_plus_one(indexes, digit_number_mappings, stack_letters):
# print(' > indexes = ', indexes)
combinations.append( ''.join(stack_letters) )
return combinations |
(77) Combinations (Medium) NOT SOLVED ❌
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example:
- Input:
n = 4, k = 2
- Output:
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
(46) Permutations (Medium) NOT SOLVED ❌
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example:
- Input:
nums = [1,2,3]
- Output:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
(39) Combination Sum (Medium) NOT SOLVED ❌
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency
of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example:
- Input:
candidates = [2,3,6,7], target = 7
- Output:
[[2,2,3],[7]]
(52) N-Queens II (Hard) NOT SOLVED ❌
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
- Input:
n = 4
- Output:
2
(22) Generate Parentheses (Medium) NOT SOLVED ❌
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example:
- Input:
n = 3
- Output:
["((()))","(()())","(())()","()(())","()()()"]
(79) Word Search (Medium) NOT SOLVED ❌
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:
- Input:
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
- Output:
true
Divide & Conquer
(108) Convert Sorted Array to Binary Search Tree (Easy) NOT SOLVED ❌
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Example:
- Input:
nums = [-10,-3,0,5,9]
- Output:
[0,-3,9,-10,null,5]
(148) Sort List (Medium) NOT SOLVED ❌
Given the head of a linked list, return the list after sorting it in ascending order.
Example:
- Input:
head = [4,2,1,3]
- Output:
[1,2,3,4]
(427) Construct Quad Tree (Medium) NOT SOLVED ❌
Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.
Return the root of the Quad-Tree representing grid.
A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:
- val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
- isLeaf: True if the node is a leaf node on the tree or False if the node has four children.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
We can construct a Quad-Tree from a two-dimensional area using the following steps:
- If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
- If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
- Recurse for each of the children with the proper sub-grid.
If you want to know more about the Quad-Tree, you can refer to the wiki.
Quad-Tree format:
You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.
It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].
If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.
Example:
- Input:
grid = [[0,1],[1,0]]
- Output:
[[0,1],[1,0],[1,1],[1,1],[1,0]]
(23) Merge k Sorted Lists (Hard) NOT SOLVED ❌
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:
- Input:
lists = [[1,4,5],[1,3,4],[2,6]]
- Output:
[1,1,2,3,4,4,5,6]
Kadane's Algorithm
(53) Maximum Subarray (Medium) Solved
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example:
- Input:
nums = [-2,1,-3,4,-1,2,1,-5,4]
- Output:
6
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
max_total = nums[0]
total = 0
for num in nums:
if total < 0:
total = 0
total += num
max_total = max(max_total, total)
return max_total |
(918) Maximum Sum Circular Subarray (Medium) NOT SOLVED ❌
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
Example:
- Input:
nums = [1,-2,3,-2]
- Output:
3
Binary Search
(35) Search Insert Position (Easy) Solved
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example:
- Input:
nums = [1,3,5,6], target = 5
- Output:
2
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if not nums:
return 0
print('INPUT: nums=', nums, ' ... target=', target)
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return low |
(74) Search a 2D Matrix (Medium) Solved
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example:
- Input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output:
true
def get_cell_value(matrix: List[List[int]], idx: int, width: int) -> int:
x = idx % width
y = idx // width
return matrix[y][x]
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
HEIGHT, WIDTH = len(matrix), len(matrix[0])
NUM_CELLS = HEIGHT * WIDTH
low, high = 0, NUM_CELLS - 1
while low < high:
mid = (low + high) // 2
val = get_cell_value(matrix, mid, WIDTH)
print(' low=', low, ' mid=', mid,' (', val,') high=', high, '... target=', target)
if val == target:
return True
if val < target:
low = mid + 1
else:
high = mid - 1
return get_cell_value(matrix, low, WIDTH) == target |
(162) Find Peak Element (Medium) Solved
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed 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] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example:
- Input:
nums = [1,2,3,1]
- Output:
2
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums:
return 0
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] < nums[mid+1]: # Uphill to the right.
low = mid + 1
else:
high = mid
return low |
(33) Search in Rotated Sorted Array (Medium) NOT SOLVED ❌
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.
You must write an algorithm with O(log n) runtime complexity.
Example:
- Input:
nums = [4,5,6,7,0,1,2], target = 0
- Output:
4
(43) Find First and Last Position of Element in Sorted Array (Medium) NOT SOLVED ❌
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.
Example:
- Input:
nums = [5,7,7,8,8,10], target = 8
- Output:
[3,4]
(153) Find Minimum in https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150 Sorted Array (Medium) NOT SOLVED ❌
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.
You must write an algorithm that runs in O(log n) time.
Example:
- Input:
nums = [3,4,5,1,2]
- Output:
1
(4) Median of Two Sorted Arrays (Hard) NOT SOLVED ❌
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)).
Example:
- Input:
nums1 = [1,3], nums2 = [2]
- Output:
2.00000
Heap
(215) Kth Largest Element in an Array (Medium) Solved
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.
Can you solve it without sorting?
Example:
- Input:
nums = [3,2,1,5,6,4], k = 2
- Output:
5
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if not nums:
return 0
smallest_x = len(nums) - k + 1
if smallest_x < 1:
return 0
min_val = float('inf')
max_val = -float('inf')
for num in nums:
min_val = min(min_val, num)
max_val = max(max_val, num)
if k == 1:
return max_val
if smallest_x == 1:
return min_val
while min_val < max_val:
mid = (max_val + min_val) // 2
num_equal = 0
num_less = 0
for num in nums:
if num == mid:
num_equal += 1
elif num < mid:
num_less += 1
num_equal_or_less = num_equal + num_less
if smallest_x <= num_less:
max_val = mid
elif smallest_x > num_equal_or_less:
min_val = mid
else:
return mid
return min_val |
(502) IPO (Hard) NOT SOLVED ❌
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.
Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
Example:
- Input:
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
- Output:
4
(373) Find K Pairs with Smallest Sums (Medium) Solved
You are given two integer arrays nums1 and nums2 sorted in non-decreasing 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.
Example:
- Input:
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
- Output:
[[1,2],[1,4],[1,6]]
(295) Find Median from Data Stream (Hard) NOT SOLVED ❌
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:
- Input:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]
- Output:
[null, null, null, 1.5, null, 2.0]
Bit Manipulation
(67) Add Binary (Easy) Solved
Given two binary strings a and b, return their sum as a binary string.
Example:
- Input:
a = "11", b = "1"
- Output:
"100"
def binary_str_to_int(s: str) -> int:
if not s:
return 0
total = 0
for digit in s:
val = 0
if digit == '1':
val = 1
total = (total * 2) + val
return total
def int_to_binary_string(value: int) -> str:
if value == 0:
return '0'
digits_arr = []
while value > 0:
digits_arr.append(str(value % 2)) # Add remainder.
value = value // 2
digits_arr.reverse()
return ''.join(digits_arr)
class Solution:
def addBinary(self, a: str, b: str) -> str:
a_val = binary_str_to_int(a)
b_val = binary_str_to_int(b)
return int_to_binary_string(a_val + b_val)
# TODO(noske): See if just iterate from the back of the array
# and doing a 'carry-over' num is faster. |
(190) Reverse Bits (Easy) Solved
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:
- Input:
n = 00000010100101000001111010011100
- Output:
964176192 (00111001011110000010100101000000)
class Solution:
def reverseBits(self, n: int) -> int:
result = 0
for _ in range(32):
result <<= 1 # Left shift result
result |= n & 1 # Bitwise OR result with the rightmost bit of n
n >>= 1 # Right shift n to process the next bit
return result |
(191) Number of 1 Bits (Easy) Solved
Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Note:
- Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It 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 3, the input represents the signed integer. -3.
Example:
- Input:
n = 00000000000000000000000000001011
- Output:
3
class Solution:
def hammingWeight(self, n: int) -> int:
# print('n=', n, ' -> ', bin(n))
num_ones = 0
while n > 0:
num_ones += n & 1 # Mask on last bit.
n >>= 1 # Right shift.
return num_ones |
(136) Single Number (Easy) Solved
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example:
- Input:
nums = [2,2,1]
- Output:
1
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
result = result ^ num
return result |
(137) Single Number II (Medium) Solved
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example:
- Input:
nums = [2,2,3,2]
- Output:
3
class Solution:
def singleNumber(self, nums: List[int]) -> int:
one, two, three = 0, 0, 0
for num in nums:
# `two` keeps the bits which appear twice.
two |= one & num
# `one` keeps the bits which appear for the first time.
one ^= num
# `three` represents whether one bit has appeared three times.
three = one & two
# if one bit has appeared three times, we clear the
# corresponding bits in both `one` and `two`.
one &= ~three
two &= ~three
return one |
(201) Bitwise AND of Numbers Range (Medium) NOT SOLVED ❌
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Example:
- Input:
left = 5, right = 7
- Output:
4
Math
(9) Palindrome Number (Easy) Solved
Given an integer x, return true if x is a palindrome, and false otherwise.
Example:
- Input:
x = 121
- Output:
true
class Solution:
def isPalindrome(self, x: int) -> bool:
x_str = str(x)
mid = len(x_str) // 2
for i in range(0, mid):
if x_str[i] != x_str[len(x_str) - i - 1]:
return False
return True |
(66) Plus One (Easy) Solved
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Example:
- Input:
[1,2,3]
- Output:
[1,2,4]
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
new_digits = []
to_add = 1
for i in range(len(digits) - 1, -1, -1):
new_digits.append( (digits[i] + to_add) % 10 )
if to_add > 0 and digits[i] < 9:
to_add = 0
if to_add == 1:
new_digits.append(1)
new_digits.reverse()
return new_digits |
(172) Factorial Trailing Zeroes (Medium) NOT SOLVED ❌
Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
Example:
- Input:
n = 3
- Output:
0
(69) Sqrt(x) (Easy) Solved
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
- For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Example:
- Input:
x = 4
- Output:
2
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
if x == 2:
return 1
low, high = 1, x // 2 # Square root is always less than half.
while low <= high:
mid = (low + high) // 2
square = mid * mid
if square == x:
return mid
if square < x:
low = mid + 1
else:
high = mid - 1
if high * high < x:
return high
return low |
(50) Pow(x, n) (Medium) Solved
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example:
- Input:
x = 2.00000, n = 10
- Output:
1024.00000
class Solution:
def myPow(self, x: float, n: int) -> float:
# Base cases:
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
# Recursive function to implement the logic:
def pow_recursive(x, n):
"""We reduce the number of multiplications using the properties of exponents.
For instance: x^8 is the same as (x^4) * (x^4).
> 3^4 (81) = 3^2 (9) * 3^2 (9)
> 2^8 (256) = 2^4 (16) * 2^4 (16)
> 2^5.5 (45.255) = 2^2 (4) * 2^2 (4) [16] * 2.75 (5.5/2)
Instead of multiplying x by itself 8 times, we can square x^4 once to get x^8.
"""
if n == 0:
return 1
half = pow_recursive(x, n // 2)
if n % 2 == 0:
return half * half
else:
return half * half * x
return pow_recursive(x, n) |
(149) Max Points on a Line (Hard) NOT SOLVED ❌
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.
Example:
- Input:
points = [[1,1],[2,2],[3,3]]
- Output:
3
1D DP
(70) Climbing Stairs (Easy) NOT SOLVED ❌
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:
- Input:
n = 2
- Output:
2
(198) House Robber (Medium) NOT SOLVED ❌
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:
- Input:
nums = [1,2,3,1]
- Output:
4
(139) Word Break (Medium) NOT SOLVED ❌
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:
- Input:
s = "leetcode", wordDict = ["leet","code"]
- Output:
true
(322) Coin Change (Medium) NOT SOLVED ❌
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:
- Input:
coins = [1,2,5], amount = 11
- Output:
3
(300) Longest Increasing Subsequence (Medium) NOT SOLVED ❌
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example:
- Input:
nums = [10,9,2,5,3,7,101,18]
- Output:
4
Multidimensional DP
(120) Triangle (Medium) NOT SOLVED ❌
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example:
- Input:
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
- Output:
11
(64) Minimum Path Sum (Medium) NOT SOLVED ❌
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.
Example:
- Input:
grid = [[1,3,1],[1,5,1],[4,2,1]]
- Output:
7
(63) Unique Paths II (Medium) NOT SOLVED ❌
You are given an m x n integer array grid. There is a robot 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.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Example:
- Input:
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
- Output:
2
(5) Longest Palindromic Substring (Medium) NOT SOLVED ❌
Given a string s, return the longest palindromic substring in s.
Example:
- Input:
s = "babad"
- Output:
"bab"
(97) Interleaving String (Medium) NOT SOLVED ❌
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
- s = s1 + s2 + ... + sn
- t = t1 + t2 + ... + tm
Example:
- Input:
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
- Output:
true
(72) Edit Distance (Medium) NOT SOLVED ❌
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example:
- Input:
word1 = "horse", word2 = "ros"
- Output:
3
(123) Best Time to Buy and Sell Stock III (Hard) NOT SOLVED ❌
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
- Input:
prices = [3,3,5,0,0,3,1,4]
- Output:
6
(188) Best Time to Buy and Sell Stock IV (Hard) NOT SOLVED ❌
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: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
- Input:
k = 2, prices = [2,4,1]
- Output:
2
(221) Maximal Square (Medium) NOT SOLVED ❌
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
- Input:
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
- Output:
4
See Also
Links
- leetcode.com - top interview 150 (official site) - and a great set of questions.
- Wikipedia - LeetCode