-
Notifications
You must be signed in to change notification settings - Fork 189
/
Program.java
102 lines (84 loc) · 2.68 KB
/
Program.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package AlgoExSolutions.VeryHard.ApartmentHunting;
import java.util.*;
/**
* * Apartment Hunting
*/
class Program {
/**
* * Optimized Approach
*
* * TC: O(br)
* * SC: O(br)
*/
public static int apartmentHunting(List<Map<String, Boolean>> blocks, String[] reqs) {
// Write your code here.
int locationIdx = -1, closestDistance = Integer.MAX_VALUE;
Map<String, List<Integer>> distances = preComputeDistances(blocks, reqs);
for (int i = 0; i < blocks.size(); i++) {
int currentDistance = Integer.MIN_VALUE;
for (String req : reqs)
currentDistance = Math.max(currentDistance, distances.get(req).get(i));
if (closestDistance > currentDistance) {
closestDistance = currentDistance;
locationIdx = i;
}
}
return locationIdx;
}
private static Map<String, List<Integer>> preComputeDistances(
List<Map<String, Boolean>> blocks, String[] reqs) {
int len = blocks.size();
Map<String, List<Integer>> cache = new HashMap<>();
for (String req : reqs) {
Integer[] minDistances = new Integer[len];
int minIdx = -1;
for (int i = 0; i < len; i++) {
if (blocks.get(i).get(req)) minIdx = i;
minDistances[i] = minIdx == -1 ? Integer.MAX_VALUE : distanceBetween(minIdx, i);
}
for (int i = len - 1; i >= 0; i--) {
if (blocks.get(i).get(req)) minIdx = i;
minDistances[i] = Math.min(minDistances[i], distanceBetween(minIdx, i));
}
cache.put(req, new ArrayList<>(Arrays.asList(minDistances)));
}
return cache;
}
private static int distanceBetween(int start, int end) {
return Math.abs(start - end);
}
/**
* * Brute Force Approach
*
* * TC: O(b^2 * r)
* * SC: O(b)
*/
// public static int apartmentHunting(
// List<Map<String, Boolean>> blocks, String[] reqs
// ) {
// int len = blocks.size();
// int[] maxDistances = new int[len];
// Arrays.fill(maxDistances, -1);
// for (int i = 0; i < len; i++) {
// for (String req : reqs) {
// int currentDistance = Integer.MAX_VALUE;
// for (int j = 0; j < len; j++) {
// if (blocks.get(j).get(req))
// currentDistance = Math.min(currentDistance, Math.abs(j - i));
// }
// maxDistances[i] = Math.max(maxDistances[i], currentDistance);
// }
// }
// return getLocationIdx(maxDistances);
// }
// private static int getLocationIdx(int[] maxDistances) {
// int locationIdx = -1, minDistance = Integer.MAX_VALUE;
// for (int i = 0; i < maxDistances.length; i++) {
// if (minDistance > maxDistances[i]) {
// minDistance = maxDistances[i];
// locationIdx = i;
// }
// }
// return locationIdx;
// }
}