com.sl.algorithms.search.pigeonhole

Class LinearTimeMNFinder

java.lang.Object

com.sl.algorithms.search.pigeonhole.LinearTimeMNFinder

All Implemented Interfaces:

MissingNumberFinder

public class LinearTimeMNFinder
extends java.lang.Object
implements MissingNumberFinder

O(n) time and O(1) space algorithm to find the first missing positive number.

See Also:

MissingNumberFinder

Constructor Summary

Constructors

Constructor and Description
LinearTimeMNFinder()

Method Summary

Modifier and Type	Method and Description
int	findFirstMissingPositive(int[] nums) First Missing Positive Approach (Reverse of Pigeonhole): you can 'n' balls, you put them into n+1 bins, one bin will remain empty. Phase-1: "approximate" sort to ensure the elements are at their rightful index e.g.
int	findMissingNumber(int[] nums) Complexity: O(n) time and O(1) space. Assumption: no duplicates. Approach: Because we know that 'nums' contains 'n' numbers and that it is missing exactly one number in the range [0..n-1], we can infer that 'n' definitely replaces the missing number in nums. Therefore, if we initialize an integer to 'n' and XOR it with every index and value, we will be left with the missing number.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LinearTimeMNFinder

public LinearTimeMNFinder()

Method Detail

findFirstMissingPositive

public int findFirstMissingPositive(int[] nums)

First Missing Positive

Approach (Reverse of Pigeonhole): you can 'n' balls, you put them into n+1 bins, one bin will remain empty.

Phase-1: "approximate" sort to ensure the elements are at their rightful index e.g. 3 is at 3
Phase-2: detect mis-match i.e. missing-number.

Usefulness: can handle duplicates and space is constant.

Specified by:

findFirstMissingPositive in interface MissingNumberFinder

Parameters:

nums - input array

Returns:

first positive number missing from the array which can contain any integer

findMissingNumber

public int findMissingNumber(int[] nums)

Complexity: O(n) time and O(1) space.

Assumption: no duplicates.

Approach: Because we know that 'nums' contains 'n' numbers and that it is missing exactly one number in the range [0..n-1], we can infer that 'n' definitely replaces the missing number in nums.

Therefore, if we initialize an integer to 'n' and XOR it with every index and value, we will be left with the missing number.

Specified by:

findMissingNumber in interface MissingNumberFinder

Parameters:

nums - input array

Returns:

first non-negative missing number missing from the array which contains 0 to n numbers