FastPrep
Problem · Array

Surviving Balls after Directional Collisions

Learn this problem
● MediumSalesforce logoSalesforceFULLTIMEONSITE INTERVIEW
See Salesforce hiring insights

Problem statement

Balls are arranged from left to right. Ball i has direction directions[i], where 1 means right and -1 means left, and positive strength strengths[i].

All balls move at the same speed. A collision occurs when a right-moving ball is immediately to the left of a left-moving ball among the balls that remain.

  • The ball with greater strength survives with its strength unchanged.
  • If the strengths are equal, both balls are destroyed.

Continue until no collision is possible. Return the original zero-based indexes of the surviving balls in increasing order.

Function

survivingBallIndexes(directions: int[], strengths: int[]) → int[]

Examples

Example 1

directions = [1,1,-1,-1]strengths = [5,3,4,5]return = []

Ball 2 destroys ball 1, then ball 0 destroys ball 2. Finally balls 0 and 3 have equal strength, so both are destroyed.

Example 2

directions = [-1,1,1]strengths = [2,7,1]return = [0,1,2]

No right-moving ball has a left-moving ball to its right, so no collision occurs.

Constraints

  • 1 <= directions.length = strengths.length <= 200000
  • directions[i] is either -1 or 1.
  • 1 <= strengths[i] <= 10^9

More Salesforce problems

drafts saved locally
public int[] survivingBallIndexes(int[] directions, int[] strengths) {
    // Write your code here.
}
directions[1,1,-1,-1]
strengths[5,3,4,5]
expected[]
checking account