LC-2122 Hard LeetCode

2122. Recover the Original Array

Array Hash Table Two Pointers Sorting Enumeration

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 40% Topics: Array, Hash Table, Two Pointers, Sorting, Enumeration

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(n)

import collections


class Solution(object):
    def recoverArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        def check(k, cnt, result):
            for x in nums:
                if cnt[x] == 0:
                    continue
                if cnt[x+2*k] == 0:
                    return False
                cnt[x] -= 1
                cnt[x+2*k] -= 1
                result.append(x+k)
            return True
            
        nums.sort()
        cnt = collections.Counter(nums)
        for i in xrange(1, len(nums)//2+1):
            k = nums[i]-nums[0]
            if k == 0 or k%2:
                continue
            k //= 2
            result = []
            if check(k, collections.Counter(cnt), result):
                return result
        return []

Solution from kamyu104/LeetCode-Solutions · MIT