Minimum Triggers to Absorb All Balls - Uber Coding — OA Interview

Here is the full interview question "Minimum Triggers to Absorb All Balls - Uber Coding — OA Interview | ShowOffer" from Uber on ShowOffer.io:

Minimum Triggers to Absorb All Balls - Uber Coding — OA Interview

You are given an array balls, where balls[i] = x represents there is a ball at position x. You are also given an array trails, where trails[j] = y represents there is a trail at position y. You can place triggers on any trail. When a ball lands on a trail, it splits into two new balls that land on the next trail in the direction of the ball. If a ball reaches the end of the trails without encountering a trigger, it is absorbed.

Return the minimum number of triggers needed to absorb all balls.

Examples:

1. balls = [1, 2, 3], trails = [1, 2, 2, 3]

   • Input: balls = [1, 2, 3], trails = [1, 2, 2, 3]
   • Output: 1
   • Explanation: Place a trigger on trail 2. The balls will follow the following paths:
     • Ball 1 -> Trail 1 -> Trail 2 -> Trigger at Trail 2 -> Absorbed
     • Ball 2 -> Trail 2 -> Trigger at Trail 2 -> Absorbed
     • Ball 3 -> Trail 3 -> Trail 2 -> Trigger at Trail 2 -> Absorbed

2. balls = [1, 2, 3], trails = [1, 1, 2, 3]

   • Input: balls = [1, 2, 3], trails = [1, 1, 2, 3]
   • Output: 2
   • Explanation: Place a trigger on trails 1 and 3. The balls will follow the following paths:
     • Ball 1 -> Trail 1 -> Trigger at Trail 1 -> Absorbed
     • Ball 2 -> Trail 1 -> Trigger at Trail 1 -> Absorbed
     • Ball 3 -> Trail 3 -> Trigger at Trail 1 -> Absorbed

Constraints:

• 1 <= balls.length, trails.length <= 10^5
• 1 <= balls[i], trails[j] <= 10^5
• trails has no repeated elements.

Hints:

1. Use a map to store the count of balls at each trail position.
2. Iterate through the trails array and update the count of balls at each position.
3. Keep track of the maximum count of balls at each position.

Solution:

`python def min_triggers(balls, trails): count = {} for ball in balls: count[ball] = count.get(ball, 0) + 1

max_count = 0
res = 0
for trail in trails:
    max_count = max(max_count, count.get(trail, 0))
    if max_count == 1:
        max_count = 0
        res += 1

return res

`

This solution has a time complexity of O(n), where n is the length of the trails array, and a space complexity of O(m), where m is the length of the balls array.