LeetCode in Swift: Max Points on a Line

Problem Statement

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

My Solution in Swift

The basic idea is to calculate gradient of every pair of points, and group points with same gradient. The final answer is then the size of the largest group. This results in an O(n²) algorithm. However, we could do it in a smarter way. When we have considered all possible pairs involving a given point, we don’t have to consider that point again. Also, when the current largest group size is x, we don’t have to consider the rest points.count – x number of points anymore. Although this improves the best case to O(n), on average, the algorithm is still in O(n²).

With proper implementation (pre-specify Dictionary capacity and keep the capacity when resetting), my Swift code runs pretty fast. It is actually faster than my friend’s C++ implementation compiling with -Ofast optimisation flag.

func maxPoints(points: [(Int, Int)]) -> Int {
    var lines: [Double:Int] = Dictionary(minimumCapacity: points.count)
    var maxNum = 0
    for var i = 0; i < points.count - maxNum; ++i {
        var curMaxNum = 1
        var sameCount = 0
        for var j = i + 1; j < points.count; ++j {
            let (x1, y1) = points[i]
            let (x2, y2) = points[j]
            
            if x1 == x2 && y1 == y2 {
                sameCount++
            } else {
                let slope: Double = x2 == x1 ? Double.infinity : Double(y2 - y1) / Double(x2 - x1)
                var line: Int! = lines[slope]
                if line != nil {
                    lines[slope] = ++line!
                } else {
                    line = 2
                    lines[slope] = line
                }
                curMaxNum = max(line, curMaxNum)
            }
        }
        maxNum = max(maxNum, curMaxNum + sameCount)
        lines.removeAll(keepCapacity: true)
    }
    return maxNum
}

func maxPoints(points: [(Int, Int)]) -> Int {

var lines: [Double:Int] = Dictionary(minimumCapacity: points.count)

var maxNum = 0

for var i = 0; i < points.count - maxNum; ++i {

var curMaxNum = 1

var sameCount = 0

for var j = i + 1; j < points.count; ++j {

let (x1, y1) = points[i]

let (x2, y2) = points[j]

if x1 == x2 && y1 == y2 {

sameCount++

} else {

let slope: Double = x2 == x1 ? Double.infinity : Double(y2 - y1) / Double(x2 - x1)

var line: Int! = lines[slope]

if line != nil {

lines[slope] = ++line!

} else {

line = 2

lines[slope] = line

}

curMaxNum = max(line, curMaxNum)

}

maxNum = max(maxNum, curMaxNum + sameCount)

lines.removeAll(keepCapacity: true)

}

return maxNum

}

Try It Yourself

1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:

$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution

The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)

Problem¹	Time²	Test Cases³	My Xcode Project⁴
Max Points on a Line	3.648ms	Save (1864)	Save (1867)

Guan Gui

Prove Logs on Blockchain with Go and ProvenDB

FileHeader for Atom

A Beautiful Linear Time Python Regex Matcher via NFA

LeetCode in Swift: Max Points on a Line

Problem Statement

My Solution in Swift

Try It Yourself

More Problems Solved in Swift

Prove Logs on Blockchain with Go and ProvenDB

FileHeader for Atom

A Beautiful Linear Time Python Regex Matcher via NFA

Problem Statement

My Solution in Swift

Try It Yourself

More Problems Solved in Swift

Share this:

Leave a Reply Cancel reply