algoadvance

Leetcode 448. Find All Numbers Disappeared in an Array

Problem Statement

You are given an array nums of size n where nums contains numbers in the range [1, n]. Some elements appear twice, and some elements appear once. Find all the elements from 1 to n that do not appear in nums and return them in any order.

Example

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

Clarifying Questions

  1. Input Constraints:
    • What is the maximum value for n?
    • Can nums array have all unique elements?
    • Can nums array be empty?
  2. Output Requirements:
    • Do we need to return numbers in sorted order?
    • Is it acceptable to return the result in a different order than the example provided?
  3. Space Complexity Constraints:
    • Are there any limitations on the amount of extra space we can use?

Strategy

To solve this problem, we’ll use an in-place algorithm to effectively mark the numbers in the array nums to identify which numbers are missing. This approach will ensure O(1) auxiliary space, not including the output array.

Steps:

  1. Mark Element’s Index:
    • Iterate through each element in the array nums.
    • For each element num, mark the number at index abs(num) - 1 as negative to indicate that abs(num) is present in the array.
  2. Identify Missing Numbers:
    • After marking, any index i that contains a positive value indicates that the number i + 1 is missing from the array.
  3. Collect Results:
    • Collect all such indices and return them as the result.

Code

Here’s the C++ code to implement this approach:

#include <vector>
#include <cmath>

std::vector<int> findDisappearedNumbers(std::vector<int>& nums) {
    std::vector<int> result;

    // Mark each number's presence by negating the value at the corresponding index.
    for (int i = 0; i < nums.size(); i++) {
        int num = std::abs(nums[i]);
        nums[num - 1] = -std::abs(nums[num - 1]);
    }

    // Collect indices with positive values, which indicates missing numbers.
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0) {
            result.push_back(i + 1);
        }
    }

    return result;
}

Time Complexity

This approach efficiently identifies all the missing numbers within the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI