Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LintCode: Rectangle

Posted on February 25, 2018July 26, 2020 by braindenny

Rectangle



Similar Problems:

  • LeetCode: Minimum Area Rectangle
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #rectangle

Give a set, if you can find four points that make up a rectangle that is parallel to the coordinate axis and outputs YES or NO.

Notice
The number of points in the set is less than 2000, and the coordinate range is [-10000000,10000000].

Example

Given set = [[0,0],[0,1],[1,1],[1,0]], return YES.

Explanation:
We can find four points that make up a rectangle which is parallel to the coordinate axis.
Given set = [[0,0],[0,1],[1,1],[2,0]], return NO.

Explanation:
We can not find four points that meet the conditions

Github: code.dennyzhang.com

Credits To: LintCode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/rectangle
#!/usr/bin/env python
"""
class Point:
    def __init__( self, x=0, y=0):
        self.x = x
        self.y = y
"""
class Solution:
    """
    @param pointSet: The point set
    @return: The answer
    """
    def rectangle(self, pointSet):
        ## Basic Ideas:
        ##   a, b, c
        ##   a*a+b*b=c*c
        ## Complexity: Time O(1), Space O(1)
        if len(pointSet) != 4: return 'NO'
        l = []
        for i in range(4):
            for j in range(4):
                if i == j: continue
                l.append(pow(pointSet[i].x-pointSet[j].x, 2)+pow(pointSet[i].y-pointSet[j].y, 2))
        mySet = set(l)
        count = len(mySet)
        # print(mySet)
        if count!=2 and count!=3: return 'NO'
        v1, v2 = min(mySet), max(mySet)
        c1, c2 = 0, 0
        for num in l:
            if num == v1: c1 += 1
            if num == v2: c2 += 1
        if len(l)%4 != 0 or c1%4 != 0 or c2%4 != 0: return 'NO'
        if count == 2:
            return 'YES' if v2 == 2*v1 else 'NO'
        else:
            v3 = None
            for num in mySet:
                if num != v1 and num !=v2: v3 = num
            return 'YES' if v2 == v1+v3 else 'NO'
linkedin
github
slack

Post Views: 6
Posted in MediumTagged rectangle

Post navigation

LeetCode: Escape The Ghosts
LeetCode: Kill Process

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.