Grokking the Coding Interview: Patterns for Coding Questions
Vote

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!
Kaochoy Saetern

Kaochoy Saetern

· 4 months ago

//Why did we change the pattern learned in the previous problem? 
//Isn't the idea to use one similar pattern to solve these?
//Solution based on previous pattern
public class Solution {

    public int findNumber(int[] nums) {
        // TODO: Write your code here
        if(nums.Length <= 1)
            return -1;
        int i = 0;
        while(i < nums.Length)
        {
            int j = nums[i] - 1;
            if(nums[i] != nums[j])
            {
                //wrong position
                Swap(nums, i, j);
            }
            else
                i++;
        }
        //finding the duplicate, after cyclic sorting you can directly check:
        for(i = 0; i < nums.Length; i++)
        {
            if(nums[i] != i + 1)
                return nums[i]; //duplic
J

Jack Tan

· 10 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>
K

kfaham

· a year ago

test case: [3, 1, 3] is invalid

Length is 3, thus range of each element has to be up to 2 based on the constraints given in the problem other wise the fast & slow pointer approach doesn't work

Show 1 reply
C

chillaxspotify

· 2 years ago

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for(auto i = 0; i < nums.size(); ++i)
        {
            auto mark = abs(nums[i]) - 1;
            if (nums[mark] > 0 ) nums[mark] *= -1;
            else 
                return abs(nums[i]);
        }


        return -1;
        
    }
};
P

Pete Stenger

· 2 years ago

Solution doesn't work on [3, 1, 3], which is one of the test cases.

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findNumber(self, nums):
    
    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]

    for i in range(len(nums)):
      while nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    return nums[-1]
V

vetaranto

· 2 years ago

The question (Find the Duplicate Number) should clarify that constant O(1) extra space is allowed given the Python3 solution instantiates a variable (and thus uses extra space).

Renat Zamaletdinov

Renat Zamaletdinov

· 3 years ago

What is the idea behind it?

current = arr[arr[slow]]
Julius Yudelson

Julius Yudelson

· 3 years ago

The fourth test (first hidden) is [5, 5, 5, 5, 5] but the problem states the array contains numbers 1 through N with N+1 numbers in the array.

Show 1 reply
D

d.psawyer

· 3 years ago

Problem reads:

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.

However, we are supplied 5,5,5,5,5 as a test case. Given that the array is supposed to contain n+1 numbers taken from the range 1 to n If the number 5 is anywhere in the range 1 to n, then the minimum array length must be 6

Reading Progress

0%