leetCodeArray.swift

// 238. Product of Array Except Self
// Link: https://leetcode.com/problems/product-of-array-except-self/
func productExceptSelf(_ nums: [Int]) -> [Int] {
      let count = nums.count
      var result = Array(repeating: 1, count: count)

      for i in 1..<count {
          result[i] = result[i - 1] * nums[i - 1]
      }

      var rightProduct = 1
      for i in stride(from: count - 2, to: -1, by: -1) {
          rightProduct *= nums[i + 1]
          result[i] = result[i] * rightProduct
      }

      return result
 }


// Problem 15. 3Sum
// Link: https://leetcode.com/problems/3sum
// Time: O(n^2) Space: O(nC3)
func threeSum(_ nums: [Int]) -> [[Int]] {
  if nums.count < 3 { return [] }
  var solutions = [[Int]]()
  let sorted = nums.sorted()

  for x in 0..<sorted.count-2 {
      if (sorted[x] > 0) { break } // trick to improve performance
      var y = x + 1
      var z = sorted.count - 1

      if x > 0 && sorted[x] == sorted[x - 1] { continue }

      while y < z {
          if sorted[x] + sorted[y] + sorted[z] < 0 {
              y += 1
          } else if sorted[x] + sorted[y] + sorted[z] > 0 {
              z -= 1
          } else { // found a solution
              solutions.append([sorted[x], sorted[y], sorted[z]])
              while (y < z && sorted[y + 1] == sorted[y]) { y += 1 } 
              while (y < z && sorted[z - 1] == sorted[z]) { z -= 1 } 
              y += 1
              z -= 1
          }
      }
  }

  return solutions
}


// 56. Merge Intervals
// Link: https://leetcode.com/problems/merge-intervals
// Time: nlogn, Space: O(n)
func merge(_ intervals: [[Int]]) -> [[Int]] {
  if intervals.count <= 1 { return intervals }

  var sorted = intervals.sorted { $0[0] < $1[0] }
  var merged = [[Int]]()
  var temp = sorted[0]

  for interval in sorted {
      if temp[1] >= interval[0] {
          temp[1] = max(temp[1], interval[1])
      } else {
          merged.append(temp)
          temp = interval
      }
  }

  merged.append(temp)

  return merged
}



// 49. Group Anagrams
// Link: https://leetcode.com/problems/group-anagrams/
// Time: n*m, Space n
func groupAnagrams(_ strs: [String]) -> [[String]] {
  var dict = [String: [String]]() // n

  for str in strs { // n
      var charCounts: [Int] = Array(repeating: 0, count: 26)
      for char in str { // m
          let index = Int(char.unicodeScalars.first!.value - "a".unicodeScalars.first!.value)
          charCounts[index] += 1
      } 
      let key = charCounts.map{ String($0) }.joined() // 26
      dict[key, default: []].append(str)
  }

  return Array(dict.values)
}

// Time: n*mlogm, Space: n
func groupAnagrams(_ strs: [String]) -> [[String]] {
  var dict = [String: [String]]() // n

  for str in strs { // n
      let sortedString = String(str.sorted()) // mlogm

      dict[sortedString, default: []].append(str)
  }

  return Array(dict.values)
}



// 33. Search in Rotated Sorted Array
// https://leetcode.com/problems/search-in-rotated-sorted-array
// Time logn, Space 1
func search(_ nums: [Int], _ target: Int) -> Int {
  if nums.isEmpty { return -1 }

  var left = 0
  var right = nums.count - 1

  while left < right {
      // avoid integer overflow (left + right may overflow to a negative number)
      let mid = ((right - left) / 2) + left
      let midNum = nums[mid]
      if target == midNum { return mid }
      let leftNum = nums[left]
      let rightNum = nums[right]

      if leftNum <= midNum {
          if leftNum <= target && target < midNum {
              right = mid - 1
          } else {
              left = mid + 1
          }
      } else {
          if midNum < target && target <= rightNum {
              left = mid + 1
          } else {
              right = mid - 1
          }
      }
  }

  return nums[left] == target ? left : -1
}


// 11. Container With Most Water
// Link: https://leetcode.com/problems/container-with-most-water/
// a max Product = a product of maximized numbers
// Time: O(n), Space O(1)
func maxArea(_ height: [Int]) -> Int {
  var maxArea = 0
  var left = 0
  var right = height.count - 1
  while left < right {
      let area = (right - left) * min(height[left], height[right])
      if area > maxArea { maxArea = area }
      if height[left] > height[right] { right -= 1 }
      else { left += 1 }
  }

  return maxArea
}



// 153. Find Minimum in Rotated Sorted Array
// Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
// Time: O(logn), Space: O(1)
func findMin(_ nums: [Int]) -> Int {
  var minNum = Int.max
  var left = 0
  var right = nums.count - 1

  while left < right {
      if nums[left] <= nums[right] { return nums[left] }
      // avoid integer overflow
      let mid = (right - left) / 2 + left

      if nums[left] <= nums[mid] {
          left = mid + 1
      } else {
          right = mid
      }
  }

  return nums[left]
}



// https://leetcode.com/problems/non-overlapping-intervals/
// Time: nlogn, Space 1
func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
  if intervals.count < 2 { return 0 }
  let sorted = intervals.sorted{ $0[1] < $1[1] }
  var max = 1
  var end = sorted[0][1]

  for i in 1..<sorted.count {
      if sorted[i][0] >= end {
          end = sorted[i][1]
          max += 1
      }
  }

  return intervals.count - max
}