Krdytkyu

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.

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.