Coding Exercise – Four Sum

Four Sum – for this coding exercise, we’re going to solve the following:

Example:

Solution in – SWIFT

class Platini {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let sortedNums = nums.sorted()
        var result = [[Int]]()

        for (index, num) in sortedNums.enumerated() {
            if index > 0 && num == sortedNums[index - 1] {
                continue
            }

            var secIndex = index + 1
            while secIndex < sortedNums.count { if secIndex > index + 1 && sortedNums[secIndex] == sortedNums[secIndex - 1] {
                    secIndex += 1
                    continue
                }

                var thirdIndex = secIndex + 1
                var lastIndex = sortedNums.count - 1
                while thirdIndex < lastIndex {
                    let sum = num + sortedNums[secIndex] + sortedNums[thirdIndex] + sortedNums[lastIndex]
                    if sum == target {
                        result.append([num, sortedNums[secIndex], sortedNums[thirdIndex], sortedNums[lastIndex]])
                        while thirdIndex < lastIndex && sortedNums[thirdIndex] == sortedNums[thirdIndex + 1] {
                            thirdIndex += 1
                        }
                        while thirdIndex < lastIndex && sortedNums[lastIndex] == sortedNums[lastIndex - 1] { lastIndex -= 1 } thirdIndex += 1 lastIndex -= 1 } else if sum > target {
                        lastIndex -= 1
                    } else {
                        thirdIndex += 1
                    }
                }
                secIndex += 1
            }
        }
        return result
    }
}

Solution in – JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  nums.sort((n1, n2) => n1 - n2)
  const result = []

  const findSum = (start, end, num, arr) => {
    let i = start
    let j = end
    while (i < j) {
      const sum = nums[i] + nums[j]
      if (sum <= num) {
        if (sum === num) result.push([...arr, nums[i], nums[j]])
        while (i < end && nums[i] === nums[i + 1]) i += 1 i += 1 } else { while (j > start && nums[j] === nums[j - 1]) j -= 1
        j -= 1
      }
    }
  }

  for (let i = 0; i < nums.length - 3; i += 1) { if (nums[i] === nums[i - 1]) continue for (let j = nums.length - 1; j > i + 2; j -= 1) {
      if (nums[j] === nums[j + 1]) continue
      const remain = target - nums[i] - nums[j]
      findSum(i + 1, j - 1, remain, [nums[i], nums[j]])
    }
  }
  return result
}

Solution in – Ruby

def three_sum(nums, start, target, pre_num)
  results = []
  index = start

  while index < nums.size - 2 do num = nums[index] if index > start && num == nums[index -1] then
      index += 1
      next
    end

    i = index + 1
    j = nums.size - 1

    while i < j do sum = nums[i] + nums[j] + num if sum > target then
        j -= 1
        while i < j && nums[j] == nums[j + 1] do
          j -= 1
        end
      elsif sum < target then
        i += 1
        while i < j && nums[i] == nums[i - 1] do
          i += 1
        end
      else
        results.push([pre_num, num, nums[i], nums[j]])
        i += 1
        j -= 1

        while i < j && nums[i] == nums[i - 1] do
          i += 1
        end
        while i < j && nums[j] == nums[j + 1] do
          j -= 1
        end
      end
    end

    index += 1
  end

  return results
end

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[][]}
def four_sum(nums, target)
  nums.sort!
  results = []

  i = 0
  while i < nums.size - 3 do
    num = nums[i]
    if i == 0 || num != nums[i - 1] then
      results += three_sum(nums, i + 1, target - num, num)
    end
    i += 1
  end

  return results
end