Skip to main content
Talentd

Count Robot Groups - Solution & Explanation

Medium2 min read
Practice this problem

Problem Statement

You are given a strictly increasing integer array position, where position[i] is the initial position of the ith robot at time t = 0.

You are also given an integer array speed, where speed[i] is the constant speed of the ith robot in units per second, and an integer distance.

Time is continuous and measured in seconds. A robot or group with speed v moves v * t units to the right over any interval of t seconds.

Whenever the distance between two robots or groups becomes at most distance, they merge into a single group.

If multiple robots or groups satisfy the merging condition at the same time, all merges happen simultaneously. In particular, every connected collection of robots or groups whose consecutive positions differ by at most distance merges into one group.

After a merge, the resulting group takes the current position and speed of the rightmost robot in that group. Once merged, robots never separate.

Return the number of groups remaining after all possible merges have occurred.

 

Example 1:

Input: position = [1,5,6,20], speed = [4,3,2,3], distance = 1

Output: 2

Explanation:

  • Initially, the groups are {R1}, {R2}, {R3}, and {Rā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹4}.
  • At t = 0, the robots R2 and R3 at positions 5 and 6, respectively, merge because they are 1 unit apart. The resulting group moves with the position and speed of the rightmost robot R3. The groups are now {R1}, {R2, R3}, and {Rā€‹4}.
  • Later at t = 2, the robot R1 catches up to the group {R2, R3} and merges with it. The groups are now {R1, R2, R3} and {Rā€‹4}.

Thus, the answer is 2.

Example 2:

Input: position = [1,5,9], speed = [3,2,2], distance = 2

Output: 2

Explanation:

  • Initially, the groups are {R1}, {R2}, and {R3}.
  • At t = 2, the robot R1 catches up to the robot R2 and merges with it. The resulting group moves with the position and speed of the rightmost robot R2. The groups are now {R1, R2} and {R3}.

Thus, the answer is 2.

Example 3:

Input: position = [9], speed = [8], distance = 5

Output: 1

Explanation:

Initially, there is only one group. Therefore, the answer is 1.

 

Constraints:

  • 1 <= position.length == speed.length <= 105
  • 1 <= position[i], speed[i], distance <= 109
  • position is strictly increasing.

Solutions for this problem are being prepared.

Try solving it yourself

Video Solution

Leetcode 4045 | Count Robot Groups | Leetcode weekly contest 518 ā€¢ CodeWithMeGuys ā€¢ 315 views views

Watch 6 more video solutions ā†’

Ready to solve this problem?

Practice Count Robot Groups with our built-in code editor and test cases.

Practice on FleetCode