Sorted Absolute-Difference Sums Across Cyclic Shifts
Hudson River Trading● MediumFULLTIMENEW GRADINTERNOAProblem statement
Given two integer arrays nums1 and nums2 of equal length n, consider every cyclic right shift of nums1.
For a shift of s positions, the value compared with nums2[i] is nums1[(i - s + n) % n]. Compute the sum of absolute pairwise differences for each shift s from 0 through n - 1.
Return all n sums sorted in nondecreasing order. Use 64-bit arithmetic for the differences and sums.
Function
solution(nums1: int[], nums2: int[]) → long[]Examples
Example 1
nums1 = [1, 4, 2, 11]nums2 = [10, 1, 8, 4]return = [7, 13, 25, 25]The four right shifts produce difference sums 25, 25, 13, and 7. Sorting them gives the returned array.
Example 2
nums1 = [1, 2]nums2 = [2, 1]return = [0, 2]Without shifting, the sum is 2. Shifting right once produces [2, 1], whose sum is 0.
Constraints
1 <= nums1.length == nums2.length <= 200-10^9 <= nums1[i], nums2[i] <= 10^9