Recover the Original Array — LeetCode 2122 Python Solution

The problem

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.

Example

Input

nums = [2,10,6,4,8,12]

Output

[3,7,11]

Explanation

If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].

Python solution

class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        for i in range(1, n):
            d = nums[i] - nums[0]
            if d == 0 or d % 2 == 1:
                continue
            vis = [False] * n
            vis[i] = True
            ans = [(nums[0] + nums[i]) >> 1]
            l, r = 1, i + 1
            while r < n:
                while l < n and vis[l]:
                    l += 1
                while r < n and nums[r] - nums[l] < d:
                    r += 1
                if r == n or nums[r] - nums[l] > d:
                    break
                vis[r] = True
                ans.append((nums[l] + nums[r]) >> 1)
                l, r = l + 1, r + 1
            if len(ans) == (n >> 1):
                return ans
        return []

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2122. Recover the Original Array is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems