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.
"""
p1, p2 = m - 1, n - 1
for p in range(m + n - 1, -1, -1):
if p2 < 0:
break
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
The time complexity of the algorithm is O(n + m) because it goes through each element in the list at most once. The space complexity is O(1) because it doesn't use any additional space that scales with the input size, it modifies the input arrays in place.
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# move elements nonequal to val forward to the start of the list
p = 0
for i, num in enumerate(nums):
if num != val:
nums[p] = num
p += 1
return p
The time complexity is O(n) and the space complexity is O(1) as it modifies the input list in place.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
#find min from left and max from right
n = len(prices)
min_l = float("inf")
res = 0
for price in prices:
min_l = min(min_l, price)
res = max(res, price - min_l)
return res
The time complexity of the algorithm is O(n) and the space complexity is O(1).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(1, len(prices)):
diff = prices[i] - prices[i - 1]
if diff > 0:
res += diff
return res
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
last_pos = n - 1
for i in range(n - 1, -1, -1):
if i + nums[i] >= last_pos:
last_pos = i
return last_pos == 0
Time Comp. O(n) because a single pass. Space Comp. O(1).