Problem

You are given an array houses of length n, where houses[i] is the position of the i-th house on a number line. You start at position 0 and want to visit all houses in any order, but you must visit each house exactly once. The cost to move from position x to position y is |x - y|. Return the minimum total cost to visit all houses.

Example 1:

Input: houses = [2, 4, 7] Output: 11 Explanation: One optimal way is 0 -> 2 -> 4 -> 7, cost = 2 + 2 + 3 = 7. Another way is 0 -> 7 -> 4 -> 2, cost = 7 + 3 + 2 = 12. The minimum is 11.

Constraints:

  • 1 <= houses.length <= 10^5
  • -10^9 <= houses[i] <= 10^9

Solution

Method 1 – Greedy + Sorting

Intuition

The minimum cost to visit all houses is achieved by visiting them in sorted order, either ascending or descending, starting from 0. This is because the sum of absolute differences between consecutive sorted positions is minimized.

Approach

  1. Sort the array of house positions.
  2. Calculate the cost to visit all houses in ascending order starting from 0.
  3. Calculate the cost to visit all houses in descending order starting from 0.
  4. Return the minimum of the two costs.
  5. Edge case: If all houses are at the same position, cost is just the distance from 0 to that position.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    long long minCost(vector<int>& houses) {
        sort(houses.begin(), houses.end());
        long long ans1 = abs(houses[0]);
        for (int i = 1; i < houses.size(); ++i) {
            ans1 += abs(houses[i] - houses[i-1]);
        }
        long long ans2 = abs(houses.back());
        for (int i = houses.size() - 2; i >= 0; --i) {
            ans2 += abs(houses[i] - houses[i+1]);
        }
        return min(ans1, ans2);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func minCost(houses []int) int64 {
    sort.Ints(houses)
    ans1 := int64(abs(houses[0]))
    for i := 1; i < len(houses); i++ {
        ans1 += int64(abs(houses[i] - houses[i-1]))
    }
    ans2 := int64(abs(houses[len(houses)-1]))
    for i := len(houses)-2; i >= 0; i-- {
        ans2 += int64(abs(houses[i] - houses[i+1]))
    }
    if ans1 < ans2 {
        return ans1
    }
    return ans2
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long minCost(int[] houses) {
        Arrays.sort(houses);
        long ans1 = Math.abs(houses[0]);
        for (int i = 1; i < houses.length; i++) {
            ans1 += Math.abs(houses[i] - houses[i-1]);
        }
        long ans2 = Math.abs(houses[houses.length-1]);
        for (int i = houses.length-2; i >= 0; i--) {
            ans2 += Math.abs(houses[i] - houses[i+1]);
        }
        return Math.min(ans1, ans2);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun minCost(houses: IntArray): Long {
        houses.sort()
        var ans1 = kotlin.math.abs(houses[0]).toLong()
        for (i in 1 until houses.size) {
            ans1 += kotlin.math.abs(houses[i] - houses[i-1])
        }
        var ans2 = kotlin.math.abs(houses.last()).toLong()
        for (i in houses.size-2 downTo 0) {
            ans2 += kotlin.math.abs(houses[i] - houses[i+1])
        }
        return minOf(ans1, ans2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minCost(self, houses: list[int]) -> int:
        houses.sort()
        ans1: int = abs(houses[0])
        for i in range(1, len(houses)):
            ans1 += abs(houses[i] - houses[i-1])
        ans2: int = abs(houses[-1])
        for i in range(len(houses)-2, -1, -1):
            ans2 += abs(houses[i] - houses[i+1])
        return min(ans1, ans2)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn min_cost(houses: Vec<i32>) -> i64 {
        let mut h = houses.clone();
        h.sort();
        let mut ans1 = (h[0]).abs() as i64;
        for i in 1..h.len() {
            ans1 += (h[i] - h[i-1]).abs() as i64;
        }
        let mut ans2 = (h[h.len()-1]).abs() as i64;
        for i in (0..h.len()-1).rev() {
            ans2 += (h[i] - h[i+1]).abs() as i64;
        }
        ans1.min(ans2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minCost(houses: number[]): number {
        houses.sort((a, b) => a - b);
        let ans1 = Math.abs(houses[0]);
        for (let i = 1; i < houses.length; i++) {
            ans1 += Math.abs(houses[i] - houses[i-1]);
        }
        let ans2 = Math.abs(houses[houses.length-1]);
        for (let i = houses.length-2; i >= 0; i--) {
            ans2 += Math.abs(houses[i] - houses[i+1]);
        }
        return Math.min(ans1, ans2);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), because sorting the array takes O(n log n) and the cost calculation is O(n).

  • 🧺 Space complexity: O(n), because we may need to copy or sort the array.

  • ⏰ Time complexity: O(nnnxxxnnn)

  • 🧺 Space complexity: O(nnnxxx)