Sorted Sums of Absolute Differences Over All Cyclic Shifts of an Array
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
Input: nums1 = [5], nums2 = [2]
Output: [3]
```
The only shift pairs 5 with 2.
Overview: Given two integer arrays of equal length, compute the sum of absolute differences between the second array and every cyclic rotation of the first, then return all of these sums in non-descending order. It tests rotation index arithmetic, accumulation over every shift, and exact output ordering.
Read the full Capital One Software Engineer interview experience this question came from
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.
### 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.
### Example 1
```text
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. Sorted, with the duplicate 4 kept, the answer is `[0, 4, 4]`.
### Example 2
```text
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. Sorted, the answer is `[4, 6, 14, 14]`.
### 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: no value exceeds 2^31 - 1, so `int` is enough in Java and C++.
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 (no value exceeds 2^31 - 1).
Examples
Input: ([7], [7])
Expected Output: [0]
Explanation: Minimum n = 1 with equal values: the only shift pairs 7 with 7.
Input: ([5], [2])
Expected Output: [3]
Explanation: Source example 3: n = 1, the only shift pairs 5 with 2.
Hints
- Work through Example 1 by hand: for each shift t, write out the rotated array using index (i + t) % n, then pair it with nums2 position by position.
- Each of the n shifts contributes exactly one sum, even when two shifts give the same value, so the result always has length n.
- Compare the shift-order sums in Example 2 (14, 4, 14, 6) with the expected output, and check the constraints to see how much work per shift is affordable.