DDSA Solutions

3731. Find Missing Elements

EasyView on LeetCode
ArrayHash Table

Problem Overview

The full original range runs from the smallest present value to the largest.

Intuition

The full original range runs from the smallest present value to the largest. Endpoints are guaranteed present, so only numbers strictly inside (mn, mx) can be missing. Put every nums value in a set, then walk that open interval and list absences in order.

Algorithm

  1. 1Scan once: track mn, mx, and insert each value into a HashSet.
  2. 2For x from mn + 1 to mx - 1 inclusive, if x is not in the set, append it to the answer.
  3. 3Return the list (already sorted by ascending x).

Example Walkthrough

Input: nums = [1, 4, 2, 5]

  1. 1.mn = 1, mx = 5; set = {1,2,4,5}.
  2. 2.Check 2,3,4: only 3 is absent.

Output: [3]

Common Pitfalls

  • •Do not report mn or mx - they are present by construction.
  • •Constraints allow seeding mn=100 and mx=0 because values lie in 1..100.
  • •Values are unique, so a set has size n with no duplicates to worry about.
  • •Empty answer is valid when the range is contiguous with no gaps.
3731.cs
C#
// Approach: Missing values are integers strictly between the array min and max.
// Build a hash set of nums while tracking mn/mx, then scan x = mn+1 .. mx-1 and
// collect every x not in the set (ascending by construction).
// Complexity: O(n + R) time and O(n) space, where R = mx - mn.
public class Solution
{
    public IList<int> FindMissingElements(int[] nums)
    {
        int mn = 100, mx = 0;
        HashSet<int> s = new HashSet<int>();
        foreach (int x in nums)
        {
            mn = Math.Min(mn, x);
            mx = Math.Max(mx, x);
            s.Add(x);
        }
        List<int> ans = new List<int>();
        for (int x = mn + 1; x < mx; ++x)
        {
            if (!s.Contains(x))
                ans.Add(x);
        }
        return ans;
    }
}
Was this solution helpful?

Related Problems