Practice Arrays

Two Sum

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Brute-force approach: Use a nested loop to check every pair of numbers. Time complexity: O(n²).

Optimized approach: Use a hash map (or a dictionary in Python) to store the numbers you've seen and their indices. For each number, check if target - number is in the hash map. This improves the time complexity to O(n) because hash map lookups are O(1) on average.

# Python
def two_sum(nums, target):
  num_map = {}
  for i, num in enumerate(nums):
    complement = target - num
    if complement in num_map:
      return [num_map[complement], i]
    num_map[num] = i

Best Time to Buy and Sell Stock

Problem: You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to 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.

Approach: Iterate through the array while keeping track of the minimum price found so far (minPrice) and the maximum profit found so far (maxProfit). For each day, calculate the potential profit if you were to sell on that day (prices[i] - minPrice) and update maxProfit. Then, update minPrice if the current day's price is lower.

# Python
def max_profit(prices):
  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

Container With Most Water

Problem: You are 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, such that the container contains the most water.

Approach: This can be solved efficiently using the two-pointer technique. Start with a pointer at the beginning (left) and one at the end (right) of the array. The area is determined by the shorter of the two lines and the distance between them. To potentially find a larger area, you must move the pointer of the shorter line inwards, because moving the taller line's pointer can't increase the height of the container, it only decreases the width.

# Python
def max_area(height):
  max_area = 0
  left = 0
  right = len(height) - 1
  while left < right:
    width = right - left
    current_height = min(height[left], height[right])
    current_area = width * current_height
    max_area = max(max_area, current_area)
    if height[left] < height[right]:
      left += 1
    else:
      right -= 1
  return max_area