Problem Statement in English

You’re given 3 positive integers n, k, and pos.

There are n people standing in a line, the $i^{th}$ person is visible if:

  • i < pos and the $i^{th}$ person is assigned the direction L, or
  • i > pos and the $i^{th}$ person is assigned the direction R.

Return the number of ways to assign directions to the n people such that there are exactly k visible people.

Since the answer may be very large, return it modulo $10^9 + 7$.

Approach

The pos doesn’t matter if you think about it.

Each person can be either on the left or on the right so we just need to choose k people from the n - 1 people (excluding the person at pos) to be visible, and multiply that by 2 to account for the two possible directions for the person at pos.

And we’re done!

Solution in Python


class Solution:

    def countVisiblePeople(self, n, pos, k):
        MOD = 1000000007
        n = n - 1

        if k == 0:
            return 2

        val = comb(n, k)
        return (val * 2) % MOD

Complexity

  • Time: $O(k)$
    Since we are calculating the binomial coefficient comb(n, k), which can be done in $O(k)$ time using a multiplicative approach.

  • Space: $O(1)$
    Since we are using only a constant amount of space to store intermediate values and the result.

Mistakes I Made

I had to look this up :(

And we are done.