Minimum Moves to Group Occupied Seats

Problem

There is a row of seats. Assume that it contains N seats adjacent to each other. There is a group of people who are already seated in that row randomly. i.e. some are sitting together & some are scattered.

An occupied seat is marked with a character 'x' and an unoccupied seat is marked with a dot ('.')

Now your target is to make the whole group sit together i.e. next to each other, without having any vacant seat between them in such a way that the total number of hops or jumps to move them should be minimum.

In one jump a person can move to the adjacent seat (if available).

NOTE: 1. Return your answer modulo 10^7 + 3.

Examples

Example 1

Input: A = "....x..xx...x.."
Output: 5

Example 2

Input: A = "....xxx"
Output: 0

Constraints

• 1 <= N <= 1000000
• A[i] = 'x' or '.'

Solution

Method 1 – Greedy Median Centering

Intuition

The minimum total moves are achieved by grouping all people around the median of their current positions. This is because the sum of absolute differences from the median is minimized.

Approach

1. Collect the indices of all occupied seats ('x').
2. Find the median index among these positions.
3. For each person, calculate the moves needed to bring them to consecutive seats centered at the median.
4. Return the total moves modulo 10000003.

Code

C++

class Solution {
public:
    int seats(string &A) {
        const int MOD = 10000003;
        vector<int> pos;
        for (int i = 0; i < A.size(); ++i) if (A[i] == 'x') pos.push_back(i);
        if (pos.empty()) return 0;
        int m = pos.size() / 2, ans = 0;
        for (int i = 0; i < pos.size(); ++i)
            ans = (ans + abs(pos[i] - (pos[m] - m + i))) % MOD;
        return ans;
    }
};

Java

class Solution {
    public int seats(String A) {
        int MOD = 10000003;
        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < A.length(); i++) {
            if (A.charAt(i) == 'x') pos.add(i);
        }
        if (pos.size() == 0) return 0;
        int m = pos.size() / 2, ans = 0;
        for (int i = 0; i < pos.size(); i++) {
            ans = (ans + Math.abs(pos.get(i) - (pos.get(m) - m + i))) % MOD;
        }
        return ans;
    }
}

Python

from typing import List
class Solution:
    def seats(self, A: str) -> int:
        MOD = 10000003
        pos = [i for i, c in enumerate(A) if c == 'x']
        if not pos:
            return 0
        m = len(pos) // 2
        ans = 0
        for i, p in enumerate(pos):
            ans = (ans + abs(p - (pos[m] - m + i))) % MOD
        return ans

Complexity

• ⏰ Time complexity: O(n) — We scan the string once and process each occupied seat once.
• 🧺 Space complexity: O(n) — We store the indices of all occupied seats.

Method 2 – Two Pointers & Deque Merging

Intuition

This approach treats each contiguous group of people as a block and repeatedly merges the leftmost or rightmost group into its neighbor, always merging the smaller group first. This minimizes the total number of moves required to bring everyone together.

Approach

1. Identify all contiguous groups of 'x' and store their start and end indices in a deque.
2. While more than one group remains:
   • Compare the sizes of the leftmost and rightmost groups.
   • Merge the smaller group into its neighbor, updating the total moves and adjusting group boundaries.
3. Continue until all people are grouped together.
4. Return the total moves modulo 10000003.

Code

Java

import java.util.*;
class Solution {
    public int seatsDeque(String A) {
        int MOD = 10000003;
        char[] seats = A.toCharArray();
        Deque<int[]> dq = new ArrayDeque<>();
        int i = 0, j = 0, n = seats.length;
        while (j < n) {
            while (j < n && seats[j] == '.') j++;
            if (j == n) break;
            for (i = j; j < n && seats[j] == 'x'; j++);
            dq.addLast(new int[]{i, j - 1});
        }
        int ans = 0;
        while (dq.size() > 1) {
            int[] left = dq.peekFirst();
            int[] right = dq.peekLast();
            int lenLeft = left[1] - left[0] + 1;
            int lenRight = right[1] - right[0] + 1;
            if (lenLeft <= lenRight) {
                left = dq.pollFirst();
                ans = (ans + lenLeft * (dq.peekFirst()[0] - left[1] - 1)) % MOD;
                dq.peekFirst()[0] -= lenLeft;
            } else {
                right = dq.pollLast();
                ans = (ans + lenRight * (right[0] - dq.peekLast()[1] - 1)) % MOD;
                dq.peekLast()[1] += lenRight;
            }
        }
        return ans;
    }
}

Python

from collections import deque
class Solution:
    def seats_deque(self, A: str) -> int:
        MOD = 10000003
        seats = list(A)
        dq = deque()
        n = len(seats)
        j = 0
        while j < n:
            while j < n and seats[j] == '.':
                j += 1
            if j == n:
                break
            i = j
            while j < n and seats[j] == 'x':
                j += 1
            dq.append([i, j - 1])
        ans = 0
        while len(dq) > 1:
            left = dq[0]
            right = dq[-1]
            len_left = left[1] - left[0] + 1
            len_right = right[1] - right[0] + 1
            if len_left <= len_right:
                left = dq.popleft()
                ans = (ans + len_left * (dq[0][0] - left[1] - 1)) % MOD
                dq[0][0] -= len_left
            else:
                right = dq.pop()
                ans = (ans + len_right * (right[0] - dq[-1][1] - 1)) % MOD
                dq[-1][1] += len_right
        return ans

Complexity

• ⏰ Time complexity: O(n) — Each seat is processed a constant number of times.
• 🧺 Space complexity: O(n) — For storing group boundaries in the deque.