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 elements marked in bold italics 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 remaining 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. 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.
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 that your solution can be accepted:
- Modify the array
numsso that the firstkelements contain the unique elements 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.
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.
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#
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.
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.
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 integer.
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 gain from this transaction. If you cannot make 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 must 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, so 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 from index 0 to 1, then jump 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: No matter what, you will always arrive at index 3. The maximum jump length at this index is 0, so you cannot 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 an integer array nums of length n, where the initial position is 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 can 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 index.
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 or suffix of the array is in the 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, 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 height map is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1], in this case, 6 units of rainwater (blue section) can be trapped.
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 in the string.
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", and its length is 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 the string.
A word is defined as a string of non-space characters. The words in s will be separated by at least one space.
Return a string that is the result of reversing the order of the words and removing any extra spaces between them.
Note: The input string s may contain leading, trailing, or multiple spaces between words. The returned string should have a single space between words, and no 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 reversed string should reduce them to a single space.
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 as an integer array [index1, index2].
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 complexity.
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 two endpoints of the i-th line are (i, 0) and (i, 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 may not slant the container.
Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The container can hold water (blue section) with a maximum value of 49.
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