LeetCode Problem 3881

Difficulty: 🟡 Medium
Topics: Math, Combinatorics

Solution

LeetCode 3881 - Direction Assignments with Exactly K Visible People

Problem Understanding

We are given n people standing in a line, indexed from 0 to n - 1. Each person independently chooses one of two directions:

• 'L' means the person is visible only to people on their right.
• 'R' means the person is visible only to people on their left.

We focus on the person located at index pos. Whether this person can see another person depends entirely on that other person's chosen direction.

For a person located to the left of pos, that person is visible to pos if and only if they choose 'L'.

For a person located to the right of pos, that person is visible to pos if and only if they choose 'R'.

The direction chosen by the person at pos does not affect how many people they see. It only contributes an independent factor of two possibilities.

Our goal is to count how many complete direction assignments exist such that the person at index pos sees exactly k people.

Because the answer can be very large, we return it modulo 10^9 + 7.

Understanding the Constraints

The constraint n ≤ 10^5 immediately rules out any solution that tries to enumerate all possible assignments.

Since each person has two possible directions, there are 2^n total assignments. Even for n = 50, this would already be far too large.

The problem therefore requires a mathematical counting approach rather than simulation.

Important Edge Cases

One important edge case occurs when n = 1. There are no other people to see, so the answer is 2 when k = 0 and 0 otherwise.

Another edge case occurs when k exceeds the total number of people other than pos. Since at most n - 1 people can be visible, the answer must be 0.

A third edge case occurs when pos is at either end of the line. In that case, all potentially visible people are on only one side, but the counting logic remains the same.

Approaches

Brute Force

A brute-force solution would generate all possible direction assignments.

Since every person independently chooses either 'L' or 'R', there are 2^n assignments. For each assignment, we could count how many people are visible from position pos and check whether the count equals k.

This approach is correct because it explicitly examines every valid assignment and counts exactly those satisfying the condition.

However, its running time is exponential. With n as large as 100000, enumerating 2^n assignments is impossible.

Key Insight

Consider every person except the one at index pos.

For any such person:

• Exactly one direction makes them visible.
• Exactly one direction makes them invisible.

Therefore, every person other than pos behaves identically:

• Visible choice: 1 possibility.
• Invisible choice: 1 possibility.

There are exactly n - 1 people whose visibility status matters.

To make exactly k people visible:

1. Choose which k of the n - 1 people will be visible.
2. Their directions become fixed.
3. The remaining n - 1 - k people must choose the unique invisible direction.
4. The person at pos may independently choose either 'L' or 'R'.

Thus:

$$\text{answer} = 2 \cdot \binom{n-1}{k}$$

The only remaining challenge is efficiently computing a binomial coefficient modulo 10^9 + 7.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n · 2^n)	O(n)	Enumerates every direction assignment
Optimal	O(n) preprocessing, O(1) query	O(n)	Uses combinatorics and modular inverses

Algorithm Walkthrough

1. Let m = n - 1, representing all people whose visibility status matters.
2. If k > m, return 0 immediately because it is impossible to see more than n - 1 people.
3. Compute the binomial coefficient:

$$\binom{m}{k}$$

modulo 10^9 + 7. 4. To do this efficiently, precompute factorials:

$$fact[i] = i!$$

for all 0 ≤ i ≤ m. 5. Use Fermat's Little Theorem to compute modular inverses:

$$a^{-1} \equiv a^{MOD-2} \pmod{MOD}$$

because MOD = 10^9 + 7 is prime. 6. Compute

$$\binom{m}{k} = \frac{m!}{k!(m-k)!} \pmod{MOD}$$

using factorials and inverse factorials. 7. Multiply the result by 2 because the direction chosen by the person at index pos never affects visibility. 8. Return the final value modulo MOD.

Why it works

Every person other than pos contributes exactly one visible direction and one invisible direction. Therefore, once we choose which k people are visible, all directions become uniquely determined for those n - 1 people. The only remaining freedom is the direction of the person at pos, which contributes a factor of two. Consequently, the total number of valid assignments is exactly:

$$2 \cdot \binom{n-1}{k}$$

which is what the algorithm computes.

Python Solution

class Solution:
    def countVisiblePeople(self, n: int, pos: int, k: int) -> int:
        MOD = 10**9 + 7

        m = n - 1
        if k > m:
            return 0

        fact = [1] * (m + 1)
        for i in range(1, m + 1):
            fact[i] = fact[i - 1] * i % MOD

        inv_fact = [1] * (m + 1)
        inv_fact[m] = pow(fact[m], MOD - 2, MOD)

        for i in range(m, 0, -1):
            inv_fact[i - 1] = inv_fact[i] * i % MOD

        comb = fact[m]
        comb = comb * inv_fact[k] % MOD
        comb = comb * inv_fact[m - k] % MOD

        return (2 * comb) % MOD

The implementation begins by observing that only n - 1 people affect the visibility count. If k exceeds that number, no valid assignment exists.

The code then precomputes factorials modulo 10^9 + 7. Using a single modular exponentiation, it obtains the inverse of the largest factorial and derives all remaining inverse factorials in linear time.

With factorials and inverse factorials available, the binomial coefficient is computed using the standard modular combination formula. Finally, the result is multiplied by two to account for the independent choice made by the person at index pos.

Go Solution

func countVisiblePeople(n int, pos int, k int) int {
	const MOD int64 = 1_000_000_007

	m := n - 1
	if k > m {
		return 0
	}

	fact := make([]int64, m+1)
	fact[0] = 1

	for i := 1; i <= m; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}

	powMod := func(base, exp int64) int64 {
		result := int64(1)

		for exp > 0 {
			if exp&1 == 1 {
				result = result * base % MOD
			}
			base = base * base % MOD
			exp >>= 1
		}

		return result
	}

	invFact := make([]int64, m+1)
	invFact[m] = powMod(fact[m], MOD-2)

	for i := m; i >= 1; i-- {
		invFact[i-1] = invFact[i] * int64(i) % MOD
	}

	comb := fact[m]
	comb = comb * invFact[k] % MOD
	comb = comb * invFact[m-k] % MOD

	return int((2 * comb) % MOD)
}

The Go implementation follows exactly the same combinatorial formula. Since intermediate factorial values can exceed 32-bit limits, all modular arithmetic uses int64. The modular exponentiation function implements binary exponentiation to compute inverse factorials efficiently.

Worked Examples

Example 1

Input

n = 3, pos = 1, k = 0

We have:

m = n - 1 = 2

We need:

$$2 \cdot \binom{2}{0}$$

Quantity	Value
m	2
k	0
C(2,0)	1
Multiply by 2	2

Result:

2

Example 2

Input

n = 3, pos = 2, k = 1

We have:

m = 2

Compute:

$$2 \cdot \binom{2}{1}$$

Quantity	Value
m	2
k	1
C(2,1)	2
Multiply by 2	4

Result:

4

Example 3

Input

n = 1, pos = 0, k = 0

We have:

m = 0

Compute:

$$2 \cdot \binom{0}{0}$$

Quantity	Value
m	0
k	0
C(0,0)	1
Multiply by 2	2

Result:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Factorial and inverse factorial precomputation up to n - 1
Space	O(n)	Stores factorial and inverse factorial arrays

The dominant cost comes from constructing the factorial and inverse factorial arrays. Each requires linear work in n. All remaining operations are constant time.

Test Cases

sol = Solution()

assert sol.countVisiblePeople(3, 1, 0) == 2      # example 1
assert sol.countVisiblePeople(3, 2, 1) == 4      # example 2
assert sol.countVisiblePeople(1, 0, 0) == 2      # example 3

assert sol.countVisiblePeople(2, 0, 0) == 2      # no visible people
assert sol.countVisiblePeople(2, 0, 1) == 2      # single visible person

assert sol.countVisiblePeople(4, 1, 0) == 2      # choose nobody visible
assert sol.countVisiblePeople(4, 1, 3) == 2      # everyone visible

assert sol.countVisiblePeople(5, 2, 2) == 12     # 2 * C(4,2)

assert sol.countVisiblePeople(5, 0, 4) == 2      # all others visible
assert sol.countVisiblePeople(5, 4, 4) == 2      # symmetric endpoint

assert sol.countVisiblePeople(5, 2, 5) == 0      # impossible k

assert sol.countVisiblePeople(100000, 50000, 0) > 0   # large n boundary
assert sol.countVisiblePeople(100000, 0, 99999) > 0   # large n, all visible

Test Summary

Test	Why
(3,1,0)	First example
(3,2,1)	Second example
(1,0,0)	Single-person edge case
(2,0,0)	Smallest nontrivial invisible case
(2,0,1)	Smallest nontrivial visible case
(4,1,0)	No visible people
(4,1,3)	Everyone visible
(5,2,2)	General combination calculation
(5,0,4)	Position at left endpoint
(5,4,4)	Position at right endpoint
(5,2,5)	Impossible visibility count
Large n, k=0	Stress test
Large n, k=n-1	Maximum visibility stress test

Edge Cases

Single Person in the Line

When n = 1, there are no people on either side of pos. The visibility count is always zero. The only choice is whether the lone person chooses 'L' or 'R', giving exactly two valid assignments when k = 0. The formula correctly produces:

$$2 \cdot \binom{0}{0} = 2$$

Maximum Possible Visibility

When k = n - 1, every other person must be visible. There is exactly one valid visibility pattern among the other people, and the person at pos still has two direction choices. Therefore the answer becomes:

$$2 \cdot \binom{n-1}{n-1} = 2$$

The implementation handles this naturally through the combination formula.

Impossible Visibility Counts

The maximum number of visible people is n - 1. Any request with k > n - 1 is impossible. Although the constraints already guarantee k ≤ n - 1, the implementation still includes a defensive check and returns 0 whenever k > m.

Position at Either End

When pos = 0 or pos = n - 1, all potentially visible people lie on one side. It might seem that this changes the counting, but each person still has exactly one visible direction and one invisible direction. Therefore the same combinatorial argument applies, and the formula remains valid without any special handling.