939. Minimum Area Rectangle
You are given an array of points in the X-Y plane points where points[i]
= [, ].
Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes. If there is not any such rectangle, return 0.
Example 1:
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Example 2:
Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Constraints:
points.length
points[i].length == 2
All the given points are unique.
Solution
Brute Force Solution
Since we need to form a rectangle from different points, we can check all combinations of points to see if it forms a rectangle. Then, we return the minimum area from a rectangle formed with these points. One key point is that we need to make sure the rectangle has positive area.
Let denote the size of points
.
This algorithm runs in .
Full Solution
Let's try to optimize our algorithm to find all possible rectangles faster. One observation we can make is that a rectangle can be defined by two points that lie on one of the two diagonals.
Example
Here, the rectangle outlined in blue can be defined by the two red points at and . It can also be defined by the two points and that lie on the other diagonal.
The two defining points have to be a part of points
for the rectangle to exist. In addition, we need to check if the two other points in the rectangle exist in points
. Specifically, let's denote the two defining points as and . We'll need to check if and exist in points
. This is where we can use a hashmap to do this operation in . We'll also need to make sure the rectangle has positive area (i.e. ).
Now, instead of trying all combinations of different points from points
, we'll try all combinations of different points from points
to be the two defining points of the rectangle.
Time Complexity
In our algorithm, we check all combinations of different points in points
. Since each check runs in and there are combinations, this algorithm runs in .
Time Complexity: .
Space Complexity
Since we store integers in our hashmap, our space complexity is .
Space Complexity: .
C++ Solution
1class Solution {
2 public:
3 int minAreaRect(vector<vector<int>>& points) {
4 unordered_map<int, unordered_map<int, bool>> hashMap;
5 for (vector<int> point : points) { // add all points into hashmap
6 hashMap[point[0]][point[1]] = true;
7 }
8 int ans = INT_MAX;
9 for (int index1 = 0; index1 < points.size();
10 index1++) { // iterate through first defining point
11 int x1 = points[index1][0];
12 int y1 = points[index1][1];
13 for (int index2 = index1 + 1; index2 < points.size();
14 index2++) { // iterate through second defining point
15 int x2 = points[index2][0];
16 int y2 = points[index2][1];
17 if (x1 == x2 ||
18 y1 == y2) { // rectangle doesn't have positive area
19 continue;
20 }
21 if (hashMap[x1].count(y2) &&
22 hashMap[x2].count(
23 y1)) { // check if other points in rectangle exist
24 ans = min(ans, abs(x1 - x2) * abs(y1 - y2));
25 }
26 }
27 }
28 if (ans == INT_MAX) { // no solution
29 return 0;
30 }
31 return ans;
32 }
33};
Java Solution
1class Solution {
2 public int minAreaRect(int[][] points) {
3 HashMap<Integer, HashMap<Integer, Boolean>> hashMap = new HashMap<>();
4 for (int[] point : points) { // add all points into hashmap
5 if (!hashMap.containsKey(point[0])) {
6 hashMap.put(point[0], new HashMap<>());
7 }
8 hashMap.get(point[0]).put(point[1], true);
9 }
10 int ans = Integer.MAX_VALUE;
11 for (int index1 = 0; index1 < points.length;
12 index1++) { // iterate through first defining point
13 int x1 = points[index1][0];
14 int y1 = points[index1][1];
15 for (int index2 = index1 + 1; index2 < points.length;
16 index2++) { // iterate through second defining point
17 int x2 = points[index2][0];
18 int y2 = points[index2][1];
19 if (x1 == x2 || y1 == y2) { // rectangle doesn't have positive area
20 continue;
21 }
22 if (hashMap.get(x1).containsKey(y2)
23 && hashMap.get(x2).containsKey(y1)) { // check if other points in rectangle exist
24 ans = Math.min(ans, Math.abs(x1 - x2) * Math.abs(y1 - y2));
25 }
26 }
27 }
28 if (ans == Integer.MAX_VALUE) { // no solution
29 return 0;
30 }
31 return ans;
32 }
33}
Python Solution
Small note: You can use a set in python which acts as a hashset and essentially serves the same purpose as a hashmap for this solution.
1class Solution: 2 def minAreaRect(self, points: List[List[int]]) -> int: 3 min_area = 10 ** 9 4 points_table = {} 5 6 for x, y in points: # add all points into hashset 7 points_table[(x, y)] = True 8 9 for x1, y1 in points: # iterate through first defining point 10 for x2, y2 in points: # iterate through second defining point 11 if x1 > x2 and y1 > y2: # Skip looking at same point 12 if (x1, y2) in points_table and (x2, y1) in points_table: # check if other points in rectangle exist 13 area = abs(x1 - x2) * abs(y1 - y2) 14 if area: 15 min_area = min(area, min_area) 16 17 return 0 if min_area == 10 ** 9 else min_area 18
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.