algoadvance

Leetcode 448. Find All Numbers Disappeared in an Array

Problem Statement

You are given an array nums of n integers where nums is in the range [1, n]. Some elements appear twice and others 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. Q: Can the array nums contain negative numbers or zero? A: No, nums contains only positive integers in the range [1, n].

  2. Q: Can the output order be any order? A: Yes, the numbers can be returned in any order.

  3. Q: Can nums be empty? A: The problem implies nums has a length of n where n >= 1.

Strategy

We can solve this problem in an optimal way without using extra space (ignoring the space for the output array). Here’s the step-by-step plan:

  1. Iterate over the array nums.
  2. Use the value of each element to mark the corresponding index in the array as visited by negating the value at that index.
  3. After processing all elements, the indices of the positive values represent the numbers that are missing from the array.
  4. Collect these missing numbers and return them.

Detailed Steps

  1. Marking Visited Indices:
    • For each number num in nums, determine its corresponding index as abs(num) - 1 (use absolute value because numbers might already be negated).
    • Negate the number at this index to mark it as visited: nums[index] = -abs(nums[index]).
  2. Finding Missing Numbers:
    • Iterate over the modified array nums. For each index i (from 0 to n-1), if nums[i] is positive, it means the number i + 1 didn’t appear in the array.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        // Step 1: Mark the visited index
        for (int num : nums) {
            int index = Math.abs(num) - 1;
            nums[index] = -Math.abs(nums[index]);
        }
        
        // Step 2: Collect all indices which are still positive
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        
        return result;
    }
}

Time Complexity

This solution also uses O(1) extra space, not counting the space needed for the output list.

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