Skip to content

Apartment Hunting

Category: Arrays

```

Problem Statement

, "store": false, }, { "gym": true, "school": false, "store": false, }, { "gym": true, "school": true, "store": false, }, { "gym": false, "school": true, "store": false, }, { "gym": false, "school": true, "store": true, }, ] reqs = ["gym", "school", "store"] Sample Output // at index 3, the farthest you'd have to walk to reach a gym, a school, or a store is 1 block; at any other index, you'd have Hints Hint 1 For every block, you want to go through every requirement, and for every requirement, you want to nd the closest other block with that requirement (or rather, the smallest distance to another block with that requirement). Once you've done that for every requirement and for every block, you want to pick, for every block, thedistanceofthefarthestrequirement.Youcandothiswiththreenested"for"loops. the distance of the farthest requirement. You can do this with three nested for loops. Hint 2 Is there a way to optimize on the solution mentioned in Hint #1 (that uses three nested "for" loops) by pre-computing the smallest distances of every requirement from every block? Hint 3 For every requirement, you should be able to pre-compute its smallest distances from every block by doing two simple passes though the array of blocks: one pass from left to right and one pass from right to left. Once you have these pre-computed values, you can iterate through all of the blocks and pick the biggest of all the pre-computed distances at that block. Optimal Space & Time Complexity O(br) time | O(br) space - where b is the number of blocks and r is the number of requirements

```

Approach & Solution

Solution 1

``` Solution 1 Solution 2 import java.util.*; class Program { // O(br) time | O(br) space - where b is the number of blocks and r is the number of // requirements public static int apartmentHunting(List> blocks, String[] reqs) { int[][] minDistancesFromBlocks = new int[reqs.length][]; for (int i = 0; i < reqs.length; i++) { minDistancesFromBlocks[i] = getMinDistances(blocks, reqs[i]); } int[] maxDistancesAtBlocks = getMaxDistancesAtBlocks(blocks, minDistancesFromBlocks); return getIdxAtMinValue(maxDistancesAtBlocks); } public static int[] getMinDistances(List> blocks, String req) { int[] minDistances = new int[blocks.size()]; int closestReqIdx = Integer.MAX_VALUE; for (int i = 0; i < blocks.size(); i++) { if (blocks.get(i).get(req)) closestReqIdx = i; minDistances[i] = distanceBetween(i, closestReqIdx); } for (int i = blocks.size() - 1; i >= 0; i--) { if (blocks.get(i).get(req)) closestReqIdx = i; minDistances[i] = Math.min(minDistances[i], distanceBetween(i, closestReqIdx)); } return minDistances; } public static int[] getMaxDistancesAtBlocks( List> blocks, int[][] minDistancesFromBlocks) { int[] maxDistancesAtBlocks = new int[blocks.size()]; for (int i = 0; i < blocks.size(); i++) { int[] minDistancesAtBlock = new int[minDistancesFromBlocks.length]; for (int j = 0; j < minDistancesFromBlocks.length; j++) { minDistancesAtBlock[j] = minDistancesFromBlocks[j][i]; } maxDistancesAtBlocks[i] = arrayMax(minDistancesAtBlock);

Solution 2

``` Solution 1 Solution 2 2 3 import java.util.; 4 5 class Program { 6 // O(b^2r) time | O(b) space - where b is the number of blocks and r is the number of 7 // requirements 8 public static int apartmentHunting(List> blocks, String[] reqs) { 9 int[] maxDistancesAtBlocks = new int[blocks.size()]; 10 Arrays.fill(maxDistancesAtBlocks, Integer.MIN_VALUE); 11 12 for (int i = 0; i < blocks.size(); i++) { 13 for (String req : reqs) { 14 int closestReqDistance = Integer.MAX_VALUE; 15 for (int j = 0; j < blocks.size(); j++) { 16 if (blocks.get(j).get(req)) { 17 closestReqDistance = Math.min(closestReqDistance, distanceBetween(i, j)); 18 } 19 } 20 maxDistancesAtBlocks[i] = Math.max(maxDistancesAtBlocks[i], closestReqDistance); 21 } 22 } 23 return getIdxAtMinValue(maxDistancesAtBlocks); 24 } 25 26 public static int getIdxAtMinValue(int[] array) { 27 int idxAtMinValue = 0; 28 int minValue = Integer.MAX_VALUE; 29 for (int i = 0; i < array.length; i++) { 30 int currentValue = array[i]; 31 if (currentValue < minValue) { 32 minValue = currentValue; 33 idxAtMinValue = i; 34 } 35 } 36 return idxAtMinValue; 37 } 38 39 public static int distanceBetween(int a, int b) { 40 return Math.abs(a - b); 41 } 42 } 43

```

Test Cases

``` Video Solution Video Solution

``` Test Case 1 { "blocks": [ {"gym": false, "school": true, "store": false}, {"gym": true, "school": false, "store": false}, {"gym": true, "school": true, "store": false}, {"gym": false, "school": true, "store": false}, {"gym": false, "school": true, "store": true} ], "reqs": ["gym", "school", "store"] } Test Case 2 { "blocks": [ {"gym": false, "office": true, "school": true, "store": false}, {"gym": true, "office": false, "school": false, "store": false}, {"gym": true, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": true} ], "reqs": ["gym", "office", "school", "store"] } Test Case 3 { "blocks": [ {"gym": false, "office": true, "school": true, "store": false}, {"gym": true, "office": false, "school": false, "store": false}, {"gym": true, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": true} ], "reqs": ["gym", "office", "school", "store"] } Test Case 4 { "blocks": [ { "foo": true, "gym": false, "kappa": false, "office": true, "school": true, "store": false }, { "foo": true, "gym": true, "kappa": false, "office": false, "school": false, "store": false }, { "foo": true, "gym": true, "kappa": false, "office": false, "school": true, "store": false }, { "foo": true, "gym": false, "kappa": false, "office": false, "school": true, "store": false }, { "foo": true, "gym": true, "kappa": false, "office": false, "school": true, "store": false }, { "foo": true, "gym": false, "kappa": false, "office": false, "school": true, "store": true } ], "reqs": ["gym", "school", "store"] } Test Case 5 { "blocks": [ {"gym": true, "school": true, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": true, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": false, "store": true}, {"gym": true, "school": false, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": true, "store": false} ], "reqs": ["gym", "school", "store"] } Test Case 6 { "blocks": [ {"gym": true, "pool": false, "school": true, "store": false}, {"gym": false, "pool": false, "school": false, "store": false}, {"gym": false, "pool": false, "school": true, "store": false}, {"gym": false, "pool": false, "school": false, "store": false}, {"gym": false, "pool": false, "school": false, "store": true}, {"gym": true, "pool": false, "school": false, "store": false}, {"gym": false, "pool": false, "school": false, "store": false}, {"gym": false, "pool": false, "school": false, "store": false}, {"gym": false, "pool": false, "school": false, "store": false}, {"gym": false, "pool": false, "school": true, "store": false}, {"gym": false, "pool": true, "school": false, "store": false} ], "reqs": ["gym", "pool", "school", "store"] } Test Case 7 { "blocks": [ { "gym": true, "office": false, "pool": false, "school": true, "store": false }, { "gym": false, "office": false, "pool": false, "school": false, "store": false }, { "gym": false, "office": true, "pool": false, "school": true, "store": false }, { "gym": false, "office": true, "pool": false, "school": false, "store": false }, { "gym": false, "office": false, "pool": false, "school": false, "store": true }, { "gym": true, "office": true, "pool": false, "school": false, "store": false }, { "gym": false, "office": false, "pool": true, "school": false, "store": false }, { "gym": false, "office": false, "pool": false, "school": false, "store": false }, { "gym": false, "office": false, "pool": false, "school": false, "store": false }, { "gym": false, "office": false, "pool": false, "school": true, "store": false }, { "gym": false, "office": false, "pool": true, "school": false, "store": false } ], "reqs": ["gym", "pool", "school", "store"] }

``` Video Solution

1 2 ​ 3 import java.util.; 4 ​ 5 class Program { 6 // O(b^2r) time | O(b) space - where b is the number of blocks and r is the number of 7 // requirements 8 public static int apartmentHunting(List> blocks, String[] reqs) { 9 int[] maxDistancesAtBlocks = new int[blocks.size()]; 10 Arrays.fill(maxDistancesAtBlocks, Integer.MIN_VALUE); 11 ​ 12 for (int i = 0; i < blocks.size(); i++) { 13 for (String req : reqs) { 14 int closestReqDistance = Integer.MAX_VALUE; 15 for (int j = 0; j < blocks.size(); j++) { 16 if (blocks.get(j).get(req)) { 17 closestReqDistance = Math.min(closestReqDistance, distanceBetween(i, j)); 18 } 19 } 20 maxDistancesAtBlocks[i] = Math.max(maxDistancesAtBlocks[i], closestReqDistance); 21 } 22 } 23 return getIdxAtMinValue(maxDistancesAtBlocks); 24 } 25 ​ 26 public static int getIdxAtMinValue(int[] array) { 27 int idxAtMinValue = 0; 28 int minValue = Integer.MAX_VALUE; 29 for (int i = 0; i < array.length; i++) { 30 int currentValue = array[i]; 31 if (currentValue < minValue) { 32 minValue = currentValue; 33 idxAtMinValue = i; 34 } 35 } 36 return idxAtMinValue; 37 } 38 ​ 39 public static int distanceBetween(int a, int b) { 40 return Math.abs(a - b); 41 }

Test Case 1 { "blocks": [ {"gym": false, "school": true, "store": false}, {"gym": true, "school": false, "store": false}, {"gym": true, "school": true, "store": false}, {"gym": false, "school": true, "store": false}, {"gym": false, "school": true, "store": true} ], "reqs": ["gym", "school", "store"] } Test Case 2 { "blocks": [ {"gym": false, "office": true, "school": true, "store": false}, {"gym": true, "office": false, "school": false, "store": false}, {"gym": true, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": true} ], "reqs": ["gym", "office", "school", "store"] } Test Case 3 { "blocks": [ {"gym": false, "office": true, "school": true, "store": false}, {"gym": true, "office": false, "school": false, "store": false}, {"gym": true, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": false}, {"gym": false, "office": false, "school": true, "store": true} ], "reqs": ["gym", "office", "school", "store"] } Test Case 4 { "blocks": [ { "foo": true, "gym": false, "kappa": false, "office": true, "school": true, "store": false }, { "foo": true, "gym": true, "kappa": false, "office": false, "school": false, "store": false }, { "foo": true, "gym": true, "kappa": false, "office": false, "school": true, "store": false }, { "foo": true, "gym": false, "kappa": false, "office": false, "school": true, "store": false }, { "foo": true, "gym": true, "kappa": false, "office": false, "school": true, "store": false }, { "foo": true, "gym": false, "kappa": false, "office": false, "school": true, "store": true } ], "reqs": ["gym", "school", "store"] } Test Case 5 { "blocks": [ {"gym": true, "school": true, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": true, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": false, "store": true}, {"gym": true, "school": false, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": false, "store": false}, {"gym": false, "school": true, "store": false} ], "reqs": ["gym", "school", "store"] } T ... (test file truncated for display)