[Arrays][InterviewBit] Find the duplicate

Find the duplicate

Question:

Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) time and using only constant memory space. 

Here  is the link

 Solution:

So basically you can't use a hashSet initially. So we have to find some way so that the number of checked elements are decreased.

Buckets! These days they are everywhere. We can create equal

  sized buckets here too, and limit the search to a single bucket. What should be the size of such a bucket? If $ \delta = (MAX-MIN)$, and there are $n$ elements, then we can create each bucket of size $$\frac{n}{\delta}$$. But this too will be a $O(n)$ search, so let's do something better.

We can decide to use buckets of size $\sqrt{n}$. 

Now the plan.

We can have $\sqrt{n}$ buckets. While going through all the elements we are given, we can check which bucket it belongs, and then increase the size  of that  bucket. Now the bucket that overlaps will be the one which has the duplicate element. Now, use the hash set. Go again through all the elements and then put the ones in the range in the hash set. Boom. You're done. The element that was already in the hash set will be the duplicate element.

Corner case.

Now this is magical fucking information. When you'll implement this stuff,  you'll realize $\sqrt{n}$ is like never an integer. So you'll have to make an array of buckets of size $\lfloor \sqrt{n} \rfloor+1$ and you'll check if any bucket reaches $\lfloor \sqrt{n} \rfloor$. But there'll be a point when no such bucket will be found because the duplicate is in the last bucket, which doesn't even have a size near to $\sqrt{n}$, so boom you're done. Take care of this case and you'll be okay.

Here is the code:

 

[Arrays] [InterviewBit] Increasing decreasing arrays

Given relationship between consecutive elements of an array, generate the array

Problem statement:

Given a positive integer $n$ and a string $s$ consisting only of letters $D$ or $I$, you have to find any permutation of first $n$ positive integer that satisfy the given input string.
$D$ means the next number is smaller, while $I$ means the next number is greater.
Notes

• Length of given string $s$ will always equal to $n - 1$
• Your solution should run in linear time and space.

Initial Thoughts:

What? How will I generate an array given only the relationship between consecutive elements? Plus they're also dependent upon the elements far after and before the elements. How?

Actual Solution:

Meh. Well after I thought a lot about it, generation can be a greedy procedure. You know how much in total increase is to be done. You also know how much decrease is to be done. The main problem is that once an increase is required, an increase must be done. So, basically you can't increase after the maximum element et cetera.

So I know that $i$ increases must be done after an element and $d$ decreases must be done after an element. So I must leave a gap of $i$ above the element $e$ I will select for the current position, and a gap of $d$ below $e$. That means, I've to select $d+1$th element. 

Meh.

So, the first element will be the $d+1$th element. All increases will go up, and all decreases will go down. So, I can create two pointers $uptr$ that goes up and $dptr$ that goes down. $uptr = d+2$ and $dptr = d$ initially. Everytime, an $I$ comes in the string, I put $uptr$ value in the current position and increase $uptr$ by $1$. 

Similarly, everytime I see a $D$ in the string, I put $dptr$ in the current position and decrease $dptr$ by $1$.

Done. EOD. Hence proved. Fuck off.

Code:

[Arrays] [InterviewBit] [GeeksforGeeks] Maximum Consecutive Gap

Maximum Consecutive Gap

Question Statement:

Given an array, find the maximum difference between its two consecutive elements in its sorted form.

And do that in $O(n)$ space and time, just for the fun of it.

My initial solution:

InterviewBit said that the numbers are all 32 bits, so obviously radix sort was on my mind. Take counting sort for each bit, from right to left. Done in $32 \times n$ time. Then check the maximum gap. Thank God I didn't implement this, otherwise I won't be able to know how to solve this correctly. 

Actual Solution:

Remember PigeonHole principle? Yes. That is what we'll be using here, got damnitwhatthefuckpeopledothesedays.

So, initially find the maximum and the minimum of the array. Done? Now here me out, create $n-1$ buckets each of equal size. 

Now out of $n$ elements two are the minimum value and the maximum value. So, we're left with $n-2$ elements. So it is impossible that each bucket will contain an element. At best, there will be a bucket that'll be empty. And guess what, if a bucket is empty, the gap between the maximum element of the previous bucket and the minimum element of the next bucket is obviously  greater than any gap between two elements inside the same bucket. Right? So what we have to do is put elements in these buckets, and then find the gap between consecutive (alive) buckets. And boop boop we're done.

Here is my code, which you don't give a fuck about: