2122. Recover the Original Array
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```csharp []
public class Solution {
    public int[] RecoverArray(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;

        for (int i = 1; i < n; i++) {
            int candidateK = (nums[i] - nums[0]) % 2 == 1 ? -1 : (nums[i] - nums[0]) / 2;
            if (candidateK <= 0) continue;

            var numberFrequency = new Dictionary<int, int>();
            var outputArray = new List<int>();

            foreach (var num in nums) {
                if (numberFrequency.ContainsKey(num) && numberFrequency[num] > 0) {
                    outputArray.Add(num - candidateK);
                    numberFrequency[num]--;
                    if (numberFrequency[num] == 0) {
                        numberFrequency.Remove(num);
                    }
                } else {
                    numberFrequency[num + 2 * candidateK] = numberFrequency.GetValueOrDefault(num + 2 * candidateK, 0) + 1;
                }
            }

            if (outputArray.Count == n / 2 && numberFrequency.Count == 0) {
                return outputArray.ToArray();
            }
        }

        return Array.Empty<int>();
    }
}

```
['C#']