Skip to main content
Talentd
Talentd#1 Freshers Platform
Find Work
Learn
Tools
Post a JobFreeJoin Community
TalentdTalentd

Direction Assignments with Exactly K Visible People - Solution & Explanation

MediumMathCombinatorics11 min read
Practice this problem

Problem Statement

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
A person at index pos sees others as follows:
  • A person i < pos is visible if and only if they choose 'L'.
  • A person 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:​​​​​​​

  • Index 0 is to the left of pos = 1, and index 2 is to the right of pos = 1.
  • To see k = 0 people, 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 = 1 person, 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 is 2 + 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 = 0 people, no additional condition is required.
  • The person at index 0 can choose 'L' or 'R'. Thus, the answer is 2.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Direction EnumerationO(2^n)O(1)Useful for understanding the visibility rule or validating small test cases
Combinatorics + EnumerationO(nk)O(n)General solution that counts valid visibility configurations without enumerating all assignments
Combinatorics with Precomputed FactorialsO(nk)O(n)Preferred when many combination queries are needed or constraints are larger

Video Solution

Leetcode 3881 | Direction Assignments with Exactly K Visible People | Leetcode biweekly contest 179 • CodeWithMeGuys • 528 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Direction Assignments with Exactly K Visible People with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer