Top 100
Find All Numbers Disappeared in an Array
- Problem
- LC 448
- File
- top100_LC448FindAllNumbersDisappearedInAnArray.java
- Path
- pkg5leetcode/top100/top100_LC448FindAllNumbersDisappearedInAnArray.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC448FindAllNumbersDisappearedInAnArray.java
- Approach
- Mark indices using negation at value positions.
- Complexity
- Time O(n), Space O(1) excluding output
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Find All Numbers Disappeared in an Array | LC 4485 * APPROACH: Mark indices using negation at value positions.6 * COMPLEXITY: Time O(n), Space O(1) excluding output7 */8import java.util.*;9 10public class top100_LC448FindAllNumbersDisappearedInAnArray {11 static List<Integer> findDisappearedNumbers(int[] nums) {12 for (int i = 0; i < nums.length; i++) {13 int idx = Math.abs(nums[i]) - 1;14 if (nums[idx] > 0) nums[idx] = -nums[idx];15 }16 List<Integer> res = new ArrayList<>();17 for (int i = 0; i < nums.length; i++)18 if (nums[i] > 0) res.add(i + 1);19 return res;20 }21 22 public static void main(String[] args) {23 check(findDisappearedNumbers(new int[]{4, 3, 2, 7, 8, 2, 3, 1}).equals(Arrays.asList(5, 6)), "case1");24 check(findDisappearedNumbers(new int[]{1, 1}).equals(Arrays.asList(2)), "case2");25 System.out.println("all tests passed");26 }27 28 static void check(boolean cond, String name) {29 if (!cond) throw new AssertionError("FAILED: " + name);30 System.out.println(" PASS " + name);31 }32}