448. Find All Numbers Disappeared in an Array

Problem Statement

Related : Pattern 1-n range array 41. First Missing Positive

---

Solution

// self-freq array approach
public List<Integer> findDisappearedNumbers (int[] nums){
	// code here
	List<Integer> missing = new ArrayList<>();
 
	// mark indices of array values as negative
	for (int num : nums){
		int absNum = Math.abs(num);
		if(nums[(absNum-1)] > 0)  nums[absNum-1] *= -1;
	}
	
	// therefore missing values are positive
	for (int i = 0; i < nums.length; i++) {
		if(nums[i] > 0) missing.add(i+1);
	}
	
	return missing;
}

Notes

• This can also be done with the Cycle Sort method