Sorted Sums of Absolute Differences Over All Cyclic Shifts of an Array

You are given two integer arrays nums1 and nums2 of the same length n. For each shift t from 0 to n - 1, rotate nums1 cyclically by t positions and add up the absolute differences between the rotated array and nums2, position by position. Return all n sums sorted in non-descending order.

Function Signature

def cyclic_shift_diff_sums(nums1: list[int], nums2: list[int]) -> list[int]:

Rules

• The shift-t rotation of nums1 is the array whose element at index i is nums1[(i + t) % n].
• The sum for shift t is S(t) = sum(abs(nums1[(i + t) % n] - nums2[i]) for i in range(n)).
• Return [S(0), S(1), ..., S(n - 1)] sorted in non-descending order. Keep duplicates: the result always has exactly n values.
• Because every shift is included and the result is sorted, rotating in the other direction gives the same answer.

Constraints

• 1 <= n <= 1000
• len(nums1) == len(nums2) == n
• 0 <= nums1[i], nums2[i] <= 10^6
• Every sum is at most n * 10^6 <= 10^9, which fits in a 32-bit signed integer.

Examples

Example 1

Input: nums1 = [1, 2, 3], nums2 = [3, 1, 2]
Output: [0, 4, 4]

Shift 0 pairs [1, 2, 3] with [3, 1, 2]: 2 + 1 + 1 = 4. Shift 1 pairs [2, 3, 1] with it: 1 + 2 + 1 = 4. Shift 2 pairs [3, 1, 2] with it: 0 + 0 + 0 = 0.

Example 2

Input: nums1 = [4, 0, 6, 1], nums2 = [2, 5, 1, 3]
Output: [4, 6, 14, 14]

The rotations are [4, 0, 6, 1], [0, 6, 1, 4], [6, 1, 4, 0] and [1, 4, 0, 6], giving sums 2 + 5 + 5 + 2 = 14, 2 + 1 + 0 + 1 = 4, 4 + 4 + 3 + 3 = 14 and 1 + 1 + 1 + 3 = 6.

Example 3

Input: nums1 = [5], nums2 = [2]
Output: [3]

The only shift pairs 5 with 2.