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.

Seats: simple test case

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?

Seats: a better test case

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.

Seats: starting at 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;

Seats: starting at index 1

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

Seats: starting at index 4

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.

Seats: maybe the answer is from clusters of people

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?

Seats: clustering at biggest cluster

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.

Seats: the correct answer

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.

Seats: using the mean

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

Seats: using the 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.

Avatar for Tanishq Chaudhary

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


    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

      A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

      Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

      To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

      Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

      This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

      Understanding why solar energy consultants assist clients via Matthew D’Agati.
      Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.