Leetcode

Max area

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
  let left = 0
  let right = height.length - 1
  let area = 0

  while (left < right) {
    area = Math.max(
      area,
      Math.min(height[left], height[right]) * (right - left),
    )

    if (height[left] < height[right]) {
      left += 1
    } else if (height[left] > height[right]) {
      right -= 1
    } else {
      left += 1
      right -= 1
    }
  }

  return area
}

2 pointers at the start and end of the array give us the widest container. As the area is constrained by the shorter line, moving the pointer at the shorter height will reduce the width but possibly increase the height, hence bigger area.

O(n) time as 1 pass, O(1) space.

Contains duplicates

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const containsDuplicate = (nums) => {
  const uniqueNums = new Set()

  for (let num of nums) {
    if (uniqueNums.has(num)) {
      return true
    }
    uniqueNums.add(num)
  }

  return false
};

I was using {} as a dictionary to keep track of unique numbers, and forgot about set.

O(n) time as 1 pass, O(n) space.

Max subarray

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = (nums) => {
  let currMax = 0
  let maxTillNow = -Infinity

  for (let num of nums) {
    currMax = Math.max(num, currMax + num)
    maxTillNow = Math.max(maxTillNow, currMax)
  } 

  return maxTillNow 
}

currMax holds the max subarray total at index i. At every index, check if max total at index i-1 + nums[i] is higher than nums[i]. maxTillNow keeps track of the max we have seen so far.

I only knew of this elegant solution by checking the answers.

O(n) time and O(1) space.

Buy and sell stock 1

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {
  let lowestPrice = +Infinity
  let maxProfitSeen = 0

  for (let price of prices) {
    maxProfitSeen = Math.max(maxProfitSeen, price - lowestPrice)
    lowestPrice = Math.min(lowestPrice, price)
  }

  return maxProfitSeen
}

Keep track of the lowest price seen, and calculate the max profit if sold every day with the lowest price.

O(n) time and O(1) space.

2Sum

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  const memo = new Map()

  for (let i = 0; i < nums.length; i++) {
    const toFind = target - nums[i]

    if (memo.has(toFind)) {
        return [i, memo.get(toFind)]
    }

    memo.set(nums[i], i)
  }

  return []
}

Use a map to to save the number and its index to speed up looking up. O(n) time and O(n) space.

3Sum

/**
* @param {number[]} nums
* @return {number[][]}
*/
const threeSum = (nums) => {
const res = []

nums.sort((a,b) => a - b)

for (let i = 0; i < nums.length - 2; i++) {
  // first num is positive, can't sum to 0
  if (nums[i] > 0) break;

  // skip duplicates nums[i]
  if (i !== 0 && nums[i] === nums[i-1]) {
    continue;
  }

  let j = i + 1
  let k = nums.length - 1

  while (j < k) {
    if (nums[i] + nums[j] + nums[k] === 0) {
      res.push([nums[i], nums[j], nums[k]])
      j += 1
      k -= 1

      // skip duplicates nums[j]
      while (j < k && nums[j] === nums[j-1]) {
          j += 1
      }
      // skip duplicates nums[k]
      while (j < k && nums[k] === nums[k+1]) {
          k -= 1
      }
    } else if (nums[i] + nums[j] + nums[k] > 0) {
      k -= 1
    } else {
      j += 1
    }
  }
}
return res
}

Sorted the array. Calculate the sum, if the sum is positive, decrease the sum by moving right index (k) to the left. If the sum is negative, increase the sum by moving left index (j) to the right.

O(n^2) time, O(n) space.