Find All Numbers Disappeared in an Array

Medium Arrays

Given an array of n integers where values are in the range 1..n, find all numbers in that range that are missing. In-place index marking, O(1) extra space.

Sample input

[4, 3, 2, 7, 8, 2, 3, 1]

Sample output

5 6

Solution

def find_disappeared(nums):
    for num in nums:
        idx = abs(num) - 1
        if nums[idx] > 0:
            nums[idx] = -nums[idx]
    return [i + 1 for i in range(len(nums)) if nums[i] > 0]

print(*find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))

function findDisappeared(nums) {
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    if (nums[idx] > 0) nums[idx] = -nums[idx];
  }
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) result.push(i + 1);
  }
  return result;
}

console.log(findDisappeared([4, 3, 2, 7, 8, 2, 3, 1]).join(" "));

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    static List<Integer> findDisappeared(int[] nums) {
        for (int num : nums) {
            int idx = Math.abs(num) - 1;
            if (nums[idx] > 0) nums[idx] = -nums[idx];
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) result.add(i + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> res = findDisappeared(new int[]{4, 3, 2, 7, 8, 2, 3, 1});
        System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

fun findDisappeared(nums: IntArray): List<Int> {
    for (num in nums) {
        val idx = Math.abs(num) - 1
        if (nums[idx] > 0) nums[idx] = -nums[idx]
    }
    return nums.indices.filter { nums[it] > 0 }.map { it + 1 }
}

fun main() {
    println(findDisappeared(intArrayOf(4, 3, 2, 7, 8, 2, 3, 1)).joinToString(" "))
}

func findDisappeared(_ nums: inout [Int]) -> [Int] {
    for num in nums {
        let idx = abs(num) - 1
        if nums[idx] > 0 { nums[idx] = -nums[idx] }
    }
    var result = [Int]()
    for i in 0..<nums.count where nums[i] > 0 {
        result.append(i + 1)
    }
    return result
}

var nums = [4, 3, 2, 7, 8, 2, 3, 1]
print(findDisappeared(&nums).map(String.init).joined(separator: " "))

List<int> findDisappeared(List<int> nums) {
  for (final num in nums) {
    final idx = num.abs() - 1;
    if (nums[idx] > 0) nums[idx] = -nums[idx];
  }
  final result = <int>[];
  for (var i = 0; i < nums.length; i++) {
    if (nums[i] > 0) result.add(i + 1);
  }
  return result;
}

void main() {
  print(findDisappeared([4, 3, 2, 7, 8, 2, 3, 1]).join(' '));
}

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

vector<int> findDisappeared(vector<int>& nums) {
    for (int num : nums) {
        int idx = abs(num) - 1;
        if (nums[idx] > 0) nums[idx] = -nums[idx];
    }
    vector<int> result;
    for (int i = 0; i < (int) nums.size(); i++) {
        if (nums[i] > 0) result.push_back(i + 1);
    }
    return result;
}

int main() {
    vector<int> nums = {4, 3, 2, 7, 8, 2, 3, 1};
    vector<int> res = findDisappeared(nums);
    for (int i = 0; i < (int) res.size(); i++) {
        cout << res[i];
        if (i < (int) res.size() - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int main() {
    int nums[] = {4, 3, 2, 7, 8, 2, 3, 1};
    int n = 8;
    for (int i = 0; i < n; i++) {
        int idx = abs(nums[i]) - 1;
        if (nums[idx] > 0) nums[idx] = -nums[idx];
    }
    int first = 1;
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) {
            if (!first) printf(" ");
            printf("%d", i + 1);
            first = 0;
        }
    }
    printf("\n");
    return 0;
}