You are given three integers n, pos, and k.
There are n people standing in a line indexed from 0 to n - 1. Each person independently chooses a direction:
'L': visible only to people on their right'R': visible only to people on their leftpos sees others as follows:
i < pos is visible if and only if they choose 'L'.i > pos is visible if and only if they choose 'R'.Return the number of possible direction assignments such that the person at index pos sees exactly k people.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: n = 3, pos = 1, k = 0
Output: 2
Explanation:
pos = 1, and index 2 is to the right of pos = 1.k = 0 people, index 0 must choose 'R' and index 2 must choose 'L', keeping both invisible.'L' or 'R' since it does not affect the count. Thus, the answer is 2.Example 2:
Input: n = 3, pos = 2, k = 1
Output: 4
Explanation:
pos = 2, and there is no index to the right.k = 1 person, exactly one of index 0 or index 1 must choose 'L', and the other must choose 'R'.'L' or 'R' since it does not affect the count. Thus, the answer is 2 + 2 = 4.Example 3:
Input: n = 1, pos = 0, k = 0
Output: 2
Explanation:
pos = 0.k = 0 people, no additional condition is required.'L' or 'R'. Thus, the answer is 2.
Constraints:
1 <= n <= 1050 <= pos, k <= n - 1Problem Overview: You are given a line of people and must assign each person a viewing direction (left or right). A person is considered visible if nobody taller blocks their view in the direction they face. The task is to count how many direction assignments produce exactly K visible people.
Approach 1: Brute Force Direction Enumeration (O(2^n) time, O(1) space)
The most direct idea is to try every possible assignment of directions. For each of the 2^n configurations, scan the line and check whether each person can see in the direction they face. Visibility can be determined by walking toward that direction until a taller person blocks the view. After computing the number of visible people for that configuration, increment the count if it equals K. This approach works only for very small n because the number of assignments doubles with each additional person.
Approach 2: Combinatorics + Enumeration (O(nk) time, O(n) space)
A more practical solution observes that visibility depends on relative height order rather than the exact configuration of directions. The tallest people determine how far visibility can extend because they block everyone behind them. Instead of enumerating all direction assignments, enumerate how many people contribute to visibility from the left and from the right.
Precompute combinations such as C(n, r) to efficiently count how many ways people can be arranged so that exactly i are visible from the left and j from the right where i + j = K. For each split of K, count the number of valid placements and multiply by the number of direction assignments that keep those people visible. This converts an exponential search into a combinatorial counting problem.
The algorithm iterates over all valid splits of visible people and sums their contributions using precomputed factorials or dynamic programming for combinations. This reduces the search to polynomial time and avoids checking every direction configuration explicitly. Concepts from combinatorics, enumeration, and math-based counting drive the optimization.
Recommended for interviews: Interviewers expect the combinatorics + enumeration approach. Starting with the brute force shows you understand the visibility rule and the search space. Transitioning to counting arrangements using combinations demonstrates algorithmic insight and reduces the complexity from O(2^n) to roughly O(nk), which is practical for typical constraints.
There are pos people to the left of position pos, and n - pos - 1 people to the right.
We enumerate the number of visible people on the left, a, so the number of visible people on the right is b = k - a. If both a and b are valid, the answer increases by 2 cdot \binom{pos}{a} cdot \binom{n - pos - 1}{b}. The factor of 2 comes from the fact that the person at index pos can face either 'L' or 'R'.
For the binomial coefficient \binom{n}{k}, we can precompute factorials and modular inverses for fast calculation.
The time complexity is O(n), where n is the input integer n. The space complexity is O(n) for storing factorials and modular inverses.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Direction Enumeration | O(2^n) | O(1) | Useful for understanding the visibility rule or validating small test cases |
| Combinatorics + Enumeration | O(nk) | O(n) | General solution that counts valid visibility configurations without enumerating all assignments |
| Combinatorics with Precomputed Factorials | O(nk) | O(n) | Preferred when many combination queries are needed or constraints are larger |
Practice Direction Assignments with Exactly K Visible People with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor