Seats | InterviewBit | Solution Explained

I explain the solution to Seats on InterviewBit using visuals in simple words.

0. Seats: Problem Discussion

0.0. IO Format

• input:
  • a string of . and x is given where . represents an empty seat and x represents a filled seat
• output:
  • the minimum number of moves required to group together every person
• constraints:
  • 1 <= N <= 1e6

0.1. Examples

“..x..x.” returns 2 as the answer. Look at the visual below to understand it.

In fact, there are two possible cases. One is where we ask the person at the index 5 to move at 3 (taking 2 cost as |5-3| = 2). Another is asking the person at index 2 to move at 4. The cost remains the same optimal value of 2.

1. Seats: Observations & Logic

1.0. Brute-force

While the test case is small and understandable, it does not tell a lot about what’s going on. How about we take a case like the one shown below?

At this point, what’s the bruteforce solution?

Recall: The goal of the problem is to minimize the number of jumps/moves while grouping together everyone.

This means that the grouped “segment” of people can start form any index and is of the length of the number of people (‘x’s).

Since we don’t know the best, optimal starting index, how about we brute-force it? For example, in the test case we were looking at above, let’s assume that the contiguous segment of people starts from index 0.

Thus, the cost for the index 0 is 14.

But at this point, we can’t be sure that it is indeed the optimal answer. So, we continue our iteration;

And we keep on going like this, till we get the optimal answer of 6.

We go over all the possible starting indices in O(N) time, where N is the total number of seats in the row (filled and empty both). For each of these indices, we find the overall cost required, taking a further O(N). This means that the total time complexity is O(N^2).

1.1. Optimization

Now this is quite tedious. Especially as we move to larger cases.

The second loop seems kind of necessary. The loop that finds the answer for a given index. Now the question we ask is: is there a better way to deal with the loop that goes over all the indices? Perhaps there is a better way to find the optimal starting index of the segment of people.

Consider a case like the one below.

In this case, doesn’t it seem like perhaps the cluster of people are important? Intuitively it makes sense for a cluster of 3 people having a conversation invite the rest of the 2 groups to join in?

This gives us a total cost of 20. We don’t know if this is correct or not, so, let’s try working out the solution using the bruteforce approach.

We see that instead, the people have grouped together at the middle. But … mathematically speaking, what is the middle? Can we find a formal definition for it?

1.2. The middle

Going back to high school math, we recall 3 statistical measures. Mean, median and mode. Mode we know didn’t work out, since the result comes in the middle. How about mean and median?

Let’s try out the mean.

Ah. The solution is centered around 5, but the mean says 6. What about median?

Looks like this is it! Let’s go ahead and implement this logic.

2. Seats: Optimized Implementation

2.0. Code

class Solution:
# @param A : string
# @return an integer
def seats(self, A):
        MOD = 10000003
        
        # all the indices of xs
        crosses = [i for i, c in enumerate(A) if c == "x"]
        # moves req assuming starting position is 0
        crosses = [(cross - i) for i, cross in enumerate(crosses)]

        n = len(crosses)
        if n == 0: return 0
        
        ans = float('inf')
        segment_start = crosses[n // 2]
        total = 0        
        for cross in crosses: # O(N)
            total += abs(cross - segment_start)
            total %= MOD
        ans = min(ans, total % MOD)
            
        return ans

2.1. Complexity Analysis

• Time: O(N), to iterate over the array A and then over the crosses later.
• Space: O(N), to store the locations of the crosses.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.