LeetCode Arrays

In this post, I’ll explore common array-based LeetCode questions, covering easy and medium difficulty levels.

Problem1: Two Sum

Problem Description: Given an array of integers and a target value, determine if there are two numbers in the array that add up to the target. Return the indices of the two numbers.
Example:
- Input: nums = [2, 7, 11, 15], target = 9
- Output: [0, 1] (Because 2 + 7 = 9)
There are many ways to solve this question, but for the sake of practicing arrays, we will include array-based solutions, which may not be the most optimized.

Using Arrays Using Dictionary

Using Arrays	Using Dictionary
`def two_sum(nums, target): for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return None` This method will be more straightforward but less efficient than using a dictionary. It involves using two loops to check every pair of numbers in the array to see if they add up to the target. 3/13	`def two_sum(nums, target): num_dict = {} for index, num in enumerate(nums): needed = target - num if needed in num_dict: return [num_dict[needed], index] else: num_dict[num] = index return None` In Python, a dictionary is a type of hash table that can map keys to values. For this problem, we can use a dictionary to remember the numbers we've seen in the array as well as their indices. We'll use this to store the array numbers as keys and their indices as values. 3/13
Sorting and Two Pointers
def two_sum(nums, target): # Use the first item of each tuple # (i.e., x[0]) as the basis for comparing tuples indexed_nums = [(num, i) for i, num in enumerate(nums)] indexed_nums.sort(key=lambda x: x[0]) left = 0 right = len(nums) - 1 while left < right: current_sum = indexed_nums[left][0] + indexed_nums[right][0] #[left][0] access the value # note: the tuple stored in form: (value,index) if current_sum == target: return [indexed_nums[left][1], indexed_nums[right][1]] elif current_sum < target: left += 1 else: right -= 1 return None First sort the array, then use two pointers to narrow down the search. If the sum is less than the target, move the left pointer forward. If the sum is greater than the target, move the right pointer backward.


def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

This method will be more straightforward but less efficient than using a dictionary. It involves using two loops to check every pair of numbers in the array to see if they add up to the target. 3/13


def two_sum(nums, target):
    num_dict = {}
    for index, num in enumerate(nums):
        needed = target - num
        if needed in num_dict:
          return [num_dict[needed], index]
        else:
          num_dict[num] = index
    return None

In Python, a dictionary is a type of hash table that can map keys to values. For this problem, we can use a dictionary to remember the numbers we've seen in the array as well as their indices. We'll use this to store the array numbers as keys and their indices as values. 3/13

Sorting and Two Pointers


  def two_sum(nums, target):
  # Use the first item of each tuple 
  # (i.e., x[0]) as the basis for comparing tuples
    indexed_nums = [(num, i) for i, num in enumerate(nums)]
    indexed_nums.sort(key=lambda x: x[0])
    left = 0
    right = len(nums) - 1

    while left < right:
      current_sum = indexed_nums[left][0] + indexed_nums[right][0]
      #[left][0] access the value
      # note: the tuple stored in form: (value,index)
      if current_sum == target:
        return [indexed_nums[left][1], indexed_nums[right][1]]
      elif current_sum < target:
        left += 1
      else:
        right -= 1
     
    return None

First sort the array, then use two pointers to narrow down the search. If the sum is less than the target, move the left pointer forward. If the sum is greater than the target, move the right pointer backward.

Problem2: Best Time to Buy and Sell Stock

Problem Description: You have an array where each element represents the price of a given stock on a single day. Find the maximum profit you can achieve by making a single transaction (buying once and selling once).
Example:
- Input: prices = [7, 1, 5, 3, 6, 4]
- Output: 5 (Buy on day 2 when the price is 1, sell on day 5 when the price is 6)

Brute Force One Pass

Brute Force	One Pass
`def max_profit(prices): max_profit = 0 for buy_days in range(len(prices)): for sell_days in range(buy_days+1, len(prices)): current_profit = prices[sell_days] - prices[buy_days] max_profit = max(current_profit, max_profit) return max(max_profit)` Easy to understand	`def max_profit(prices): min_price = float('inf') # Start with a very high initial minimum price max_profit = 0 for price in prices: min_price = min(min_price, price) # Keep track of the lowest buying price seen so far, # in this case every price will be the lowest price profit = price - min_price # Calculate potential profit if selling today max_profit = max(max_profit, profit) # Update max_profit if necessary return max_profit` Tracking the minimum price seen so far as we go through the price list. Using a infinite big value, so every value you see will be min price


def max_profit(prices):
  max_profit = 0
  for buy_days in range(len(prices)):
    for sell_days in range(buy_days+1, len(prices)):
      current_profit = prices[sell_days] - prices[buy_days]
      max_profit = max(current_profit, max_profit)
  return max(max_profit)

Easy to understand


def max_profit(prices):
    min_price = float('inf')  
    # Start with a very high initial minimum price
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)  
        # Keep track of the lowest buying price seen so far, 
        # in this case every price will be the lowest price
        profit = price - min_price         
        # Calculate potential profit if selling today
        max_profit = max(max_profit, profit)  
        # Update max_profit if necessary

    return max_profit

Tracking the minimum price seen so far as we go through the price list. Using a infinite big value, so every value you see will be min price

Problem3: Contains Duplicate

Problem Description: Determine if a given array of integers contains any duplicate elements.
Example:
- Input: nums = [1, 2, 3, 1]
- Output: true

Brute Force Using Set

Brute Force	Using Set
`def contains_duplicate(nums): n = len(nums) for i in range(n): for j in range(i+1,n): if nums[i] == nums[j]: return True return False` comparing every element in the array with every other element.	`def contains_duplicate(nums): seen = set() for num in nums: if num in seen: return True else: seen.add(num) return False` we can use a set to store these elements, because sets do not allow duplicate values. As we iterate through the array, we check if the current element is already in the set. If it is, this means we have found a duplicate, and we can return true


def contains_duplicate(nums):
  n = len(nums)
  for i in range(n):
    for j in range(i+1,n):
      if nums[i] == nums[j]:
        return True
  
  return False

comparing every element in the array with every other element.


def contains_duplicate(nums):
  seen = set()
  for num in nums:
    if num in seen:
      return True
    else:
      seen.add(num)
      
  return False

we can use a set to store these elements, because sets do not allow duplicate values. As we iterate through the array, we check if the current element is already in the set. If it is, this means we have found a duplicate, and we can return true

Problem4: Single Number

Problem Description: In an array where every number appears twice except for one, find the single number.
Example:
- Input: nums = [4, 1, 2, 1, 2]
- Output: 4

Brute Force ...TBD

Brute Force	...TBD
`def`	`def`

def

def

Problem5: Product of Array Except Self

Problem Description: Given an array of integers, calculate an output array where each element is the product of all the other elements in the input array without using division.
Example:
- Input: nums = [1, 2, 3, 4]
- Output: [24, 12, 8, 6]

Problem6: 3Sum

Problem Description: Find all unique triplets in an array that sum to zero.
Example:
- Input: nums = [-1, 0, 1, 2, -1, -4]
- Output: [[-1, -1, 2], [-1, 0, 1]]

Problem7: Spiral Matrix

Problem Description: Given an m x n matrix, return all elements of the matrix in spiral order.
Example:
- Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
- Output: [1,2,3,6,9,8,7,4,5]

Problem8: Container With Most Water

Problem Description: You are given an array representing heights of walls. Calculate the maximum amount of water that can be contained between any two walls, assuming they form a container.
Example:
- Input: heights = [1,8,6,2,5,4,8,3,7]
- Output: 49