Get Min Operations
Updated
Problem statement
Developers at Amazon are working on a new sorting algorithm for points on the x-axis of the coordinate system.
There are n points. The ith point initially has a weight of weight[i] and is located at position i on the x-axis.
In a single operation, the ith point can be moved to the right by a distance of dist[i].
Given weight and dist, find the minimum number of operations required to sort the points by their weights. The points are sorted when, read from left to right, their weights increase: every point ends strictly to the right of every point with a smaller weight. Points with equal weight keep their original order: the one with the smaller index must end strictly to the left of the other. Indices and positions are 0-based.
Function
getMinOperations2(weight: int[], dist: int[]) → long
Complete the function getMinOperations2 in the editor below.
getMinOperations2 has the following parameters:
int weight[n]: the weights of the pointsint dist[n]: the distances the points can move
Returns
long int: the minimum number of operations needed to sort the points. Here long int represents a 64-bit integer.
Examples
Example 1
weight = [3, 6, 5, 2]dist = [4, 3, 2, 1]return = 5Indices are 0-based, and point i starts at position i. By weight the points must end in the order index 3 (weight 2), index 0 (weight 3), index 2 (weight 5), index 1 (weight 6), each strictly to the right of the one before. Index 3 stays at position 3. Index 0 must pass 3: one move of 4 takes it to 4. Index 2 must pass 4: one move of 2 gives 4, which is not enough, so it moves twice, to 6. Index 1 must pass 6: one move of 3 gives 4, two moves give 7. The final positions by index are [4, 7, 6, 3], and the moves add up to 1 + 2 + 2 = 5. Moving a point further than needed only pushes the later points further, so 5 is the minimum.
Example 2
weight = [2, 4, 3, 1]dist = [2, 6, 3, 5]return = 4Indices are 0-based, and point i starts at position i. By weight the points must end in the order index 3 (weight 1), index 0 (weight 2), index 2 (weight 3), index 1 (weight 4). Index 3 stays at position 3. Index 0 must pass 3: one move of 2 gives 2, two moves give 4. Index 2 must pass 4: one move of 3 takes it to 5. Index 1 must pass 5: one move of 6 takes it to 7. The final positions by index are [4, 7, 5, 3], and the moves add up to 2 + 1 + 1 = 4, the minimum.
Constraints
2 <= n <= 2 * 10^5, wherenis the length of bothweightanddist1 <= weight[i] <= 10^91 <= dist[i] <= 10^3
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Find Minimum TimeAlphaSense · OA
- Find Minimum TimeBlackRock · OABlackRock interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Minimum Cost of Every K-Capable Model SetTikTok · OATikTok interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximum Alternating-Index Packet ValueInfosys · OAInfosys interview questions
- Maximize Minimum Deployment DifficultyJP Morgan Chase · OAJP Morgan Chase interview questions