Array

Find the Duplicate Number

Problem Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.There is only one repeated number in nums, return this repeated number.

Learning: First that repeating number can occure more than twice this is a common mistake in this question. Now we have trival solution like sorting and hashmap but they can be be further optimized. The ideas is to map the number to its index and if the number and index is already same then we have found the repeating number. We have a two pointer approch as well Floyd’s Tortoise and Hare (Cycle Detection) read the editorial for more details.

Find All Duplicates in an Array

Problem Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

Learning: Swaping logic from the above question can be used here as well.