Leetcode 2122: Recover the Original Array

In this problem, one array was “mixed up” and we are trying to recover the original array. Any valid possibility is okay to return and we don’t need to return the entire set of valid answers.

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:
lower[i] = arr[i] - k, for every index i where 0 <= i < n
higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.
Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.

Note: The test cases are generated such that there exists at least one valid array arr.

We are given a few examples:

Examples

Unfortunately, these examples are too easy to solve and don’t offer a lot of insights on how to solve the problem. The way I see the problem, we need to “assign” low or high to signify the number was part of the original low or hi…