Problem: Given a array of distinct integers, how many triple integers sum to exactly zero

Threesumtozero.swift

//
//  ComputationalGeometry.swift//
//  Created by James Rochabrun on 5/2/17.
//
//

import Foundation

//types of algorhitms
//1) constant -> 1   (1)
// a = b + c

//2) logarithmic -> log N   (~1)
//bynary search

//3) linear -> N    (2)
//loop

//4) linearithmic -> N log N (~2)
//mergesort

//5) quadratic -> N^2  (4)
//double loop

//6) cubic -> n^3 (8)
//triple loop

//7) exponential -> 2^N     T(N)
//exhaustive search

//Binary search algorithm : logarithmic

//brut algorithm three sum problem
//Problem: Given a array of distinct integers, how many triple integers sum to exactly zero

let integers = [-50,-40, 10, 30, 40, 50, -20, -10, 0, 5]

//Step 1 sort Array
let sortedArray = integers.sorted()

//(n ^ 3) cubic solution
func findTripleSumEqualZero(in integers: [Int]) -> Int {
    
    let n = integers.count
    var count = 0
    var a = 0
    var b = 0
    var c = 0
    for i in 0..<n {
        a += 1
        for j in (i + 1)..<n {
            b += 1
            for  k in (j + 1)..<n {
                c += 1
                if integers[i] + integers[j] + integers[k] == 0 {
                    count += 1
                    print("[\(integers[i]),\(integers[j]),\(integers[k])]")
                }
            }
        }
    }
   // print(a,b,c)
    return count
}
print("brutCount:", findTripleSumEqualZero(in: sortedArray))

//implementing a binary search - log N
func find(value: Int, in array: [Int]) -> Int {
    
    var leftIndex = 0
    var rightIndex = array.count - 1
    
    while leftIndex <= rightIndex {
        
        let middleIndex = (leftIndex + rightIndex) / 2
        let middleValue = array[middleIndex]
        
        if middleValue == value {
            return middleIndex
        }
        if value < middleValue {
            rightIndex = middleIndex - 1
        }
        if value > middleValue {
            leftIndex = middleIndex + 1
        }
    }
    return 0
}

//refactoring the three sum problem in to N^2 log N

func findTripleSumEqualZeroBinary(in integers: [Int]) -> Int {

    let n = integers.count
    var count  = 0
    
    //loop the array twice N^2
    for i in 0..<n {
        for j in (i + 1)..<n {
            //Sum the first pair and assign it as a negative value
            let twoSum = -(integers[i] + integers[j])
           // perform a binary search log N
            // it will return the index of the give number, this replaces the third loop
            let index = find(value: twoSum, in: integers)
            //to avoid duplications we need to do this check by checking the items at correspondingly indexes
            if (integers[i] < integers[j] &&  integers[j] < integers[index]) {
                print("\([integers[i], integers[j], integers[index]])")
                count += 1
            }
        }
    }
    return count
}

print("count:", findTripleSumEqualZeroBinary(in: sortedArray))