287. Find the Duplicate Number - Detailed Explanation

3. Using a HashSet (or extra memory)

Logic:
We can leverage a data structure to track seen numbers as we iterate. A HashSet (or any set) is ideal because checking for membership and adding elements are on average O(1) operations. As we go through the array:

• For each number, check if it's already in the set.
• If it is, we've found the duplicate.
• If not, add it to the set and continue.

This approach does not modify the original array. The trade-off is it uses O(n) extra space for the set, which violates the strict constant space requirement but is acceptable if memory usage is not a big concern.

Step-by-Step Example (HashSet on [1, 3, 4, 2, 2]):

Initialize an empty set seen = {}.
Traverse the array:

• Read 1: not in seen, add it. (seen becomes {1})
• Read 3: not in seen, add it. (seen becomes {1, 3})
• Read 4: not in seen, add it. (seen becomes {1, 3, 4})
• Read 2: not in seen, add it. (seen becomes {1, 2, 3, 4})
• Read the next 2: this time, 2 is already in seen! This means we've seen 2 before, so 2 is the duplicate. Return 2.

We found the duplicate when we tried to add a number that's already in our set.

Complexity: Checking and adding in a hash set is O(1) on average, so going through n elements is O(n) time.

Space complexity is O(n) for the hash set in the worst case (if the duplicate is at the very end, the set grows to size ~n).

Python Implementation (HashSet):

Example: For the input array 3 1 3 4 2, the two pointers will eventually meet at the value 3, which is the duplicate. The program will output 3. Similarly, for input 1 3 4 2 2, they would meet at 2.

Analysis: This approach runs in O(n) time and uses only O(1) extra space, fulfilling the tough constraints. Floyd’s algorithm is initially non-intuitive for array problems, but it’s a brilliant trick for situations where a "cycle" is formed due to a pigeonhole condition (like this problem). Once recognized, it provides a clean and efficient solution.

Common Mistakes

Beginners often run into a few pitfalls with this problem:

• Modifying the array when not allowed: For example, sorting the array in place or using methods that alter the array (like swapping elements) may violate the problem conditions if the interviewer expects you not to change the input. Always clarify whether modifying input is acceptable. In this LeetCode problem, it specifically is not.

• Using too much extra memory: A solution that uses a data structure like a list or hash map to store frequencies will find the duplicate, but it uses O(n) extra space. If the problem expects O(1) space, that solution, while correct, is not optimal. It’s a common initial solution (and fine for a first attempt), but you should then discuss how to reduce space.

• Brute force on large inputs: Writing a double loop to compare every pair will work logically, but it will time out or be extremely slow for large arrays (like n = 100k). This is a mistake in terms of efficiency.

• Off-by-one errors in binary search: When implementing the binary search on the value range, it's easy to make mistakes with the low and high boundaries or the mid calculation. For instance, not updating low or high correctly can lead to an infinite loop. Always test the binary search logic on simple cases (like a small array) to ensure it narrows down properly.

• Misunderstanding Floyd’s algorithm: A common mistake is to think that the meeting point of the tortoise and hare in phase 1 is the duplicate. It’s not — the meeting point is just an intersection inside the cycle. You must do the second phase to find the actual duplicate. Also, forgetting to reset one pointer to the start for phase 2, or starting them incorrectly, will lead to wrong results or infinite loops. Another subtle bug can be not initializing tortoise and hare to the same starting position. In our solution, we started both at nums[0]. If you start one at index 0 and the other at nums[0] or something different, it won't work correctly.

• Using mathematical formulas incorrectly: One might think of using the formula for sum of 1..n or XOR of 1..n to find the duplicate. For example, computing sum(nums) - sum(1..n) would equal the duplicate if the duplicate appears exactly twice. However, if the duplicate appears more than twice, this difference would be a multiple of the duplicate, not equal to it. Relying on such a trick can be risky and fails for cases where the duplicate count > 2. Similarly, XOR-based methods (XOR of all numbers vs XOR of 1..n) fail when the duplicate appears more than twice (and XOR doesn't directly give counts).

• Not considering all constraints: Not realizing that the numbers range from 1 to n (and not 0 to n or any other range) might lead to confusion. That range detail is crucial for the cycle detection method. Also, not noticing that there is exactly one duplicate (and not multiple distinct duplicates) simplifies the problem — some might try to handle finding multiple duplicates unnecessarily.

Always double-check the problem constraints and ensure your solution logic aligns with them.

Edge Cases

Consider these edge and special cases to ensure your solution handles them:

• Smallest array (n=1): The array of length 2 (since n+1) would be [1, 1]. The duplicate is obviously 1. Make sure the code handles this trivial case (our approaches do handle this: Floyd’s algorithm, for example, would immediately find the cycle of 1 -> 1).

• Duplicate is the smallest number: e.g. nums = [1, 2, 3, 1]. Here n=3, array length 4. The duplicate (1) is at the start and end. Any approach should find 1. This tests if the algorithm correctly identifies a duplicate that occurs at the beginning of the array.

• Duplicate is the largest number: e.g. nums = [2, 4, 1, 3, 4] (n=4, length 5). The number 4 (the max value) is duplicated. Ensure the binary search approach correctly handles the upper half in such a case, and that others also catch it.

• Duplicate in the middle: e.g. nums = [1, 4, 2, 4, 3]. The duplicate is 4 in the middle of the array. This is a normal case but good to test different positions.

• All elements same (except one): This scenario can't fully happen under the given constraints because if one number repeats many times, some other would be missing (violating "all others appear once"). However, a near scenario: if n is large and the duplicate number appears more than twice, e.g. nums = [5, 1, 2, 3, 4, 5, 5] for n=5 (here 5 appears three times and some number appears 0 times, which technically breaks the rule of all others appearing once). The problem constraints avoid this exact case, but our algorithms (especially Floyd's and binary search) would still handle it because the logic only needs one duplicate to exist. It’s worth knowing that Floyd’s cycle detection will still find the duplicate entrance even if the duplicate count is more than 2.

• Nearly sorted array vs jumbled array: Some solutions might fail if they assume something about input order. Our described approaches do not rely on any ordering. For instance, nums = [1, 2, 3, 4, 2] and nums = [2, 1, 4, 3, 2] should both yield 2.

• Performance on large input: If n is at the upper limit (100,000), the solution needs to be efficient. Brute force would never finish in reasonable time. Floyd’s algorithm or the binary search method will handle it fine. It’s good to mentally consider that scale to be confident in your complexity analysis.

Always test edge cases in your mind or with actual code to be sure your solution doesn’t break on the extremes.

Alternative Variations

This problem has a specific scenario (one duplicate in an array of n+1 with range 1..n), but there are several related variations and extensions. Let's discuss a few and how you might approach them:

• Allowing modifications to the array: If the problem did not forbid modifying the array, you could use some neat tricks:

  • In-place swapping (Cyclic sort approach): Since we know numbers are 1..n, one approach is to try to "place" each number at its correct index (i.e., number x should ideally be at index x). You can iterate through the array and swap elements to their correct position (for example, if nums[i] != i and nums[i] != nums[ nums[i] ], swap them into place). During this process, if you ever find that the target position already has the same number, you've found a duplicate. This is O(n) time and O(1) space, but it actively rearranges the array.
  • Marking visited indices: Another trick is to treat the array indices as a hash by marking visited spots. For example, for each number you encounter, go to the index corresponding to that number and negate the value there to mark it visited. If you come across a number whose corresponding index is already negative, that number is a duplicate. This also modifies the array (and you have to be careful to restore it if needed). These methods are efficient but mutate the input array, which was not allowed in the original problem. However, they're great if modifications are permitted or if it’s a different problem variant (like many "find duplicates" problems allow this).

• Multiple duplicates (finding all duplicates): Suppose the array could have more than one distinct duplicate (e.g., two different numbers each appearing twice). An example: [1, 2, 2, 3, 4, 4, 5] has duplicates 2 and 4. The approach changes because Floyd’s algorithm only finds one cycle entrance and the problem guarantee of one duplicate is gone. For finding all duplicates:

  • You could use a hash set to collect all numbers that appear more than once (just check as you go, similar to our HashSet approach but don't break on first found).
  • If modifications are allowed, the negative marking technique (or cyclic sort) can be extended to find all duplicates by marking and checking. LeetCode has a problem "Find All Duplicates in an Array" which specifically asks for all duplicates; the typical solution is to use the index marking trick to get O(n) time and O(1) space.

• Duplicate and missing number together: Another variation is when you have an array of length n (not n+1) containing numbers 1..n, where one number is missing and one is duplicated (often called the "Set Mismatch" problem). For example: [1,2,2,4] (here 3 is missing and 2 is duplicate). This requires finding two numbers: the duplicate and the missing. Floyd’s algorithm doesn’t directly apply because the length isn't n+1. Instead, you can use math: the sum or XOR method can be applied here because the presence of a missing number balances the equations. Or you can modify the array (using index marking or swapping) to detect both anomalies. This is a different problem but conceptually related.

• Different ranges or constraints: If the array values weren’t guaranteed to be 1..n, Floyd’s cycle detection wouldn’t directly work. You might then rely on hashing or sorting. Or if the array is extremely large but numbers are in a smaller range, counting sort or frequency arrays could be considered. Always adapt to the given constraints.

• Continuous input stream or read-only array: If you cannot even read all numbers at once (say it's a stream) or the array is read-only, you might adapt by using the binary search counting method because it only needs counts (which you can accumulate on the fly or via multiple passes). Floyd’s requires random access but not modification, so it still works on read-only arrays.

In summary, the approach can change based on what you're allowed to do:

• If you can sort or modify, simpler solutions become viable.
• If you expect multiple duplicates, you have to collect more than one result.
• If a missing element is involved, combine strategies (like sum/XOR for one missing & one duplicate).

Understanding the core techniques (sorting, hashing, binary search counting, cycle detection, index marking) gives you a toolkit to handle any of these variations.

Related Problems

Learning to solve this problem opens the door to several other algorithmically similar problems. Here are some related LeetCode problems and concepts:

• LeetCode 268. Missing Number: You are given an array of size n containing numbers from 0 to n (one number missing). This is a complement to the duplicate problem. Techniques like using sum or XOR to find the missing number are common. (In a sense, our problem is a "duplicate number" instead of a missing number, but both use the idea of an extra or missing count.)

• LeetCode 41. First Missing Positive: While not about duplicates, it's another problem that uses index marking (cyclic sort idea) on an array with a constrained range (1..n) to find the smallest missing number. It’s good practice for using array index manipulation tricks, similar in spirit to some duplicate finding techniques.

• LeetCode 219. Contains Duplicate II