Rearrange array alternately
Вставка
- Опубліковано 29 вер 2024
- This is a very commonly asked arrray based programming interview question. We have rearranged the array alternately using two methods. First method is extremely simple but it takes extra space while the efficient solution do not take any extra space. Just O(1) space. Both takes O(N) time. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
![Rearrange Array so that Arr[i] becomes Arr[Arr[i]] with O(1) extra space #InterviewBit Code C++](http://i.ytimg.com/vi/IEr74xZGNoU/mqdefault.jpg)
If you have already done the problem , only then you could come with O(1) space solution in an interview / test environment .
Otherwise its hard to think of a soln for O(1) space .
It is next to impossible to crack the O(1) space version
@@aakashmehta9474 yeah bro u kinda need to be math nerd to do this how on earth could we figure this logic😂. That to in a interview its almost impossible
Well explained I just had to see for 5 minutes and I understood and coded it myself.
Nice :)
can u share the code?
// naive approach n^2 by shifting
void rearrange(long long *arr, int n)
{
// Your code here
int s = 0;
int last;
for (int i = 0; is; j--){
arr[j] = arr[j-1];
}
arr[s] = last;
s+=2;
}
}
This method will not work if negative numbers are in array. Please provide solution for negative numbers also.
I was asking about the logic behind this formula.
Anyways thanks😇
As I said about the logic. It works so everyone uses it 😅 You can also think about any other method or read in blogs if you can find.
how can you manage when '0' Is in array?
You are already given an arranged array (according to question). So, even if 0 is present, it will be present before 1 and it will be the smallest element and so will ocuur at the 2nd position (in alternate array). You can even have negative numbers (lower than 0) and this algo will still work fine. Just dry run by taking an example array. I am sure you will get it :)
thank you !!
Sir what if the given array is unsorted
First sort the array and then rearrange the array:)
please add the code link
👍🏼
another naive approach that i found O (n^2) time complexity & O( 1 ) space
for i --> 0 to n-1
reverse_elements_between(arr[ i ] , arr[ n - 1 ] )
I can't express how much thankful I am. I read this problem multiple times still could not understand it (plus mere college k teachers to Marsha alah). Thanks a lot for explaining it so well..
Ps: If anyone can recommend some more questions (links) based on this approach i;e storing 2 numbers together, it'd be very helpful.
Welcome bhai :)
if anyone facing issues with the code ,
here it is.....
int maxi=n-1;
int mini=0;
int me= arr[n-1]+1;
for( int i=0;i
The solution is great but it works on sorted arrays only.
I think it's prime focus is to eliminate extra space required. because no matter what technique we use we need to sort the array first to achieve our output.
hello bro!
my question is how can we come up with this formula?
what is the reference for this trick/solution? what is the intuition??
@@Patrick-hb9dbjDividened=Quotient×Divisor+remainder
can u please explain why we are using this formula. how u deducted. becoz, its hard to remember like this. can u pls explain when we need to use this formula. thanks.
Should have explained it. Will improve this.
What is the basic mathematical logic used in efficient solution of this problem??
Is the modulo-technique applicable only for sorted arrays which have elements greater than 0?
wHAT IS WRONG WITH THIS CODE
PLEASE HELP
void rotateRight(long long *arr,int s,int e)
{
int t=arr[e];
for(int i=e;i>s;i--)
{
arr[i]=arr[i-1];
}
arr[s]=t;
}
void rearrange(long long *arr, int n)
{
// Your code here
int i=0;
while(i
kk it works for sorted array only....... anyway thanks for you logic
code in python:
def largest_smallest(a,me):
min_id=0
max_id=len(a)-1
if len(a)
for _ in range(int(input())):
n=int(input())
l=list(map(int,input().split()))
minin=0
maxin=n-1
me=max(l)+1
for i in range(n):
if i%2==0:
l[i]=l[i]+(l[maxin]%me)*me
maxin=maxin-1
else:
l[i]=l[i]+(l[minin]%me)*me
minin=minin+1
for i in l:
print(i//me,end=" ")
print()
##can someone tell me where i am wrong its giving memory error on line 3 but working well for sample test cases
Should we just memorise this formulae? doesn't sound good to memorise a formula just for this one case.
if they ask you this question in an interview, you know you dont want to work there in constant time :p
that's literally impossible for someone to find this strategy if he is not experienced one!!!
Thank you. I have found some explanation on this problem but i found yours easy to understand the most.
Great ❤️
so corner cases like -ve and need to know this form instead using swap on inarray easy-peasy
Please tell the logic behind this trick so that it is easy to remember
Logic is to store 2 numbers at the same place and technique is the formula which you see in the video.
YEH sab theek h socha kse ki yh hoga aur aisa formula koi ekdum kaise soch sakta h
why did we add +1 to maximum element ?
< Correct me if i am wrong >
If the array would contain 10^7 as the maximum element then we would need to store the result it in long which will be taking extra space , whereas in the question it has integer constraints . so at that point it will fail .
You need to store it in long long. But that doesn't count as extra space.
this is giving error for some test cases where input size is 1000000
help!!
Change the data type of the array to long.
Got an intresting Trick XD
XD
it is not working for limit of 1000000 numbers .
can u please help me out
What is the problem you are facing?
Do we really need to mug up coding questions. If there is no generic solution to such question then better not try to remember at all.
Can you give some examples where this technique can be used
Design a special stack with getMin or getMax jn O(1) space. There are many other mathematical problems but I don't remember their names. I found many on codechef.
This solution is good but will not work if array is not sorted or there are any negative elements in array.
I have one question here. The trick is to store two elements in a place. Such that arr % max gives arr[i] and arr[i] / max element gives the re-arrangement. Why not save like this: arr[i] = arr[i] + maxElement * arr[ index of the element that should go here]. Why do not need a mod with max element ?
Try submitting the question. If it gets accepted then you can be absolutely sure about the logic otherwise what may seem to be working may not work for all the cases.
@@techdose4u You are right, Checking :D
i tried this on paper , it shoud work theoretically.
@@1998praneeth I think we are taking modulo to prevent overflow
where is the code
is this work only for already sorted array?because i dry run an unsorted array and i found myself wrong..
How can we just deduce that formula ? I mean the only way is to mug it up.
The simple approach is sufficient for this problem :)
Thanks for the Content Dose 😉
Welcome :)
🔥🔥🔥🔥🔥🔥
solution nahi chahiye....solution soche kaise
:) Samjhaenge don't worry
how we can think these type of Solutions???
how you come up to that formula
Will this work even if the numbers are not consecutive or negative?
Can anyone tell me the modification this technique will need for negative numbers?
Sir, I have written the code using the above approach. But, I am getting a memory error. Could you please explain why is it happening and how to resolve it.
nice ,keep it up
will this work only for sorted array Sir ? please reply
c program to sort odd and even in single array...
pls do sir
Bro can you make a video on how to get into product based companies with 4 months of prepration
I will consider this making. What is your current status? Which year and dept?
@@techdose4u Right now I am in 3rd year Btech(CSE) . Companies have been visiting our college for one year internship + PPO. Amazon will visit our college in august for the same.And Right now I am having 3-4 months free time as our university is closed for 3-4 months.
@@techdose4u You are one of the best coding teacher I can say. Because you talk about the actual idea of the code. Please keep doing that
So, what is your current level of code understanding and solving ability? Based on that I can help you.
@@techdose4u Bro I have almost done all the questions of data structures which are available on this link www.geeksforgeeks.org/must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/
And I can solve all questions of Easy and 50-60% of medium on leetcode and GFG
Which application are you using sir for explaining ?
Will the array be sorted always?
If the array is unsorted ,sort it and implement the algorithm for rearranging the array:)
What setup(app/device) are you using for making videos?
thank u
Welcome
Thanks
Welcome
Good explanation. Thanks a lot.
:)
How to rearrange positive and negative elements in alternative fashion
Nice explanation brother.. thanks for helping
Nice approach
Thanks
Thanks bro
Welcome :)
sir your techniques are amazing but if you will give code it will helpfull to us more.
Please find the code in geeksforgeeks. I use to show the code now but back then I just explained logic 😅
@@techdose4u ok sir
Nice
Thanks :)
thanks a lot for uploading the video man!
Welcome :)
@@techdose4u your work is really great! keep up this great work friend :)
Yea i will :)
👍👍
👍🏼
u have decremented only one time yy
Nice explanation!
After a long time❤️
I have recorded a video in a noisy environment. Let me know if there is noise in the video. Finally back :)
@@techdose4u yeah, i can hear a little bit of noise sometimes but it's not affecting the content though.
@@sambhumahato8320 My room is just beside a busy fourway. Its very noisy in my room. So, i was not making videos. If its not affecting anything then should i continue?
TECH DOSE Yes, Definitely,you should not stop doing this. We r somehow dependent on you.
That was amazing !!
Thanks :)
@@techdose4u I have my google interview tomorrow and late night I'm just watching your videos for revision and intuition
I have to admit I do not fully understand it yet, but I found that the max_element that you use for the modulo operation does not need to be that number per se.
It just needs to be at least 1 bigger than the largest element. For example, for the input [1,2,3,4,5], the max_element according to the video would have to be 6, but any number larger than 6 would also work (7,8,9...infinity)
If anyone has more insights please share, this is blowing my mind.
I think I got the gist of the modulo technique and how it can be generalized to save space.
TLDR: division allows you to store 2 numbers in 1 number. (quotient and remainder)
for example, [1,2,3,4,5,6] and [7,8,9,10,11,12] can be stored together as [20,34,85,114,128,168] to save space.
Then, if you want to get the value from the first one, you just divide by 13 and floor it.
If you want to get the value from the second one, you modulo by 13.
The 13 can be any number bigger than the max value from the 2 arrays, but if you plan to add more values that are bigger, it might help to choose a big value.
How this applies here is that with the O(N) approach we are creating another array, but with modulo, we actually get a free array from math.
This is probably also useful for cryptography, because the [20,34,85,114,128,168] is only useful when we know the key (13), without it, we cannot get back the first 2 arrays.
You will need 1 greater than max value in array but you will have to unnecessarily traverse the array to find the max value. However if you take INT_MAX then you will be guaranteed to have max value unless someone has INT_MAX. Why are you finding it difficult?
@@techdose4u I don't think so, since the original question says the input array is sorted, finding the max value is just getting the last element from input array. You wouldn't need to traverse the array.
I was struggling with how the formula
arr[i] = arr[i] + arr[min_i or max_i] % max_el * max_el
was derived.
But I think I got the general idea after my analysis above.
Not the optimal solution, but you could also do the following, this helps dissect the original formula.
if (i % 2 === 0) { //even
if (i > max_i) {
// this means max_i has been overwritten and needs to be decoded
arr[i] = Math.floor(arr[max_i]/key) + arr[i] * key
} else {
// this means max_i still has the original value
arr[i] = arr[max_i] + arr[i] * key
}
max_i--
} else { // odd
if (i > min_i) {
// this means min_i has been overwritten and needs to be decoded
arr[i] = Math.floor(arr[min_i]/key) + arr[i] * key
} else {
// this means min_i still has the original value
arr[i] = arr[min_i] + arr[i] * key
}
min_i++
}
This swaps the 2 arrays at the end 9:27 , instead of getting [1,2,3,4,5] from %, you'd get [5,1,4,2,3] from %
@@zss123456789 interesting!!