LeetCode 15. 3Sum

LeetCode Problem No.15

No.14 is here

modalsoul.hatenablog.com

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2

Input: nums = []
Output: []

Example 3

Input: nums = [0]
Output: []

Code 1

object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
        nums.combinations(3).flatMap(x => if(x.sum == 0) Some(x.toList) else None).toList
    }
}

Methods

• Make all combinations and check sum.

Results

315 / 318 test cases passed. Status: Memory Limit Exceeded

Code 2

object Solution {
  def threeSum(nums: Array[Int]): List[List[Int]] = {
    val sorted = nums.sorted
    var result = List.empty[List[Int]]
    for(i <- 0 until nums.length-2) {
      val head = sorted(i)
      var left = i+1
      var right = nums.length-1
      if(i == 0 || sorted(i-1) < sorted(i)) {
        while(left < right) {
          if(head+sorted(left)+sorted(right) == 0) {
            result = result :+ List(head, sorted(left), sorted(right))
            left = left+1
            right = right-1
            while(left < right && sorted(right+1) == sorted(right)) {
              right = right-1
            }
          } else if(head+sorted(left)+sorted(right) < 0) left = left+1
          else right = right-1
        }
      }
    }
    result
  }
}

Methods

This problem is similar to No. 11.

modalsoul.hatenablog.com

• Sort given array.
• Take a variable(i) from array in order, and make sub-array(like tail)
  • Skip while i and i-1 are equivalent.
  • Left starts with head of sub-array.
  • Right starts with last of sub-array.
  • If sum of triplets is
    • 0
      • Shift left and right.
      • Skip right while same value.
    • under 0
      • Shift left.
    • over 0
      • Shift right.

Results

Runtime: 2654 ms, faster than 51.47% of Scala online submissions for 3Sum. Memory Usage: 733.3 MB, less than 6.62% of Scala online submissions for 3Sum.