let matrix1 = [[1,2,3],
               [2,3,4],
               [3,4,5]]

// min col max row = 3
// max col min row = 3

let matrix2 = [[1,5,2],
               [5,7,5],
               [4,5,8],
               [1,1,1],
               [3,3,3]]

// min col max row = 1
// max col min row = 5

let matrix10 = [[5,4,2,8],
                [8,1,7,9],
                [5,9,4,8]]


let matrix11 = [[1,2,3],
                 [2,3,4],
                 [3,4,5]]

func quicksort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }

    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }

    return quicksort(less) + equal + quicksort(greater)
}

func getSaddlePoints(from input: [[Int]]) {

    for (index, array) in input.enumerated()  {
        let maxInRow = maxPointInRow(from: array)
        let indexOfMaxInRow = input[index].firstIndex(of: maxInRow)
        let minInCol = minPointInColumn(from: formColumn(from: input, index: indexOfMaxInRow!))
        if maxInRow == minInCol {
            print(maxInRow)
        }

        let minInRow = minPointInRow(from: array)
        let indexOfMixInRow = input[index].firstIndex(of: minInRow)
        let maxInCol = maxPointInColumn(from: formColumn(from: input, index: indexOfMixInRow!))
        if minInRow == maxInCol {
            print(minInRow)
        }
    }
}

func formColumn(from input: [[Int]], index:Int) -> [Int]{
    var column = [Int]()
    for array in input {
        column.append(array[index])
    }
    return column
}

func minPointInColumn(from input: [Int]) -> Int {
    return quicksort(input).first!
}

func maxPointInColumn(from input: [Int]) -> Int {
    return quicksort(input).last!
}

func minPointInRow(from input: [Int]) -> Int {
    let sorted = quicksort(input)
    return sorted.first!
}

func maxPointInRow(from input: [Int]) -> Int {
    let sorted = quicksort(input)
    return sorted.last!
}

getSaddlePoints(from: matrix1)