# Find Original Array From Doubled Array

Published: Sep 15, 2022

Medium Hash Table Sorting Greedy Array

## Introduction

This problem needs a frequency table. While checking the doubled value is in the frequency table, the count should be decremented not to use the same value more than once.

## Problem Description

An integer array `original` is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array `changed`, return `original` if changed is a doubled array. If `changed` is not a doubled array, return an empty array. The elements in `original` may be returned in any order.

Constraints:

• `1 <= changed.length <= 10**5`
• `0 <= changed[i] <= 10**5`

https://leetcode.com/problems/find-original-array-from-doubled-array/

## Examples

``````Example 1:
Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4], [3,1,4] and any order
``````
``````Example 2:
Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.
``````
``````Example 3:
Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.
``````

## Analysis

The first step is to create a frequency table and sort the given array. Start from smallest value and check its doubled value exists and whose count is more than 0. If it does, add the value to the result array and count down. This way, we get the answer.

## Solution

``````class FindOriginalArrayFromDoubledArray:
def findOriginalArray(self, changed: List[int]) -> List[int]:
freq = collections.Counter(changed)
changed.sort()
original = []
for v in changed:
if freq[v]:
freq[v] -= 1
twice = v * 2
if twice in freq and freq[twice] > 0:
freq[twice] -= 1
original.append(v)
else:
return []
return original
``````

## Complexities

• Time: `O(n)`
• Space: `O(n)`