Leetcode Problem: Construct the Rectangle
In this article I would be going over a solution to leetcode problem 492: Construct the Rectangle,
Two solutions were developed and I will be walking you through them
Solutuion 1
The function accepts a parameter area, in this example we would go with 16area = 16
Next we create our answer dictionary variable to hold the factors of the target areaad = {}
Also setup a temp list with maximum and minimum values of infinitytemp = [ float('inf'), float('-inf')]
First we wanna iterate over from 1 till the square root of the target area + 1 to avoid duplicatesfor 1,2...sqrt(16)+1 --> 5
For every iteration, if we find a factor of that number then we want to save it to the answer dictionary
# 16/1 # 16/2 # 16/3 # 16/4 ad = {'1':'16', '2':'8', '4':'4'}
Now we can iterate through the answer dictionary to select the best length and width combination with the lowest absolute difference
for k,v in ad: if abs(k-v) < abs(temp[0]-temp[1]) temp[0], temp[1] = min(k, v), max(k,v) return temp
At the end of this process we have the answer in temp list
Code Below
import mathclass Solution: def constructRectangle(self, area: int) -> List[int]: answer_dict = {} temp = [float('inf'), float('-inf')] for n in range(1, int(math.sqrt(area))+1): if area%n == 0: answer_dict[n] = area // n for k, v in answer_dict.items(): if abs(temp[0] - temp[1]) > abs(k-v): temp[0], temp[1] = max(k, v), min(k, v) return temp
The first solution was long and it could be made a lot simpler
This second solution makes use of one list to keep the prospective lengths and breadths
Easy to understand
class Solution: def constructRectangle(self, area: int) -> List[int]: ans = [] for i in range(1, int(sqrt(area))+1): j = area // i if i * j == area: if i <= j: ans.append([max(i,j), min(i,j)]) return ans[-1]
A little task for the readers, what is the time and space complexities of both solutions
Also do let me know if you have a better solution, or any improvements to be made
Happy Cocding :)
Original Link: https://dev.to/joshthecodingaddict/leetcode-problem-construct-the-rectangle-5fen
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To