Coding Interview: Reverse Array in Place - Whiteboard Thursday

hey guys welcome to another whiteboard Thursday and this week we have a classic interview problem which is how do you reverse an array in place so let's see how we solve it and also at the end I tell you what problem I'm going to cover next week so that you can get a head start and try it out yourself before you watch the video so let's get right into it so basically I have an input as an array right so let me just write it down I is an array and my output should be the same array but reversed ok perfect so let me just go through an example and we'll go into the code after that is that okay yeah perfect so let's say I have 0 1 2 3 4 5 6 and 7 let's say I have these elements the output if this is the input the output will basically be 0 so up with 7 1 swap to it 6 to swap with 5 and 3 so good for right which will then yield 7 6 5 4 3 2 1 and 0 so actually this is pretty straightforward just like I mentioned right now I can I can implement it I just want to make sure that I'm covering all the edge cases so what can be some of the edge cases here the array could be the input maybe could be known in that case I just return now write the array if it is empty there's nothing to reverse so just return an empty array but beyond that I can't really think of any other edge cases so if you don't are there any that that come to your mind okay ok perfect so let me erase this and all you're doing is we are iterating on the array and we were swapping right so let's say I have function let me call it reverse all right it takes it in all right right and then I say array dot or I can I can establish two different indices the start or the front in the back so let me just say front even before I do that let me just handle the edge case that I just talked about right so I will say if not array so basically if array is a falsie value return all right right now let's go into the meat of the logic I will say front equals zero and back back front is basically the first index and back is then array dot length minus one right so what I can do is have a while loop and throughout the time I'm incrementing the front and decrementing back and swapping the elements that way so let's say let me just erase this let's say I'm starting a while loop and the stopping condition would just be that while front is less than back so anytime front is equal to or written back we just stop right there yeah and what I do is I perform a swap operation let's say for the swap function I have a swap function helper function I give it array I give it the front index in the back index and swaps it for me and then I say front plus plus and back - - and that's it and after the while loop is done I just return the array technically I won't even need to return the array because it's doing it in place and the reference will still be there with the calling function but as the output is the array itself you know I will have returned it now let me implement the swap function function swap it takes in array front and back in this case I will have a temp to store the value of the front say temp equals array front then I will say array front equals arrey back and finally array back equals ten and that's that's pretty much it I think this should give us the result which is just reversing VRI so the time complexity for this as we are iterating through the entire array basically it is n over two but it's still linear right so the time complexity is going to be linear I'm not really storing anything sites maybe a couple variables so the space complexity is going to be constant here thanks for watching I hope you liked it and if you did make sure you hit the like button below in next week we are going to cover a Google interview question which is basically if you're given an array in each element in the array corresponds to an index of the same array how do you detect whether there's a cycle in the array or not so try it out yourself if you want more details on the problem or maybe a text version of it I've included it in the description below check it out try it out yourself and subscribe so that you get notified when that solution comes out and I'll see you next week

Channel: Irfan Baqui

Views: 18,135

Rating: 4.852941 out of 5

Keywords: Coding interview, interview problems, whiteboard coding interview, data structures, algorithms, irfan baqui, whiteboard thursday, whiteboard, array, hash map, coding practice

Id: p0VD9Fdlx5A

Length: 7min 7sec (427 seconds)

Published: Thu Nov 30 2017