2007. Find Original Array From Doubled Array

Time: O(n log n)

Space: O(n)

Approach

Sort array; use a queue/map to match each element with its double; build original array.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Hash Table

Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.

2007.cs

// Approach: Sort array; use a queue/map to match each element with its double; build original array.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public int[] FindOriginalArray(int[] changed)
    {
        List<int> ans = new List<int>();
        Queue<int> q = new Queue<int>();

        Array.Sort(changed);

        foreach (int num in changed)
        {
            if (q.Count > 0 && num == q.Peek())
                q.Dequeue();
            else
            {
                q.Enqueue(num * 2);
                ans.Add(num);
            }
        }

        return q.Count == 0 ? ans.ToArray() : new int[] { };
    }
}

Was this solution helpful?