Find Missing Values in the Range One Through N

Quick Overview

Find every absent value in the range determined by an integer array length, including arbitrary repetition. Includes fresh examples, input-effect discussion, and a full written reference.

Find Missing Values in the Range One Through N

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Other

# Find Missing Values in the Range One Through N An array `nums` has length `n`, and every entry lies in `[1,n]`. Return all values in that range that never occur in the array. Repeated values may occur any number of times within the array's length. ### Function `vector<int> findDisappearedNumbers(vector<int>& nums)` ### Example 1 ```text Input: nums = [2,2,2,5,5] Output: [1,3,4] ``` The range is one through five. Only `2` and `5` occur, so the other three values are missing. ### Example 2 ```text Input: nums = [2,1] Output: [] ``` Both values in the required range occur. ### Constraints - `n == nums.length` and `1 <= n <= 100000`. - `1 <= nums[i] <= n`. ### Clarifications Return missing values, not missing positions or the repeated values themselves. The domain is determined by the array length. The examples list missing values in increasing order. ### What a Strong Answer Covers - No missing values, many missing values, and repeated occurrences beyond two. - Why every reported value is absent and every absent value is reported. - Time and auxiliary-space bounds, including how output storage is counted. - Any changes made to the input array. ### Follow-up Questions Can you achieve `O(n)` time without extra space, excluding the returned list?

Overview: Find every absent value in the range determined by an integer array length, including arbitrary repetition. Includes fresh examples, input-effect discussion, and a full written reference.

Google logo
Google
easySoftware EngineerOtherCoding & Algorithms
0
0

Find Missing Values in the Range One Through N

An array nums has length n, and every entry lies in [1,n]. Return all values in that range that never occur in the array.

Repeated values may occur any number of times within the array's length.

Function

vector<int> findDisappearedNumbers(vector<int>& nums)

Example 1

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

The range is one through five. Only 2 and 5 occur, so the other three values are missing.

Example 2

Input: nums = [2,1]
Output: []

Both values in the required range occur.

Constraints

  • n == nums.length and 1 <= n <= 100000 .
  • 1 <= nums[i] <= n .

Clarifications

Return missing values, not missing positions or the repeated values themselves. The domain is determined by the array length. The examples list missing values in increasing order.

What a Strong Answer Covers Guidance

  • No missing values, many missing values, and repeated occurrences beyond two.
  • Why every reported value is absent and every absent value is reported.
  • Time and auxiliary-space bounds, including how output storage is counted.
  • Any changes made to the input array.

Follow-up Questions Guidance

Can you achieve O(n) time without extra space, excluding the returned list?