Leetcode Random Challenge - Wk7 (Question15)

Cicero · Aug 21, 2017

Hello Droid....and other lurkers

A follow on problem to the first "Two Sum" question posted. This week, "3sum". Its apparently medium difficulty.

15. 3Sum - https://leetcode.com/problems/3sum/description/

Code:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Code:

For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

How it works/Rules:

We use the random question picker (sometimes), and all attempt it, one question a week.
No cheating/looking at the editorial solution until your soln is accepted on leetcode, and you're convinced you can't get it any quicker.
Language is up to you, this may help people appreciate other languages as well
Only post your time taken, language, and percentage of submissions beaten at first. Use spoiler+php tags for your code.

/inb4 threesome jokes

Hamster · Aug 21, 2017

/subs

Maybe if I get time this week

Cicero · Aug 22, 2017

This one is kicking my ass. Fml

[)roi(] · Aug 22, 2017

Cicero said:
This one is kicking my ass. Fml

Your previous 2Sum solution could help here; it's O(N) and iterating the 3rd value will be O(N) so the result should roughly be O(N * N)

Here's a spoiler hint if you need it:

Picking up from your recent O(N) solution to the 2Sum challenge.
We can solve 3Sum challenge by dividing this it into 2 steps; first we pick out a number that represents "c", and the 2nd step is to invoke 2Sum solution, feeding the target with (0 – c) from the equation a + b + c == 0, or written more appropriately as a + b == 0 - c. So basically if you calculate (0 - c); you can use 2sum to determine the 2 values that represent the sum of this.

As for Big O:
The first step would take O(N), the second one would also take O(N), too, so the combined time complexity would roughly be O(N * N). Except to avoid duplicates we should sort the input & use a set type structure (to avoid duplicates); roughly O(N log N) time. The end speed really comes down to reuse of structures; which as I will later explain has been a bit of challenge in Swift re bugs in Swift 3 (fixed in Swift 4 (but not supported yet by leet)

[)roi(] · Aug 22, 2017

By approaching this problem as an extension of the 2sum solution; I unfortunately hit a few Swift 3 bugs which ended up making my attempts really slow... mostly due to my less than ideal work arounds using COW (copy on write); here's a brief overview:

In Swift we can use the concept of an ArraySlice to segment out sections of an existing array without incurring the cost of COW, but unfortunately in Swift 3 a subscript bug hadn't been fixed until Swift 4, https://bugs.swift.org/browse/SR-5369
Generic limitations: Swift 3 was unable to support a type with inheritance whilst at the same time applying constraints, for example:

PHP:

extension Array: Hashable, Equatable where Element == Int { ... }

Which means we have to create a wrapper type for the protocol conformances to Hashable and Equatable (used to avoid set duplicates).

These two issues meant that both my approaches using 2Sum were not performant as we have to revert to Copy On Write (COW) twice. i.e. O(N * N) it certainly isn't. Nevertheless in Swift 4 it will be; but for pure interest sake I am still posting the code:
Work arounds for Swift bugs i.e. a non-performant version using 2Sum

PHP:

enum Result<E,A> {
  case Done(A)
  case Call(E, A)
}

func trampoline<E, A>(with fn: @escaping (E, A) -> Result<E, A>) -> ((E, A) -> A) {
  return { (value: E, accumulator: A) -> A in
    var result = fn(value, accumulator)
    while true {
      switch result {
      case let .Done(accumulator):
        return accumulator
      case let .Call(number, accumulator):
        result = fn(number, accumulator)
      }
    }
  }
}

func twoSum(_ nums: [Int], _ target: Int) -> [Int]
{
  let c = nums.count, m = c / 2
  var found = false
  let twoSumR = trampoline(with: { (n: (Int, Int), array: [Int]) -> Result<(Int, Int), [Int]> in
    guard n.0 < c && n.1 < c else { return .Done([]) }
    if target - nums[n.0] - nums[n.1] == 0 { found = true; return .Done([n.0, n.1]) }
    if n.0 == m - 1 || n.0 == c - 2 || found { return .Done([]) }
    if n.1 >= c - 2 { return .Call((n.0 + 1, n.0 + 2), array)}
    return .Call((n.0, n.1 + 1), array)
  })
  return c < 3 ? nums : twoSumR((0, 1), []) + twoSumR((m, m + 1), [])
}

// Swift 3 workaround due to current generics limitation;
// Extension of type 'Array' with constraints cannot have an inheritance clause
// re this doesn't work yet: "extension Array: Hashable where Element == Int { ... } "
struct ArrayHash {
  let values: [Int]
  init(_ values: [Int]) {
    self.values = values.sorted()
  }
  func sum() -> Int {
    return values.reduce(0, +)
  }
}

// Uniquely identify array of Int where order doesn't matter
extension ArrayHash: Hashable, Equatable {
  public var hashValue: Int {
    return self.values.reduce(5381) {
      ($0 << 5) &+ $0 &+ $1.hashValue    }
  }
  
  static func ==(lhs: ArrayHash, rhs: ArrayHash) -> Bool {
    return lhs.hashValue == rhs.hashValue
  }
}

func threeSum(_ nums: [Int]) -> [[Int]] {
  let c = nums.count
  guard c >= 3 else { return [] }
  guard c >= 4 else { let r = nums.reduce(0) { $0 + $1 }; return r == 0 ? [nums] : [] }
  var result = Set<ArrayHash>()
  let sortNums = nums
  print(sortNums)
  for i in 0 ..< c {
    // ArraySlice for performance reasons would be preferred, but in Swift 3 it has a subscript bug
    // https://bugs.swift.org/browse/SR-5369
    // Hence workaround using COW
    var cow = sortNums; cow.remove(at: i)
    for abc in ((0 ..< c).map { twoSum1(cow, 0 - sortNums[$0]) }) {
      guard abc.count > 1 else { continue }
      let p = ArrayHash([cow[abc[0]], cow[abc[1]], sortNums[i]])
      if p.sum() == 0 { result.insert(p) }
    }
  }
  return result.map { $0.values }
}

Here's an alternative 2sum / 3sum approach, however still not the fastest outcome; for many of the same reasons as above:

PHP:

// Swift 3 workaround due to current generics limitation;
// Extension of type 'Array' with constraints cannot have an inheritance clause
// re this doesn't work yet: "extension Array: Hashable where Element == Int { ... } "
struct ArrayHash {
  let values: [Int]
  init(_ values: [Int]) {
    self.values = values.sorted()
  }
  func sum() -> Int {
    return values.reduce(0, +)
  }
}

// Uniquely identify array of Int where order doesn't matter
extension ArrayHash: Hashable, Equatable {
  public var hashValue: Int {
    return self.values.reduce(5381) {
      ($0 << 5) &+ $0 &+ $1.hashValue    }
  }
  
  static func ==(lhs: ArrayHash, rhs: ArrayHash) -> Bool {
    return lhs.hashValue == rhs.hashValue
  }
}

func twoSum(_ nums: [Int], _ target: Int, _ startIdx: Int) -> [[Int]] {
  let c = num.count
  var result = Set<ArrayHash>()
  var set = Set<Int>()
  for i in startIdx ..< c {
    if set.contains(target - nums[i]) {
      result.insert(ArrayHash([target - nums[i], nums[i]]))
      set.remove(target - nums[i])
      set.remove(nums[i])
    }
    else
    {
      if i > startIdx && nums[i - 1] == nums[i] { continue }
      set.insert(nums[i])
    }
  }
  return result.map { $0.values }
}

func threeSum(_ nums: [Int]) -> [[Int]] {
  let c = nums.count
  let numsSorted = nums.sorted()
  var result = Set<ArrayHash>()
  for i in 0 ..< c {
    for abc in twoSum(numsSorted, 0 - numsSorted[i], i + 1) {
      let p = ArrayHash([abc[0], abc[1], numsSorted[i]])
      if p.sum() == 0 { result.insert(p) }
    }
  }
  return result.map { $0.values }
}

Note: a less costly version would be possible using an inout array between 3sum and 2sum; however as that would involve a code rewrite I decided instead to build an all in one solution; which finally was more optimised by avoiding these bugs:

Beats 100% of Swift submissions, time: 77ms

PHP:

func threeSum(_ nums: [Int]) -> [[Int]] {
  let c = nums.count
  var result = [[Int]]()
  let sNums = nums.sorted()
  for i in 0 ..< c {
    let target = sNums[i]
    guard !(i > 0 && sNums[i] == sNums[i - 1]) else { continue }
    var idx = (i + 1, c - 1)
    while idx.0 < idx.1 {
      let current = sNums[idx.0] + sNums[idx.1]
      if 0 - target == current {
        result.append([sNums[idx.0], sNums[idx.1], target])
        idx = (idx.0 + 1, idx.1 - 1)
        while idx.0 < idx.1 && sNums[idx.0] == sNums[idx.0 - 1] { idx.0 += 1 }
        while idx.0 < idx.1 && sNums[idx.1] == sNums[idx.1 + 1] { idx.1 -= 1 }
      }
      else if 0 - target > current { idx.0 += 1 }
      else { idx.1 -= 1 }
    }
  }
  return result
}

Cicero · Sep 1, 2017

Dammit, haven't forgotten about this challenge.

I'll finish my submission at the weekend and post the new challenge on Monday.

Join the MyBroadband community

Get started

Leetcode Random Challenge - Wk7 (Question15)

Cicero

Expert Member

Hamster

Resident Rodent

Cicero

Expert Member

[)roi(]

Executive Member

[)roi(]

Executive Member

Cicero

Expert Member