Merge Two Sorted Arrays#
You are given two integer arrays nums1 and nums2 sorted in non-decreasing order, along with two integers m and n, representing the number of elements in nums1 and nums2, respectively.
Please merge nums2 into nums1 so that the merged array is also sorted in non-decreasing order.
Note: The final merged array should not be returned by the function, but instead be stored in the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements represent the elements to be merged, and the last n elements are 0, which should be ignored. The length of nums2 is n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays [1,2,3] and [2,5,6] need to be merged.
The merged result is [1,2,2,3,5,6], where the bold italicized elements are from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays [1] and [] need to be merged.
The merged result is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays to be merged are [] and [1].
The merged result is [1].
Note that since m = 0, there are no elements in nums1. The only 0 in nums1 is just to ensure that the merged result can be stored in nums1.
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.
"""
i, j = m - 1, n - 1
k = len(nums1) - 1
while (i >= 0 and j >= 0):
if (nums1[i] > nums2[j]):
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
if (i == -1):
for i in range(0, j+1):
nums1[i] = nums2[i]
Remove Element#
You are given an array nums and a value val, you need to in-place remove all elements equal to val and return the new length of the array after removal.
Do not use extra array space, you must use only O(1) extra space and modify the input array in-place.
The order of elements can be changed. You do not need to consider the elements beyond the new length.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: The function should return the new length 2, and the first two elements of nums are both 2. You do not need to consider the elements beyond the new length of the array. For example, if the function returns a new length of 2, and nums = [2,2,3,3] or nums = [2,2,0,0], it will be considered a correct answer.
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: The function should return the new length 5, and the first five elements of nums are 0, 1, 3, 0, 4. Note that these five elements can be in any order. You do not need to consider the elements beyond the new length of the array.
class Solution:
def removeElement(self, nums: list[int], val: int) -> int:
i, j = 0, len(nums)
while (i < j):
if (nums[i] == val):
j -= 1
nums[i] = nums[j]
else:
i += 1
return j
Remove Duplicates from Sorted Array#
Given a sorted array nums, please in-place remove duplicates such that each element appears only once and return the new length of the array. The relative order of the elements should be kept consistent. Then return the number of unique elements in nums.
Consider the number of unique elements in nums as k, you need to ensure your solution can be accepted by doing the following:
- Modify the array
numsso that the firstkelements contain the unique elements and are arranged in the order they originally appeared innums. The remaining elements innumscan be ignored. - Return
k.
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: The function should return the new length 2, and the first two elements of the original array nums are modified to be 1, 2. You do not need to consider the elements beyond the new length of the array.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: The function should return the new length 5, and the first five elements of the original array nums are modified to be 0, 1, 2, 3, 4. You do not need to consider the elements beyond the new length of the array.
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
j = 0
for i in range(1, len(nums)):
if (nums[i] != nums[j]):
nums[j + 1] = nums[i]
j += 1
return j + 1
Remove Duplicates from Sorted Array II#
You are given a sorted array nums, please in-place remove duplicates such that each element appears at most twice, and return the new length of the array.
Do not use extra array space, you must modify the input array in-place and complete it using O(1) extra space.
Example 1:
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3]
Explanation: The function should return the new length length = 5, and the first five elements of the original array are modified to be 1, 1, 2, 2, 3. You do not need to consider the elements beyond the new length of the array.
Example 2:
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3]
Explanation: The function should return the new length length = 7, and the first seven elements of the original array are modified to be 0, 0, 1, 1, 2, 3, 3. You do not need to consider the elements beyond the new length of the array.
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
if (len(nums) <= 2):
return len(nums)
i = 1
for j in range(2, len(nums)):
if (nums[j] != nums[i] or nums[j] == nums[i] and nums[j] != nums[i-1]):
nums[i + 1] = nums[j]
i += 1
return i + 1
Majority Element#
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 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
class Solution:
def majorityElement(self, nums: list[int]) -> int:
count = 0
res = nums[0]
for num in nums:
if (count == 0 or res == num):
res = num
count += 1
else:
count -= 1
return res
Rotate Array#
Given an integer array nums, rotate the elements of the array to the right by k positions, where k is a non-negative number.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Rotate 1 step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
Rotate 1 step to the right: [99,-1,-100,3]
Rotate 2 steps to the right: [3,99,-1,-100]
class Solution:
def rotate(self, nums: list[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(nums, start, end):
while (start < end):
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
k = k % len(nums)
reverse(nums, 0, len(nums) - k - 1)
reverse(nums, len(nums) - k, len(nums)-1)
reverse(nums, 0, len(nums)-1)
Best Time to Buy and Sell Stock#
Given an array prices, where the i-th element prices[i] represents the price of a given stock on the i-th day.
You can only choose to buy the stock on one day and choose to sell it on another different day in the future. Design an algorithm to calculate the maximum profit you can achieve from this transaction.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on the second day (stock price = 1) and sell on the fifth day (stock price = 6), the maximum profit = 6-1 = 5.
Note that profit cannot be 7-1 = 6, because selling price needs to be higher than buying price; also, you cannot sell the stock before you buy it.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the maximum profit is 0.
class Solution:
def maxProfit(self, prices: list[int]) -> int:
minprice = int(1e9)
maxprofit = 0
for price in prices:
maxprofit = max(price - minprice, maxprofit)
minprice = min(price, minprice)
return maxprofit
Jump Game#
Given a non-negative integer array nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you can reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: You can jump 1 step to reach index 1, and then jump 3 steps to reach the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: It can be proven that you will never reach the last index.
class Solution:
def canJump(self, nums: list[int]) -> bool:
n, rightmost = len(nums), 0
for i in range(n):
if (i <= rightmost):
rightmost = max(rightmost, i + nums[i])
if (rightmost >= n-1):
return True
return False
Jump Game II#
Given a length n 0-indexed integer array nums. The initial position is at nums[0].
Each element nums[i] represents the maximum length you can jump forward 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]i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The generated test cases are guaranteed to be able to reach nums[n - 1].
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last position is 2.
Jump from index 0 to index 1, then jump 3 steps to reach the last position.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
class Solution:
def jump(self, nums: list[int]) -> int:
n = len(nums)
rightmost, end, step = 0, 0, 0
for i in range(n-1):
if (rightmost >= i):
rightmost = max(rightmost, i + nums[i])
if (i == end):
end = rightmost
step += 1
return step
Product of Array Except Self#
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The problem data guarantees that the product of any prefix product and suffix product of the array nums will fit in a 32-bit integer range.
Please do not use division, and complete the task in O(*n*) time complexity.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
left = [1 for _ in nums]
right = [1 for _ in nums]
for i in range(1, len(nums)):
left[i] = nums[i-1] * left[i-1]
for i in range(len(nums)-2, -1, -1):
right[i] = nums[i+1] * right[i+1]
return [left[i] * right[i] for i in range(len(nums))]
Trapping Rain Water#
Given n non-negative integers representing the height of each bar with a width of 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above is a representation of the height array [0,1,0,2,1,0,1,3,2,1,2,1], in this case, 6 units of rainwater can be trapped (the blue part represents the rainwater).
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
class Solution:
def trap(self, height: list[int]) -> int:
if (len(height) <= 2):
return 0
lmax = [0 for _ in height]
rmax = [0 for _ in height]
for i in range(1, len(height)-1):
lmax[i] = max(lmax[i-1], height[i-1])
for i in range(len(height)-2, 0, -1):
rmax[i] = max(rmax[i+1], height[i+1])
res = 0
for i in range(1, len(height) - 1):
if (min(lmax[i], rmax[i]) - height[i] > 0):
res += (min(lmax[i], rmax[i]) - height[i])
return res
Roman to Integer#
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, the Roman numeral 2 is written as II, which is two ones. 12 is written as XII, which is X + II. The number 27 is written as XXVII, which is XX + V + II.
Usually, Roman numerals are written from largest to smallest from left to right. However, there are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to represent 4 and 9.Xcan be placed beforeL(50) andC(100) to represent 40 and 90.Ccan be placed beforeD(500) andM(1000) to represent 400 and 900.
Given a Roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Example 2:
Input: s = "IV"
Output: 4
Example 3:
Input: s = "IX"
Output: 9
Example 4:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.
class Solution:
SYMBOL_VALUES = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
def romanToInt(self, s: str) -> int:
ans = 0
n = len(s)
for i, ch in enumerate(s):
val = Solution.SYMBOL_VALUES[ch]
if ((i < n-1) and val < Solution.SYMBOL_VALUES[s[i+1]]):
ans -= val
else:
ans += val
return ans
Integer to Roman#
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, the Roman numeral 2 is written as II, which is two ones. 12 is written as XII, which is X + II. The number 27 is written as XXVII, which is XX + V + II.
Usually, Roman numerals are written from largest to smallest from left to right. However, there are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to represent 4 and 9.Xcan be placed beforeL(50) andC(100) to represent 40 and 90.Ccan be placed beforeD(500) andM(1000) to represent 400 and 900.
Given an integer, convert it to a Roman numeral.
Example 1:
Input: num = 3
Output: "III"
Example 2:
Input: num = 4
Output: "IV"
Example 3:
Input: num = 9
Output: "IX"
Example 4:
Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 5:
Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.
class Solution:
VALUE_SYMBOLS = [
(1000, "M"),
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
]
def intToRoman(self, num: int) -> str:
res = []
for val, symbol in Solution.VALUE_SYMBOLS:
while (num >= val):
res.append(symbol)
num -= val
if (num == 0):
break
return ''.join(res)
Length of Last Word#
Given a string s consisting of words separated by spaces, return the length of the last word.
A word is defined as a maximal substring consisting of non-space characters.
Example 1:
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World", and its length is 5.
Example 2:
Input: s = " fly me to the moon "
Output: 4
Explanation: The last word is "moon", and its length is 4.
Example 3:
Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.
class Solution:
def lengthOfLastWord(self, s: str) -> int:
r = len(s)-1
while (s[r] == ' '):
r -= 1
i = r
while (i >= 0 and s[i] != ' '):
i -= 1
return r-i
Longest Common Prefix#
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 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix.
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
if (len(strs) == 1):
return "".join(strs)
ans = ""
minLength = 300
for s in strs:
minLength = min(minLength, len(s))
for i in range(minLength):
c = strs[0][i]
print(c)
for j in range(len(strs)):
if (strs[j][i] != c):
return ans
ans += c
return ans
Reverse Words in a String#
Given a string s, reverse the order of the words in a string.
A word is defined as a string of non-space characters. s can contain leading, trailing, and multiple spaces between words. The returned string should have a single space separating the words and should not contain any extra spaces.
Example 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: s = " hello world "
Output: "world hello"
Explanation: The reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example"
Output: "example good a"
Explanation: If there are multiple spaces between two words, the result should have a single space between them.
class Solution:
def reverseWords(self, s: str) -> str:
ans = []
end, start = 0, 0
i = len(s) - 1
while (i >= 0):
if (s[i] == " "):
i -= 1
continue
end = i + 1
while (s[i] != " " and i >= 0):
i -= 1
start = i + 1
ans.append(s[start: end])
return ' '.join(ans)
Zigzag Conversion#
Convert a given string s into a zigzag pattern on a given number of rows numRows, reading line by line.
For example, when the input string is "PAYPALISHIRING" and the number of rows is 3, the zigzag pattern looks like this:
P A H N
A P L S I I G
Y I R
Afterwards, your output should be the concatenation of each line read from left to right, producing the new string: "PAHNAPLSIIGYIR".
Please implement a function that converts the string according to the specified number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Example 3:
Input: s = "A", numRows = 1
Output: "A"
class Solution:
def convert(self, s: str, numRows: int) -> str:
if (numRows == 1):
return s
res = ["" for _ in range(numRows)]
step = -1
i, j = 0, 0
while (i < len(s)):
if (j == 0 or j == numRows-1):
step = 0 - step
res[j] += s[i]
j += step
i += 1
return ''.join(res)
Find the Index of the First Occurrence in a String#
Given two strings haystack and needle, return the index of the first occurrence of needle in haystack (0-indexed). If needle is not part of haystack, return -1.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" is not present in "leetcode", so return -1.
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
l1, l2 = len(haystack), len(needle)
if (l2 > l1):
return -1
for i in range(0, l1 - l2 + 1):
if (haystack[i] != needle[0]):
continue
j = 0
while (j < l2 and haystack[i + j] == needle[j]):
j += 1
if (j == l2):
return i
return -1
Is Subsequence#
Given strings s and t, determine if s is a subsequence of t.
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 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
print(s,t)
if(len(s) == 0 or s == t):
return True
for i in range(0,len(t)):
if(t[i] == s[0]):
return self.isSubsequence(s[1:],t[i+1:])
return False
Two Sum II - Input Array Is Sorted#
Given a 1-indexed integer array numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2], where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, as an integer array of length 2.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Your solution should be in constant space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 and 7 add up to 9. Therefore, index1 = 1, index2 = 2. Return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: 2 and 4 add up to 6. Therefore, index1 = 1, index2 = 3. Return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: -1 and 0 add up to -1. Therefore, index1 = 1, index2 = 2. Return [1, 2].
class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
start = 0
end = len(numbers) - 1
while(start < end):
if(numbers[start] + numbers[end] == target):
return [start+1,end+1]
elif(numbers[start] + numbers[end] > target):
end -= 1
else:
start += 1
Container With Most Water#
Given an integer array height of length n. There are n vertical lines drawn such that the i-th line has a height of height[i].
Find two lines that together with the x-axis form a container that can hold the most water.
Return the maximum amount of water a container can store.
Note: You cannot tilt the container.
Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The vertical lines represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the container can hold 49 units of water.
Example 2:
Input: height = [1,1]
Output: 1
class Solution:
def maxArea(self, height: list[int]) -> int:
start,end = 0,len(height)-1
res = (end-start) * min(height[start],height[end])
while(start < end):
if(height[start] < height[end]):
start += 1
else:
end -= 1
res = max(res,(end-start) * min(height[start],height[end]))
return res