FastPrepAssigned Parking

Assigned Parking

Airbnb logoAirbnb● MediumFULLTIMEOA

Updated

Problem statement

There are n cars on a grid. Car i is at the point (x[i], y[i]).

You must park all the cars side by side in one horizontal row, with no gaps. So the cars end up at the points (a, b), (a + 1, b), ..., (a + n - 1, b) for some integers a and b that you choose, with one car at each point. Any car may take any of these spots.

Moving a car from (x1, y1) to (x2, y2) uses |x1 - x2| + |y1 - y2| units of fuel.

Return the minimum total fuel needed to park all the cars. Several cars may start at the same point.

Function

minFuel(x: int[], y: int[]) → long

Examples

Example 1

x = [1, 4]y = [1, 4]return = 5

Park both cars in the row y = 1, at (3, 1) and (4, 1). The car at (1, 1) moves right by 2, and the car at (4, 4) moves down by 3. The total is 2 + 3 = 5.

No plan is cheaper. The two cars are 3 rows apart, so putting them in one row costs at least 3. They are 3 columns apart, but side by side they must be 1 column apart, so that costs at least 2 more.

Example 2

x = [1, 5]y = [1, 5]return = 7

Park both cars in the row y = 1, at (4, 1) and (5, 1). The car at (1, 1) moves right by 3, and the car at (5, 5) moves down by 4. The total is 3 + 4 = 7.

Example 3

x = [4, 6, 4, -4, 1]y = [-1, 1, -5, -4, 5]return = 23

Park the cars in the row y = -1, at x = 1 to x = 5:

  • (-4, -4) moves to (1, -1): 5 + 3 = 8.
  • (1, 5) moves to (2, -1): 1 + 6 = 7.
  • (4, -1) moves to (3, -1): 1 + 0 = 1.
  • (4, -5) moves to (4, -1): 0 + 4 = 4.
  • (6, 1) moves to (5, -1): 1 + 2 = 3.

The total is 8 + 7 + 1 + 4 + 3 = 23, and no other row or start position does better.

Constraints

  • n == x.length == y.length
  • 1 <= n <= 105
  • -109 <= x[i], y[i] <= 109

More Airbnb Online Assessment questions

Similar questions at other companies

Interview reports that mention this question

Airbnb interview experiences

All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public long minFuel(int[] x, int[] y) {
      // Write your code here.
    }
}
Checking account…