Minimum Area Rectangle in Swift

Question

This is my solution to LeetCode – Minimum Area Rectangle in Swift

939. Minimum Area Rectangle

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
If there isn't any rectangle, return 0.

• Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output: 4

• Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

Output: 2

class Solution {
 struct Point_Dng: Hashable{
 var x: Int
 var y: Int
 
 init(_ x: Int, _ y: Int) {
 self.x = x
 self.y = y
 }
 
 var hashValue: Int{
 return x * 100000 + y
 }
 
 
 static func == (_ lhs: Point_Dng, _ rhs: Point_Dng) -> Bool{
 return lhs.x == rhs.x && lhs.y == rhs.y
 }
 }
 
 
 
 func minAreaRect(_ points: [[Int]]) -> Int {
 let points_new = points.map({ (point: [Int]) -> Point_Dng in
 return Point_Dng(point[0], point[1])
 })
 let set = Set(points_new)
 var ans = Int.max
 for point in points{
 
 for point_piece in points{
 
 
 if point[0] != point_piece[0] , point[1] != point_piece[1] , set.contains(Point_Dng(point[0], point_piece[1])) ,set.contains(Point_Dng(point_piece[0], point[1])) {
 
 ans = min(ans, abs((point_piece[1] - point[1] ) * (point_piece[0] - point[0])))
 }
 }
 }
 
 if ans == Int.max {
 return 0
 }
 else{
 return ans
 }
 }
}

Note:

1. 1 <= points.length <= 500

2. 0 <= points[i][0] <= 40000

3. 0 <= points[i][1] <= 40000

4. All points are distinct.

According to LeetCode's note, I improved the hash performance. I turned

var hashValue: Int{
 return "\(x)\(y)".hashValue
}

into

var hashValue: Int{
 return x * 100000 + y
}

because Swift's tuple is not hashable. The prior one will lead to "Time Limit Exceeded"

How can I improve it further?
In fact I want to know is there something I missed in Swift.
Something out of my knowledge.
Because I did it simple.

Answer 1

Naming

The meaning of some identifier names is hard to grasp:

• What does Point_Dng stand for? Why not simply Point?
• What is point_piece in the inner loop, and how is it different from piece from the outer loop?
• set is too generic, what does it contain?
• ans stands for "answer," but actually contains the "minimal area" found so far.

Simplifications

As of Swift 4.2, the compiler automatically creates the required methods for Equatable and Hashable conformance for a struct if all its member are Equatable/Hashable.

A struct also has a default memberwise initializer if you don't define your own.

The properties of a point are never mutated, so they can be declared as constants (with let).

This makes the struct Point as simple as

struct Point: Hashable {
 let x: Int
 let y: Int
}

The closure in

let points_new = points.map({ (point: [Int]) -> Point_Dng in
 return Point_Dng(point[0], point[1])
})

can be simplified because the compiler can infer the argument type and the return type automatically. Since the array is only needed for creating the set, the assignments can be combined into one:

let pointSet = Set(points.map { point in Point(x: point[0], y: point[1]) })

Performance improvements

In the nested loop it suffices to consider only those pairs where one point is the "lower left" and the other the "upper right" corner of a potential rectangle. That reduces the number of tests, and makes the abs() call redundant.

Putting it together

The following version was roughly twice as fast in my tests with random arrays of 500 points (on a 3.5 GHz Intel Core i5 iMac, compiled in Release mode, i.e. with optimizations):

class Solution {
 struct Point: Hashable {
 let x: Int
 let y: Int
 }
 func minAreaRect(_ points: [[Int]]) -> Int {
 let pointSet = Set(points.map { point in Point(x: point[0], y: point[1]) })
 var minArea = Int.max
 for lowerLeft in points {
 for upperRight in points {
 if upperRight[0] > lowerLeft[0]
 && upperRight[1] > lowerLeft[1]
 && pointSet.contains(Point(x: lowerLeft[0], y: upperRight[1]))
 && pointSet.contains(Point(x: upperRight[0], y: lowerLeft[1])) {
 let area = (upperRight[0] - lowerLeft[0]) * (upperRight[1] - lowerLeft[1])
 minArea = min(minArea, area)
 }
 }
 }
 return minArea == Int.max ? 0 : minArea
 }
}

Further suggestions

Sorting the point array in increasing order of x-coordinates would allow to find "lower left/upper right" pairs faster, potentially increasing the performance.

• ielyamani: Design: Should minAreaRect(_:) be a class/static function? Would a struct Solution be preferable to a class?
• Martin R: @Carpsen90: Generally yes, but the class and the instance method is given on the LeetCode problem page leetcode.com/problems/minimum-area-rectangle when you submit a solution in Swift.

Answer 2

Alternative Approach

Here is an alternative implementation that is currently the fastest on LeetCode:

1- First, let's create two dictionaries, one all for the abscissae (x-axis) and the other for the ordinates (y-axis) :

var xAxisDictionary: [Int:Set<Int>] = [:]
var yAxisDictionary: [Int:Set<Int>] = [:]

Each dictionary will store the indices of the elements of points that have a certain coordinate. Abscissae are the keys of xAxisDictionary. Ordinates are the keys of yAxisDictionary.

2- pointsCoordinates will store unique strings that would represent points, this is faster than creating a struct and relying on the automatic hashing system:

var pointsCoordinates: Set<String> = []

Using a set rather than an array gives better execution time. In fact, if an array is used, the time limit would be exceeded. As shown by the following graph, Array.contains is faster for less than 16 elements. SortedArray.contains would be the fastest from approximately 16 up to 256 elements. Set.contains is the fastest from 256 up to 500 points :

Contains

3- indicesToConsider is a set of indices of points that may be part of a rectangle :

var indicesToConsider: Set<Int> = []

4- Let's fill the dictionaries:

for (index, point) in points.enumerated() {
 if var set = xAxisDictionary[point[0]] {
 set.insert(index)
 xAxisDictionary[point[0]] = set
 } else {
 xAxisDictionary[point[0]] = Set([index])
 }
 if var set = yAxisDictionary[point[1]] {
 set.insert(index)
 yAxisDictionary[point[1]] = set
 } else {
 yAxisDictionary[point[1]] = Set([index])
 }
}

Notice that optional binding is done using if var for set to be mutable.

5- Then, we only keep points that may be part of a rectangle :

for (_, indicesSet) in xAxisDictionary {
 // A vertical side of a rectangle, as described in this problem, has to have two points with the same x coordinate
 if indicesSet.count < 2 {
 continue
 }
 // Likewise, a horizontal side of a rectangle, as described in this problem, has to have two points with the same y coordinate
 for pointIndex in indicesSet {
 if yAxisDictionary[points[pointIndex][1]]!.count > 1 {
 indicesToConsider.insert(pointIndex)
 pointsCoordinates.insert("\(points[pointIndex][0])_\(points[pointIndex][1])")
 }
 }
}

Force-unwrapping is safe here, it serves also for brevity.

6- Let's traverse the considered indices from smallest to largest :

let indicesToConsiderArray = indicesToConsider.sorted()

Using a sorted array makes a 500ms difference on LeetCode.

7- Initially, we'll consider that the minimum area is as big as possible :

var result = Int.max

The maximum value of result is 40_000 * 40_000 since all the coordinates belong to the interval [0, 40000].

On LeetCode, defining result as an integer, initially equal to Int.max, was little bit faster than: defining result as an optional integer initially equal to nil, updating it using result = min(abs((x2 - x1) * (y2 - y1)), result ?? Int.max), and returning result ?? 0.

8- Now, traverse the indicesToConsiderArray, and calculate the area of the rectangle which is confined between a bottom left corner, and a top right corner :

for pointIndex in indicesToConsiderArray {
 let x1 = points[pointIndex][0]
 let y1 = points[pointIndex][1]
 let xPeers = xAxisDictionary[x1]!
 let yPeers = yAxisDictionary[y1]!
 for xPeer in xPeers {
 if xPeer <= pointIndex {
 continue
 }
 let y2 = points[xPeer][1]
 for yPeer in yPeers {
 if yPeer <= pointIndex {
 continue
 }
 let x2 = points[yPeer][0]
 if pointsCoordinates.contains("\(x2)_\(y2)") {
 result = min(abs((x2 - x1) * (y2 - y1)), result)
 }
 }
 }
}

Looping through xPeers (or yPeers) could also be written this way :

for case let xPeer in xPeers where xPeer > pointIndex { ... }

Meanwhile, we update result if a smaller area is found.

9- At the end of our function, if the value of result isn't changed, then we'll return 0, meaning that no rectangle can be formed using points :

return result < Int.max ? result : 0

---

For convenience, here is the whole solution :

class Solution {
 func minAreaRect(_ points: [[Int]]) -> Int {
 var xAxisDictionary: [Int:Set<Int>] = [:]
 var yAxisDictionary: [Int:Set<Int>] = [:]
 var pointsCoordinates: Set<String> = []
 var indicesToConsider: Set<Int> = []
 for (index, point) in points.enumerated() {
 if var set = xAxisDictionary[point[0]] {
 set.insert(index)
 xAxisDictionary[point[0]] = set
 } else {
 xAxisDictionary[point[0]] = Set([index])
 }
 if var set = yAxisDictionary[point[1]] {
 set.insert(index)
 yAxisDictionary[point[1]] = set
 } else {
 yAxisDictionary[point[1]] = Set([index])
 }
 }
 for (_, indicesSet) in xAxisDictionary {
 if indicesSet.count < 2 {
 continue
 }
 for pointIndex in indicesSet {
 if yAxisDictionary[points[pointIndex][1]]!.count > 1 {
 indicesToConsider.insert(pointIndex)
 pointsCoordinates.insert("\(points[pointIndex][0])_\(points[pointIndex][1])")
 }
 }
 }
 let indicesToConsiderArray = indicesToConsider.sorted()
 var result = Int.max
 for pointIndex in indicesToConsiderArray {
 let x1 = points[pointIndex][0]
 let y1 = points[pointIndex][1]
 let xPeers = xAxisDictionary[x1]! //Force unwrapping is safe here
 let yPeers = yAxisDictionary[y1]! //and here
 for xPeer in xPeers {
 if xPeer <= pointIndex {
 continue
 }
 let y2 = points[xPeer][1]
 for yPeer in yPeers {
 if yPeer <= pointIndex {
 continue
 }
 let x2 = points[yPeer][0]
 if pointsCoordinates.contains("\(x2)_\(y2)") {
 result = min(abs((x2 - x1) * (y2 - y1)), result)
 }
 }
 }
 }
 return result < Int.max ? result : 0
 }
}

The execution time on LeetCode is 1472 ms :

100%

Compared to 3404 ms for the accepted answer (which is faster than 0.00%)