Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Find the Duplicate Number

Problem Statement

We are given an unsorted array containing ‘n+1’ numbers taken from the range 1 to ‘n’. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

Example 1:

Input: [1, 4, 4, 3, 2]
Output: 4

Example 2:

Input: [2, 1, 3, 3, 5, 4]
Output: 3

Example 3:

Input: [2, 4, 1, 4, 4]
Output: 4

Constraints:

  • nums.length == n + 1
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • All the integers in `nums

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jack Tan

· 9 months ago

<p>Hey Guru,</p><p>The solution in this extra problem seems quite convoluted but it only has minimum explanation. As a mediocre learner myself, I spent a lot of time on it, I was stuck and I felt upset about not fully understanding it.</p><p>From the perspective of good course content design, if the extra problem is important, you should list it as a stand-alone problem and give a detailed explanation, even a video explanation like what NeetCode does; If the extra problem is not important, since the solution is convoluted, it's better to remove it to avoid blocking the learners.</p><p>This is just my two cents. What do you think?</p><p>Thanks!</p>