com.sl.algorithms.search.pigeonhole

Class ConstantSpaceDupFinder

java.lang.Object

com.sl.algorithms.search.pigeonhole.ConstantSpaceDupFinder

All Implemented Interfaces:

BaseInterface, Constants, DuplicateFinder

public class ConstantSpaceDupFinder
extends java.lang.Object
implements DuplicateFinder

Reference

Crux: Position of the node with multiple incoming pointers is the duplicate.

Assumption: There is at least one duplicate in the list.

Complexity: O(n) time, O(1) space

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.search.pigeonhole.DuplicateFinder

NO_DUPLICATES_FOUND

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
ConstantSpaceDupFinder()

Method Summary

Modifier and Type	Method and Description
int	findDuplicate(int[] nums) Problem Reference Requirements: 1.

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

ConstantSpaceDupFinder

public ConstantSpaceDupFinder()

Method Detail

findDuplicate

public int findDuplicate(int[] nums)

Problem Reference

Requirements:
1. solve without modifying the original array, else sort and detect would be OK to go with.
2. solve without any additional space, else hash-set would be OK to go with.

Specified by:

findDuplicate in interface DuplicateFinder

Parameters:

nums - input

Returns:

find the first repeating number