Problem Brief

Compute Lowest Linking (Connection) Expense

FULLTIMEOA

Within Amazon's highly optimized supply chain framework, trimming operational strain and refining package pathways is vital to maintain seamless parcel deliveries throughout different zones.

This framework consists of n depots, numbered sequentially from 1 to n, each precisely located at its respective index. Every depot holds a distinct holding capacity, described by storageLimit, where storageLimit[i] indicates the holding potential of the depot positioned at index i (using 1-based counting).

These depots are aligned in ascending order based on their holding capacities, implying that each subsequent depot’s capacity is the same or greater than the previous. Every depot must link to a dispatch hub located at an index equal to or greater than its own. Thus, a depot at index i can only form a connection with a hub placed at index j, where j >= i.

For optimal inventory flow, Amazon has installed a principal, high-volume distribution hub at the last depot (position n), acting as the ultimate fallback hub for all depots if required. The expense to link a depot at i to a hub at j is determined by storageLimit[j] - storageLimit[i].

You are provided with several inquiries, each represented as a pair (hubX, hubY), where two temporary, high-capacity distribution hubs are added (or we can call it - deployed) at depots hubX and hubY (1 <= hubX < hubY < n). The task is to compute the least total connection cost for all depots, ensuring each connects to the closest possible hub at or after its index (either hubX, hubY, or the main hub at n).

Note:

This scenario assumes 1-based indexing for the storageLimit list.

Each depot must establish a connection with the nearest hub positioned at or beyond its index to minimize the connection cost.

Each inquiry is standalone — modifications made in one do not influence the next.

Function Description

The func they ask you to implement has the following parameters:

int storageLimit[n]: A non-decreasing list of integers that signifies the storage capacities of depots.

int extraHubs[q][2]: A list where every element is a pair of integers marking the positions of two added distribution hubs for each inquiry.

Returns

long int[q]: the answers for each query

Hello -

Each time I update the last seen, I go through the context again to confirm its correctness. However, mistakes can still happen. If you find anything wrong, please contact me. We continuously try to improve the user experience. Many thanks in advance!🙏 💚

1Example 1

Input

storageLimit = [3, 6, 10, 15, 20], q = 1, extraHubs = [[2, 4]]

Output

[8]

Explanation

In this scenario, there exists q = 1 inquiry featuring two supplementary high-capacity dispatch hubs positioned at hubX = 2 and hubY = 4. After deploying the extra distribution hubs at indexes hubX = 2 and hubY = 4, the resulting connections and costs are determined as follows: The first depot links to the closest reachable dispatch hub at position 2, accumulating a cost of 6 - 3 = 3. The second depot operates as a dispatch hub itself, leading to zero cost. The third depot connects to the nearest accessible dispatch hub located at 4, generating a cost of 15 - 10 = 5. Both the fourth and fifth depots are either distribution hubs themselves or directly connected, contributing 0 + 0 = 0 cost. In conclusion, the total connection expense is calculated as (6 - 3) + (0) + (15 - 10) + (0) + (0) = 8. Thus, the resulting output is [8] for this query.

2Example 2

Input

storageLimit = [0, 2, 5, 9, 12, 18], q = 2, extraHubs = [[2, 5], [1, 3]]

Output

[12, 18]

Explanation

Clarification - In this scenario, we are given n = 6, with storageLimit = [0, 2, 5, 9, 12, 18], and q = 2 inquiries where extraHubs = [[2, 5], [1, 3]]. At the start, there’s a single primary dispatch hub located at depot number n. Therefore, the total initial linking cost amounts to (18 - 0) + (18 - 2) + (18 - 5) + (18 - 9) + (18 - 12) + (18 - 18) = 62. For the first inquiry, two temporary distribution hubs are deployed at positions 2 and 5. The connections and costs unfold as follows: The 1st depot connects to the closest available hub at position 2, generating a cost of 2 - 0 = 2. The 2nd depot acts as a dispatch hub itself, contributing 0 to the cost. The 3rd depot connects to the nearest dispatch hub at 5, yielding a cost of 12 - 5 = 7. The 4th depot links to the nearest hub at 5, causing a cost of 12 - 9 = 3. The 5th depot serves as a hub itself, resulting in zero cost. The 6th depot is also a hub, adding zero to the expense. Hence, the cumulative connection cost becomes 2 + 0 + 7 + 3 + 0 + 0 = 12. Moving to the second inquiry, two more high-performance distribution hubs are set up at positions 1 and 3. The cost breakdown is: The 1st depot is a hub itself, so cost incurred is 0. The 2nd depot connects to the closest available hub at 3, resulting in a cost of 5 - 2 = 3. The 3rd depot operates as a hub itself, so cost is 0. The 4th depot links to the closest hub at 6, adding a cost of 18 - 9 = 9. The 5th depot connects to the nearest hub at 6, with a cost of 18 - 12 = 6. The 6th depot serves as a hub itself, contributing 0 cost. Therefore, the total expense in this inquiry amounts to 0 + 3 + 0 + 9 + 6 + 0 = 18. The final output is [12, 18].

3Example 3

Input

storageLimit = [2, 6, 8, 14], q = 1, extraHubs = [[1, 2]]

Output

[6]

Explanation

In this situation, we are given n = 4 with storageLimit = [2, 6, 8, 14], and q = 1 inquiry where extraHubs = [[1, 2]]. At the start, there exists only a single central dispatch hub stationed at depot number 4. Therefore, the total connection distance is computed as (14 - 2) + (14 - 6) + (14 - 8) + (14 - 14) = 26. For the first inquiry, two temporary high-capacity dispatch hubs are established at indices 1 and 2. The resulting connections and incurred costs are as follows: The first depot functions as a distribution hub itself, leading to zero expense. The second depot also serves as a dispatch hub, hence zero expense. The third depot links to the closest accessible hub located at index 4, producing a cost of 14 - 8 = 6. The fourth depot acts as a hub itself, yielding zero expense. Summing up, the total connection expenditure equals 0 + 0 + 6 + 0 = 6. As a result, the output for this inquiry becomes [6].

Constraints

Limits and guarantees your solution can rely on.

🍑