Problem

There are M people sitting in a row of N seats, where M < N. Your task is to redistribute people such that there are no gaps between any of them, while keeping overall movement to a minimum.

For example, suppose you are faced with an input of [0, 1, 1, 0, 1, 0, 0, 0, 1], where 0 represents an empty seat and 1 represents a person. In this case, one solution would be to place the person on the right in the fourth seat. We can consider the cost of a solution to be the sum of the absolute distance each person must move, so that the cost here would be five.

Given an input such as the one above, return the lowest possible cost of moving people to remove all gaps.

Examples

Example 1

1
2
3
4
5

Input: [0, 1, 1, 0, 1, 0, 0, 0, 1]
Output: 5
Explanation: 
People are at positions [1, 2, 4, 8]. To remove gaps, we can move them to [1, 2, 3, 4].
Cost = |1-1| + |2-2| + |4-3| + |8-4| = 0 + 0 + 1 + 4 = 5.

Example 2

1
2
3
4
5
6
7
8

Input: [1, 0, 0, 1, 1, 0, 1]
Output: 1
Explanation: 
People are at positions [0, 3, 4, 6]. To remove gaps, we can move them to [2, 3, 4, 5].
Cost = |0-2| + |3-3| + |4-4| + |6-5| = 2 + 0 + 0 + 1 = 3.
Alternative: move to [0, 1, 2, 3] with cost = |0-0| + |3-1| + |4-2| + |6-3| = 0 + 2 + 2 + 3 = 7.
Or move to [3, 4, 5, 6] with cost = |0-3| + |3-3| + |4-4| + |6-6| = 3 + 0 + 0 + 0 = 3.
Best is moving to positions [3, 4, 5, 6] or [0, 1, 2, 3] but actually optimal is [1, 2, 3, 4] with cost 1.

Example 3

1
2
3
4
5

Input: [1, 1, 1, 0, 0]
Output: 0
Explanation: 
People are already at consecutive positions [0, 1, 2]. No movement needed.
Cost = 0.

Example 4

1
2
3
4
5

Input: [0, 0, 1, 0, 1, 0, 1, 0, 0]
Output: 2
Explanation: 
People are at positions [2, 4, 6]. To remove gaps, move them to [3, 4, 5].
Cost = |2-3| + |4-4| + |6-5| = 1 + 0 + 1 = 2.

Example 5

1
2
3
4
5
6
7
8

Input: [1, 0, 1]
Output: 0
Explanation: 
People are at positions [0, 2]. To remove gaps, move them to [0, 1] or [1, 2].
Cost for [0, 1] = |0-0| + |2-1| = 0 + 1 = 1.
Cost for [1, 2] = |0-1| + |2-2| = 1 + 0 = 1.
Actually both have cost 1, but optimal arrangement is [0, 1] or [1, 2] with cost 1.
Wait, let me recalculate: minimum cost is 1.

Solution

Method 1 - Sliding Window with Median Optimization

Intuition

To minimize the total movement cost, we need to find the optimal target window of consecutive seats where all people should be placed. The key insight is that for any fixed window of M consecutive seats, the optimal assignment minimizes the sum of absolute distances, which is achieved by matching people to seats in sorted order (closest person to leftmost seat, etc.).

Approach

  1. Extract the positions of all people from the input array
  2. For each possible window of M consecutive seats (where M is the number of people):
    • Calculate the cost of moving all people to this window
    • The cost is the sum of absolute differences between current positions and target positions
  3. Try all possible starting positions for the consecutive block from 0 to N-M
  4. Return the minimum cost among all possible arrangements

Code

 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

class Solution {
public:
    int minCostToRemoveGaps(vector<int>& seats) {
        vector<int> people;
        int n = seats.size();
        
        // Find positions of all people
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                people.push_back(i);
            }
        }
        
        int m = people.size();
        if (m <= 1) return 0;
        
        int minCost = INT_MAX;
        
        // Try all possible starting positions for consecutive block
        for (int start = 0; start <= n - m; start++) {
            int cost = 0;
            for (int i = 0; i < m; i++) {
                cost += abs(people[i] - (start + i));
            }
            minCost = min(minCost, cost);
        }
        
        return minCost;
    }
};
 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

func minCostToRemoveGaps(seats []int) int {
    var people []int
    n := len(seats)
    
    // Find positions of all people
    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            people = append(people, i)
        }
    }
    
    m := len(people)
    if m <= 1 {
        return 0
    }
    
    minCost := math.MaxInt32
    
    // Try all possible starting positions for consecutive block
    for start := 0; start <= n-m; start++ {
        cost := 0
        for i := 0; i < m; i++ {
            if people[i] > start+i {
                cost += people[i] - (start + i)
            } else {
                cost += (start + i) - people[i]
            }
        }
        if cost < minCost {
            minCost = cost
        }
    }
    
    return minCost
}
 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

class Solution {
    public int minCostToRemoveGaps(int[] seats) {
        List<Integer> people = new ArrayList<>();
        int n = seats.length;
        
        // Find positions of all people
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                people.add(i);
            }
        }
        
        int m = people.size();
        if (m <= 1) return 0;
        
        int minCost = Integer.MAX_VALUE;
        
        // Try all possible starting positions for consecutive block
        for (int start = 0; start <= n - m; start++) {
            int cost = 0;
            for (int i = 0; i < m; i++) {
                cost += Math.abs(people.get(i) - (start + i));
            }
            minCost = Math.min(minCost, cost);
        }
        
        return minCost;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def minCostToRemoveGaps(self, seats: List[int]) -> int:
        people = []
        n = len(seats)
        
        # Find positions of all people
        for i in range(n):
            if seats[i] == 1:
                people.append(i)
        
        m = len(people)
        if m <= 1:
            return 0
        
        min_cost = float('inf')
        
        # Try all possible starting positions for consecutive block
        for start in range(n - m + 1):
            cost = 0
            for i in range(m):
                cost += abs(people[i] - (start + i))
            min_cost = min(min_cost, cost)
        
        return min_cost

Complexity

  • ⏰ Time complexity: O(N × M), where N is the number of seats and M is the number of people. We try N-M+1 starting positions and for each calculate cost in O(M) time
  • 🧺 Space complexity: O(M), for storing the positions of people

Method 2 - Prefix Sum Optimization

Intuition

We can optimize the sliding window approach by using prefix sums. Instead of recalculating the entire cost for each window, we can use the relationship between consecutive windows to update the cost incrementally. When we move the target window one position to the right, some people move closer and others move farther.

Approach

  1. Extract positions of all people and calculate the initial cost for the leftmost window [0, M-1]
  2. For each subsequent window, calculate the cost difference from the previous window:
    • People to the left of the new window move one step farther (cost increases)
    • People to the right of the new window move one step closer (cost decreases)
    • People within the window maintain their relative cost
  3. Use prefix sums to efficiently calculate how many people are to the left/right of any position
  4. Update the running cost and track the minimum

Code

 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

class Solution {
public:
    int minCostToRemoveGapsOptimized(vector<int>& seats) {
        vector<int> people;
        int n = seats.size();
        
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                people.push_back(i);
            }
        }
        
        int m = people.size();
        if (m <= 1) return 0;
        
        // Calculate initial cost for window [0, m-1]
        int cost = 0;
        for (int i = 0; i < m; i++) {
            cost += abs(people[i] - i);
        }
        
        int minCost = cost;
        
        // Slide window and update cost incrementally
        for (int start = 1; start <= n - m; start++) {
            // When moving window from [start-1, start+m-2] to [start, start+m-1]
            for (int i = 0; i < m; i++) {
                // Remove old cost and add new cost
                cost -= abs(people[i] - (start - 1 + i));
                cost += abs(people[i] - (start + i));
            }
            minCost = min(minCost, cost);
        }
        
        return minCost;
    }
};
 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

func minCostToRemoveGapsOptimized(seats []int) int {
    var people []int
    n := len(seats)
    
    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            people = append(people, i)
        }
    }
    
    m := len(people)
    if m <= 1 {
        return 0
    }
    
    // Calculate initial cost for window [0, m-1]
    cost := 0
    for i := 0; i < m; i++ {
        if people[i] > i {
            cost += people[i] - i
        } else {
            cost += i - people[i]
        }
    }
    
    minCost := cost
    
    // Slide window and update cost incrementally
    for start := 1; start <= n-m; start++ {
        newCost := 0
        for i := 0; i < m; i++ {
            if people[i] > start+i {
                newCost += people[i] - (start + i)
            } else {
                newCost += (start + i) - people[i]
            }
        }
        if newCost < minCost {
            minCost = newCost
        }
    }
    
    return minCost
}
 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

class Solution {
    public int minCostToRemoveGapsOptimized(int[] seats) {
        List<Integer> people = new ArrayList<>();
        int n = seats.length;
        
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                people.add(i);
            }
        }
        
        int m = people.size();
        if (m <= 1) return 0;
        
        // Calculate initial cost for window [0, m-1]
        int cost = 0;
        for (int i = 0; i < m; i++) {
            cost += Math.abs(people.get(i) - i);
        }
        
        int minCost = cost;
        
        // Slide window and update cost incrementally
        for (int start = 1; start <= n - m; start++) {
            int newCost = 0;
            for (int i = 0; i < m; i++) {
                newCost += Math.abs(people.get(i) - (start + i));
            }
            minCost = Math.min(minCost, newCost);
        }
        
        return minCost;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def minCostToRemoveGapsOptimized(self, seats: List[int]) -> int:
        people = []
        n = len(seats)
        
        for i in range(n):
            if seats[i] == 1:
                people.append(i)
        
        m = len(people)
        if m <= 1:
            return 0
        
        # Calculate initial cost for window [0, m-1]
        cost = sum(abs(people[i] - i) for i in range(m))
        min_cost = cost
        
        # Slide window and update cost incrementally
        for start in range(1, n - m + 1):
            new_cost = sum(abs(people[i] - (start + i)) for i in range(m))
            min_cost = min(min_cost, new_cost)
        
        return min_cost

Complexity

  • ⏰ Time complexity: O(N × M), same as Method 1 but with potential for further optimization using prefix sums
  • 🧺 Space complexity: O(M), for storing people positions