Find All Numbers Disappeared in an Array

Problem

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

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

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Solution

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // cyclic sort
        var i = 0;
        while (i < nums.length) {
            var dst = nums[i] - 1;
            if (nums[dst] == nums[i]) {
                i += 1;
            } else {
                swap(nums, i, dst);
            }
        }

        var ans = new ArrayList<Integer>();
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    void swap(int[] nums, int x, int y) {
        nums[x] ^= nums[y];
        nums[y] ^= nums[x];
        nums[x] ^= nums[y];
    }
}

Recent posts from blogs that I like

Painting and Photography: Is it art?

Degas' photos of women bathing, Gérôme supporting photography as a fine art, Pierre Bonnard's snaps of Marthe, and the extreme realism of Ellen Altfest.

via The Eclectic Light Company

How often do LLMs snitch? Recreating Theo's SnitchBench with LLM

via Simon Willison

The virtue of unsynn

via fasterthanlime