duplicate

Searching Questions

Posted on April 4, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Here are some questions on searching Search types Linear Search on Array Binary search on Array - Recursive and iterative Special case of Ranged array By ranged array, I mean that array has some specific size, say N, and numbers in that array can occur in a range of 0 to N-1. I don’t know if some other special name exists for such arrays. But lets go ahead with this name. [Read More]

Find the duplicate element most number of times in array of 0 to n-1

Posted on April 4, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Problem Given an array of n numbers from 0 to n-1, find the element occurring most number of times Solution This problem is similar to following problem : Find the two repeating elements in a given array We can use some of the method used there. Method 1 - Brute force Here we will match the adjacent elements, and increment the count accordingly. Here is the code public int maxDuplicateItemBruteForce(int

A){ int n = A. [Read More]

search kodeknight ranged-array duplicate

Find duplicate elements in the array with 4KB memory only

Posted on April 1, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array? Solution 4KB = 32768 bits. We can use a byte array to represent if we have seen number i. If so, we make it 1. [Read More]

kodeknight System Design And Memory Limits duplicate CrackingTheCodingInterview limited memory

Check if array contains duplicates

Posted on March 31, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

**Problem ** Given an array of n elements, check if it has duplicates Solution This problem is similar to following problem : Find the two repeating elements in a given array We can use some of the method used there. Method 1 - Brute force Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. [Read More]

search kodeknight ranged-array duplicate

Find duplicates in the ranged array

Posted on March 31, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Follow UP - Find these repeating numbers in O(n) and using only constant memory space. Example Input : array = {1, 2, 3, 1, 3, 6, 6}, n = 7 Output = 1,3,6 Solution This problem is an extended version of following problem. Find the two repeating elements in a given array [Read More]

search kodeknight ranged-array duplicate

Find the two repeating elements in ranged array

Posted on March 31, 2014 (Last modified on August 7, 2020) | 7 minutes | Kinshuk Chandra

Problem You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers. Example Input : array = {4, 2, 4, 5, 2, 3, 1} and n = 5, array.length = n+2 = 7 Output : 4,2 Solution This can be achieved by various methods. [Read More]

search kodeknight ranged-array duplicate

Find the two non-repeating elements in a ranged array of repeating elements

Posted on March 31, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Problem Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way. Example Input : {2,4,7,9,2,4} Output : 7,9 Solution Method 1 - Use Sorting First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. [Read More]

search kodeknight ranged-array duplicate

Remove duplicates from unsorted array

Posted on March 25, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

**Problem ** Remove duplicates from unsorted array Example a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3] ```so after that operation the array should look like a[1,5,2,6,8,9,10,3,4,11] Solution **Method 1 - Brute Force - Check every element against every other element** The naive solution is to check every element against every other element. This is wasteful and yields an O(n2) solution, even if you only go "forward". **Method 2 - Sort then remove duplicates** A better solution is sort the array and then check each element to the one next to it to find duplicates. [Read More]

kodeknight duplicate unsorted-array remove-duplicates

Number of unique elements in sorted array with repeated elements

Posted on March 25, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem Find the number of unique elements in sorted array with repeated elements. Follow up - How can you do it without using extra space Example Input = [1,1,1, 2] Output = 2 i.e. 1 and 2. Example for follow up Input = [1,1,2] Output = 2 Solution It’s not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. [Read More]

kodeknight duplicate count sorted-array java

Find the maximum repeating number in array where all the elements are in range 0 to k-1, k ∈ [0,N]

Posted on January 18, 2014 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). [Read More]

kodeknight duplicate array