Array / String

# Time complexity: O(n)
# Space complexity: O(1)
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = m + n - 1
    i1 = m - 1
    i2 = n - 1

    # Merge backwards in nums1 until nums2 is empty
    while i2 >= 0:
        if i1 >= 0 and nums1[i1] > nums2[i2]:
            nums1[i] = nums1[i1]
            i1 -= 1
        else:
            nums1[i] = nums2[i2]
            i2 -= 1
        i -= 1

# Time complexity: O(n)
# Space complexity: O(1)
def removeElement(nums: List[int], val: int) -> int:
    nonValIndex = 0

    # Swap values until all instances of target are at back of list
    for i in range(len(nums)):
        if nums[i] != val:
            nums[i], nums[nonValIndex] = nums[nonValIndex], nums[i]
            nonValIndex += 1
    return nonValIndex

# Time complexity: O(n)
# Space complexity: O(1)
def removeDuplicates(nums: List[int]) -> int:
    finalIndex = 1

    for i in range(1, len(nums)):
        # If not duplicate, place current integer at nums[finalIndex]
        if nums[i] > nums[i - 1]:
            nums[finalIndex] = nums[i]
            finalIndex += 1
    return finalIndex

# Time complexity: O(n)
# Space complexity: O(1)
def majorityElement(nums: List[int]) -> int:
    answer = nums[0]
    count = 0

    # If an answer always exists, its count will always be
    # greater than the total count of all other values
    for num in nums:
        if num == answer:
            count += 1
        else:
            count -= 1
            if count == 0:
                answer = num
                count = 1

    return answer

# Time complexity: O(n)
# Space complexity: O(1)
def maxProfit(prices: List[int]) -> int:
    profit = 0
    minPrice = prices[0]

    for i in range(1, len(prices)):
        profit = max(profit, prices[i] - minPrice)
        minPrice = min(minPrice, prices[i])

    return profit

This problem is similar to finding a maximum subarray.

# Kadane's algorithm
# Time complexity: O(n)
# Space complexity: O(1)
def maxSubarray(nums: List[int]) -> int:
    bestSum = currentSum = 0

    for x in nums:
        # If x is low enough to make the current sum negative,
        # expanding the current subarray is useless.
        # Reset to 0 for new subarray.
        currentSum = max(0, currentSum + x)
        bestSum = max(bestSum, currentSum)

    return bestSum

# Time complexity: O(n)
# Space complexity: O(1)
def romanToInt(s: str) -> int:
    m = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000
    }

    answer = 0
    end = len(s) - 1

    # If current char is 'less' than next char,
    # current char must be decremented from answer
    for i in range(len(s)):
        if i < end and m[s[i]] < m[s[i + 1]]:
            answer -= m[s[i]]
        else:
            answer += m[s[i]]
    return answer

# Time complexity: O(n)
# Space complexity: O(1)
def lengthOfLastWord(s: str) -> int:
    i = len(s) - 1
    while s[i] == " ":
        i -= 1

    count = 0
    while i >= 0 and s[i] != " ":
        i -= 1
        count += 1

    return count

# Time complexity: O(n*m) where m is length of shortest word
# Space complexity: O(1)
def longestCommonPrefix(strs: List[str]) -> str:
    answer = []

    # Find shortest word, which will contain answer
    shortestWord = strs[0]
    for word in strs:
        if len(word) < len(shortestWord):
            shortestWord = word

    for i in range(len(shortestWord)):
        for word in strs:
            if word[i] != shortestWord[i]:
                return "".join(answer)
        answer.append(shortestWord[i])

    return shortestWord

# Time complexity: O(n)
# Space complexity: O(1)
def strStr(haystack: str, needle: str) -> int:
    i = 0
    matchCount = 0

    while i < len(haystack):
        if haystack[i] == needle[matchCount]:
            matchCount += 1
        else: # Reset search
            i -= matchCount
            matchCount = 0

        if matchCount == len(needle):
            return i - len(needle) + 1
        i += 1

    return -1

# Time complexity: O(n)
# Space complexity: O(1)
def removeDuplicates(nums: List[int]) -> int:
    i = 0

    # Ignore first two elements
    # i essentially tracks the next duplicate for replacing
    # If current integer is valid, place in nums[i]
    for n in range(len(nums)):
        if i < 2 or nums[n] > nums[i - 2]:
            nums[i] = nums[n]
            i += 1
    return i

# Time complexity: O(n)
# Space complexity: O(1)
def rotate(nums: List[int], k: int) -> None:
    k = k % len(nums)
    reverseList(nums, 0, len(nums) - 1)
    reverseList(nums, 0, k - 1)
    reverseList(nums, k, len(nums) - 1)

def reverseList(li: List[int], start: int, end: int) -> None:
    while start < end:
        li[start], li[end] = li[end], li[start]
        start += 1
        end -= 1

# Time complexity: O(n)
# Space complexity: O(1)
def maxProfit(prices: List[int]) -> int:
    answer = 0
    i = 1

    while i < len(prices):
        # Buy at valley
        while i < len(prices) and prices[i] <= prices[i - 1]:
            i += 1
        buy = prices[i - 1]
        # Sell at peak
        while i < len(prices) and prices[i] >= prices[i - 1]:
            i += 1
        sell = prices[i - 1]
        answer += sell - buy

    return answer

# Time complexity: O(n)
# Space complexity: O(1)
def canJump(nums: List[int]) -> bool:
    if len(nums) <= 1:
        return True

    farthest = 0
    target = len(nums) - 1

    # From start, update farthest possible index
    for i in range(len(nums)):
        if nums[i] == 0 and i == farthest:
            return False
        farthest = max(farthest, i + nums[i])
        if farthest >= target:
            return True

    return farthest >= target

# Time complexity: O(n)
# Space complexity: O(1)
def jump(nums: List[int]) -> int:
    answer = currFarthest = currEnd = 0

    # Find max jumps and track jump count
    for i in range(len(nums) - 1):
        currFarthest = max(currFarthest, nums[i] + i)
        # Loop excludes last index because if currEnd >= end,
        # this conditional will unnecessarily increment the answer
        if i == currEnd:
            answer += 1
            # currEnd becomes max distance of previous jump
            currEnd = currFarthest
    return answer

# Time complexity: O(n)
# Space complexity: O(n)
def hIndex(citations: List[int]) -> int:
    buckets = [0] * (len(citations) + 1)
    # Example: If current val = 2, increment buckets[2] by 1
    # Essentially, buckets index tracks frequency
    for val in citations:
        if val >= len(citations):
            buckets[-1] += 1
        else:
            buckets[val] += 1

    count = 0
    for i in range(len(buckets) - 1, -1, -1):
        count += buckets[i]
        # Example: count = i = 3 means at least 3 papers were cited 3 times
        if count >= i:
            return i
    return 0

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.indexMap = {}

    def insert(self, val: int) -> bool:
        if val in self.indexMap:
            return False
        self.indexMap[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.indexMap:
            return False
        # Swap val with last element in nums
        valIndex = self.indexMap[val]
        if valIndex < len(self.nums) - 1:
            self.nums[valIndex] = self.nums[-1]
            self.indexMap[self.nums[-1]] = valIndex
        # Remove last element
        self.nums.pop()
        del self.indexMap[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

Solution logic:

• The answer can be derived by creating two arrays: prefix and suffix.
• prefix[i] contains the product of all elements before i.
• suffix[i] contains the product of all elements after i.
• answer[i] = prefix[i] * suffix[i]
• Space can be optimized by using the answer array to build both prefix and suffix.
• Iterate normally through answer while keeping track of a prefix total.
• Then iterate backwards while keeping track of a suffix total.

# Time complexity: O(n)
# Space complexity: O(1) excluding output
def productExceptSelf(nums: List[int]) -> List[int]:
    answer = [1 for _ in nums]

    product = 1
    for i in range(len(nums)):
        answer[i] *= product
        product *= nums[i]

    product = 1
    for i in range(len(nums) -  1, -1, -1):
        answer[i] *= product
        product *= nums[i]

    return answer

# Time complexity: O(n)
# Space complexity: O(1)
def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
    if sum(gas) < sum(cost): return -1

    # An answer is guaranteed at this point
    net = idx = 0
    for i in range(len(gas)):
        net += gas[i] - cost[i]
        # If net becomes negative, the answer must be at least after i
        # Essentially looking for largest net positive subarray
        #   that includes last element
        if net < 0:
            net = 0
            idx = i + 1
    return idx

# Time complexity: O(n)
# Space complexity: O(1)
def intToRoman(num: int) -> str:
    pairs = [
        (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")
    ]
    answer = []

    for pair in pairs:
        while num >= pair[0]:
            answer.append(pair[1])
            num -= pair[0]

    return "".join(answer)

# Time complexity: O(n)
# Space complexity: O(n)
def reverseWords(s: str) -> str:
    answer = []
    start = end = len(s) - 1

    while start >= 0:
        # Skip whitespace
        while s[start] == " ":
            start -= 1
            end -= 1
        # In case string starts with whitespace
        if start < 0:
            break
        # Find next word
        while start >= 1 and s[start - 1] != " ":
            start -= 1
        answer.append(s[start:end + 1])
        start -= 1
        end = start

    return " ".join(answer)

# Time complexity: O(n)
# Space complexity: O(n)
def convert(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s

    # 2D matrix representing zigzag
    answer = [[] for _ in range(numRows)]

    # Sequentially place characters into the appropriate row
    i = 0
    while i < len(s):
        # Filling in columns
        for idx in range(numRows):
            if i >= len(s):
                break
            answer[idx].append(s[i])
            i += 1
        # Filling in diagonals
        for idx in range(numRows - 2, 0, -1):
            if i >= len(s):
                break
            answer[idx].append(s[i])
            i += 1

    return "".join(["".join(row) for row in answer])

Alternative solution:

• This solution relies on finding the numerical pattern between indices per row.
• To see the pattern, create the expected output and zigzag for cases numRows = 3, 4, and 5.

# Time complexity: O(n)
# Space complexity: O(n)
def convert(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s

    answer = []
    # Index difference between columns in the same row
    offset = numRows * 2 - 2

    # Handle first row
    i = 0
    while i < len(s):
        answer.append(s[i])
        i += offset

    for i in range(1, numRows - 1):
        # Middle rows will have alternating index differences
        flip = False
        offset1 = (numRows - i - 1) * 2
        offset2 = offset - offset1
        idx = i
        while idx < len(s):
            answer.append(s[idx])
            idx += offset2 if flip else offset1
            flip = not flip

    # Handle last row
    i = numRows - 1
    while i < len(s):
        answer.append(s[i])
        i += offset

    return "".join(answer)

# Time complexity: O(n)
# Space complexity: O(1)
def maxSubArray(nums: List[int]) -> int:
    answer = float("-inf")
    currSum = 0

    for n in nums:
        # If new value does not lead to larger currSum,
        #   reset currSum and start new subarray
        currSum = max(n, currSum + n)
        answer = max(answer, currSum)
    return answer

Solution logic:

• The maximum sum subarray is either contiguous or wraps around the circular array.
• Find the potentially contiguous subarray using Kadane's algorithm.
• To find the wrapping subarray, get the contiguous minimum sum and subtract from the array total sum.
  • total = min array + max array --> max array = total - min array
• Note that only computing (total - min array) is not enough to find the maximum sum subarray. If the maximum sum subarray is contiguous, the minimum sum subarray wraps and will not be found by Kadane's algorithm.

# Time complexity: O(n)
# Space complexity: O(1)
def maxSubarraySumCircular(nums: List[int]) -> int:
    total = 0
    maxSum = minSum = nums[0]
    currMax = currMin = 0

    # Use Kadane's algorithm to get both minimum and maximum sum subarrays
    for n in nums:
        total += n

        currMax = max(n, currMax + n)
        maxSum = max(maxSum, currMax)

        currMin = min(n, currMin + n)
        minSum = min(minSum, currMin)

    # Edge case: If all ints are negative, (total - minSum) == 0
    #   and maxSum will be negative, resulting in a return of 0
    if maxSum <= 0:
        return maxSum
    return max(maxSum, total - minSum)