Direction Assignments with Exactly K Visible People solution and explanation
The problem
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 left
pos sees others as follows:
- A person
i < posis visible if and only if they choose'L'. - A person
i > posis 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:
- Index 0 is to the left of
pos = 1, and index 2 is to the right ofpos = 1. - To see
k = 0people, index 0 must choose'R'and index 2 must choose'L', keeping both invisible. - The person at index 1 can choose
'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:
- Index 0 and index 1 are left of
pos = 2, and there is no index to the right. - To see
k = 1person, exactly one of index 0 or index 1 must choose'L', and the other must choose'R'. - There are 2 ways to choose which index is visible from the left.
- The person at index 2 can choose
'L'or'R'since it does not affect the count. Thus, the answer is2 + 2 = 4.
Example 3:
Input: n = 1, pos = 0, k = 0
Output: 2
Explanation:
- There are no indices to the left or right of
pos = 0. - To see
k = 0people, no additional condition is required. - The person at index 0 can choose
'L'or'R'. Thus, the answer is 2.
Constraints:
1 <= n <= 1050 <= pos, k <= n - 1
Approach overview
Problem 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.
Solution
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.
N = 100001
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
for i in range(1, N):
f[i] = f[i - 1] * i % MOD
g[i] = pow(f[i], MOD - 2, MOD)
def comb(n, k):
return f[n] * g[k] * g[n - k] % MOD
class Solution:
def countVisiblePeople(self, n: int, pos: int, k: int) -> int:
l, r = pos, n - pos - 1
ans = 0
for a in range(min(k, l) + 1):
b = k - a
if b <= r:
ans += 2 * comb(l, a) * comb(r, b)
ans %= MOD
return ansclass Solution {
private static final int N = 100001;
private static final int MOD = (int) 1e9 + 7;
private static final long[] F = new long[N];
private static final long[] G = new long[N];
static {
F[0] = 1;
G[0] = 1;
for (int i = 1; i < N; ++i) {
F[i] = F[i - 1] * i % MOD;
G[i] = qmi(F[i], MOD - 2, MOD);
}
}
public static long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
public static long comb(int n, int k) {
return (F[n] * G[k] % MOD) * G[n - k] % MOD;
}
public int countVisiblePeople(int n, int pos, int k) {
int l = pos, r = n - pos - 1;
long ans = 0;
for (int a = 0; a <= Math.min(k, l); ++a) {
int b = k - a;
if (b <= r) {
ans = (ans + 2 * comb(l, a) % MOD * comb(r, b) % MOD) % MOD;
}
}
return (int) ans;
}
}int N = 100001;
int MOD = 1e9 + 7;
long long f[100001];
long long g[100001];
long long qmi(long long a, long long k, long long p) {
long long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
int init = []() {
f[0] = 1;
g[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = f[i - 1] * i % MOD;
g[i] = qmi(f[i], MOD - 2, MOD);
}
return 0;
}();
long long comb(int n, int k) {
return f[n] * g[k] % MOD * g[n - k] % MOD;
}
class Solution {
public:
int countVisiblePeople(int n, int pos, int k) {
int l = pos, r = n - pos - 1;
long long ans = 0;
for (int a = 0; a <= min(k, l); ++a) {
int b = k - a;
if (b <= r) {
ans = (ans + 2 * comb(l, a) % MOD * comb(r, b) % MOD) % MOD;
}
}
return ans;
}
};const N = 100001;
const MOD = 1000000007n;
const f: bigint[] = Array(N).fill(0n);
const g: bigint[] = Array(N).fill(0n);
function qmi(a: bigint, k: bigint, p: bigint): bigint {
let res = 1n;
while (k > 0n) {
if (k & 1n) res = (res * a) % p;
k >>= 1n;
a = (a * a) % p;
}
return res;
}
f[0] = 1n;
g[0] = 1n;
for (let i = 1; i < N; i++) {
f[i] = (f[i - 1] * BigInt(i)) % MOD;
g[i] = qmi(f[i], MOD - 2n, MOD);
}
function comb(n: number, k: number): bigint {
return (((f[n] * g[k]) % MOD) * g[n - k]) % MOD;
}
function countVisiblePeople(n: number, pos: number, k: number): number {
const l = pos,
r = n - pos - 1;
let ans = 0n;
for (let a = 0; a <= Math.min(k, l); a++) {
const b = k - a;
if (b <= r) {
ans = (ans + ((((2n * comb(l, a)) % MOD) * comb(r, b)) % MOD)) % MOD;
}
}
return Number(ans);
}package main
const N = 100001
const MOD = 1e9 + 7
var f = make([]int, N)
var g = make([]int, N)
func qmi(a, k, p int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % p
}
k >>= 1
a = a * a % p
}
return res
}
func init() {
f[0], g[0] = 1, 1
for i := 1; i < N; i++ {
f[i] = f[i-1] * i % MOD
g[i] = qmi(f[i], MOD-2, MOD)
}
}
func comb(n, k int) int {
return f[n] * g[k] % MOD * g[n-k] % MOD
}
func countVisiblePeople(n int, pos int, k int) int {
l, r := pos, n-pos-1
ans := 0
for a := 0; a <= min(k, l); a++ {
b := k - a
if b <= r {
ans = (ans + 2*comb(l, a)%MOD*comb(r, b)%MOD) % MOD
}
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
Is Direction Assignments with Exactly K Visible People easy or hard?
The problem is generally rated Medium because the brute force idea is simple but inefficient. Recognizing that the task can be converted into a combinatorics counting problem requires deeper algorithmic insight.
Direction Assignments with Exactly K Visible People Python/Java solution
The implementation typically precomputes combinations using factorials or dynamic programming, then iterates over possible splits of visible people. The same logic works across Python, Java, C++, Go, and TypeScript because the core idea is combinatorial counting rather than language-specific data structures.
How to solve Direction Assignments with Exactly K Visible People in O(nk)?
Enumerate the number of people visible from the left and right such that their sum equals K. For each split, use combinatorics to count how many configurations produce that visibility pattern. Precomputing factorials or combination values allows each count to be computed in constant time during the enumeration loop.
What is the best approach for Direction Assignments with Exactly K Visible People?
The combinatorics plus enumeration approach is the most efficient. Instead of testing all 2^n direction assignments, it counts how many arrangements produce exactly K visible people by splitting visibility between the left and right sides. Using precomputed combinations allows the algorithm to run in about O(nk) time with O(n) space.
Is Direction Assignments with Exactly K Visible People asked at Google/Amazon/Meta?
Problems combining visibility rules with combinatorial counting appear in interviews at large tech companies such as Google, Amazon, and Meta. They test understanding of counting techniques, permutations, and the ability to reduce exponential search spaces into mathematical counting problems.
What data structure is used in Direction Assignments with Exactly K Visible People?
The solution primarily relies on mathematical structures such as factorial arrays and combination tables for efficient nCr computation. Some implementations also use simple arrays or dynamic programming tables to store intermediate combinatorial values.
What is the time complexity of Direction Assignments with Exactly K Visible People?
The optimal solution runs in O(nk) time by enumerating how many people are visible from each side and using combinatorial counting to compute the number of valid assignments. Space complexity is typically O(n) if factorials or dynamic programming tables are used for combinations.