Gold Chain Equal Splits After Removing One Link
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
A gold chain has n links in their current order, and weights[i] is the positive weight of link i.
Remove exactly one link, reconnect the remaining links without reordering them, and split the reconnected chain into two nonempty contiguous pieces. A method is valid when the two pieces have equal total weight.
Return every valid method as [removedIndex, leftCount], where removedIndex is the original index of the removed link and leftCount is the number of links in the left piece after removal. Order the rows by increasing leftCount, then by increasing removedIndex. Return an empty array when no method works.
The original yes-or-no question is true exactly when the returned array is nonempty.
Function
equalGoldChainSplits(weights: int[]) → int[][]Examples
Example 1
weights = [1,5,3,4]return = [[1,2]]Remove link 1, leaving [1,3,4]. The first two remaining links weigh 4, equal to the final link, so [1,2] is valid.
Example 2
weights = [1,3,4]return = []Removing any one link leaves two links with different weights, so no equal split exists.
Example 3
weights = [1,1,1]return = [[0,1],[1,1],[2,1]]Removing any link leaves [1,1], whose only split has one link on each side. Rows share leftCount = 1 and are ordered by removed index.
Constraints
3 <= weights.length <= 100000.1 <= weights[i] <= 1000000000.- The answer contains at most
2 * weights.lengthrows.