LeetCode Practice

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Each input has exactly one solution, and you may not use the same element twice.

To find two numbers \(a + b = \text{target}\), we rewrite it as \(b = \text{target} - a\). As we iterate through the array, we check if the required complement (\(\text{target} - \text{nums}[i]\)) already exists in a hash map. If it does, we return its index along with the current index. Otherwise, we store the current number and its index in the hash map.

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
    

Given an array prices where prices[i] is the price of a given stock on the \(i\)-th day, 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.

Track the minimum purchase price seen so far as you iterate through the prices. For each price, calculate the potential profit if sold on that day (\(\text{price} - \text{min\_price}\)). Keep updating the maximum profit seen.

def maxProfit(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit
    

Given an integer array nums, return True if any value appears at least twice in the array, and return False if every element is distinct.

Use a hash set to store elements as you iterate. If an element is already in the hash set, a duplicate exists. Alternatively, compare the length of the array to the length of a set created from the array.

def containsDuplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))
    

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], without using division and in \(O(N)\) time.

Compute prefix products and suffix products. First, pass from left to right to calculate the product of all elements to the left of each index. Then, pass from right to left, multiplying the prefix product with the running product of all elements to the right.

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [1] * n

    # Left prefix products
    prefix = 1
    for i in range(n):
        res[i] = prefix
        prefix *= nums[i]

    # Right suffix products
    postfix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= postfix
        postfix *= nums[i]

    return res
    

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Kadane's Algorithm: Iterate through the array maintaining a running current_sum. At each position, decide whether to add the current number to current_sum or start a new subarray starting at the current element (\(\max(\text{num}, \text{current\_sum} + \text{num})\)). Track the overall maximum.

def maxSubArray(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum
    

Given an integer array nums, find a subarray that has the largest product, and return the product.

Since multiplying two negative numbers creates a positive number, keep track of both the maximum product and the minimum product up to the current index. When encountering a negative number, the minimum and maximum swap roles.

def maxProduct(nums: list[int]) -> int:
    res = max(nums)
    curMin, curMax = 1, 1

    for n in nums:
        if n == 0:
            curMin, curMax = 1, 1
            continue
        tmp = curMax * n
        curMax = max(n * curMax, n * curMin, n)
        curMin = min(tmp, n * curMin, n)
        res = max(res, curMax)

    return res
    

Given the sorted rotated array nums of unique elements, return the minimum element of this array in \(O(\log N)\) time.

Use Binary Search. Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum must lie in the right half (left = mid + 1). Otherwise, the minimum lies in the left half including mid (right = mid).

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]
    

Given a rotated sorted array nums and an integer target, return the index of target if it is in nums, or -1 if it is not, in \(O(\log N)\) time.

Modify Binary Search. At least one half (left or right) of the array will always be strictly sorted. Determine which half is sorted, then check if target lies within that sorted half's range to decide where to search next.

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        # Left sorted portion
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right sorted portion
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
    

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that \(i \neq j, i \neq k, j \neq k\), and \(\text{nums}[i] + \text{nums}[j] + \text{nums}[k] == 0\).

Sort the array first. Iterate through each element as the first element of the triplet. For the remaining part of the array, use the Two-Pointer approach (left and right) to find pairs that sum to -nums[i]. Skip duplicate values to ensure unique triplets.

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    for i, a in enumerate(nums):
        if i > 0 and a == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            three_sum = a + nums[l] + nums[r]
            if three_sum > 0:
                r -= 1
            elif three_sum < 0:
                l += 1
            else:
                res.append([a, nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
    return res
    

Given \(n\) non-negative integers representing heights where each point is at \((i, \text{height}[i])\), find two lines that together with the x-axis form a container containing the most water.

Use Two Pointers starting at both ends of the array. The amount of water stored is determined by \(\text{width} \times \min(\text{height}[left], \text{height}[right])\). To maximize water, move the pointer pointing to the shorter height inward, as keeping the shorter height could never yield a larger area with a smaller width.

def maxArea(height: list[int]) -> int:
    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