Amazon Coding Interview Question - Rotate Image

[@asmarc1]

I love how you walk through the "inefficient" method first, and then explain how to optimize. That's so helpful for learning how to get from "this works" to "this works really well." Thanks!

[@javiergavilanmerida2133]

First of all, sorry for my really bad english, understand its ok for me, but when I want to say something...well, this is the result xD Im not sure at all that the first method is the "inefficent". If you want the lowest time, the first method is the right answer, if you want to use the lowest memory, then take the second method. The first method is O(n) on time, but O(2n) on memory, and this second is O(2n) on time, but O(n) on memory. All depends on your requirements.

[@jonaskoelker]

> All depends on your requirements. I can think of three kinds of requirements: - for reasons of program (de)composability and understandability, leave the input unmodified. - for reasons of memory consumption, do the operation in place. - for reasons of time efficiency, only read the input once and only write the output once. - for reasons of readability, make sure every step is simple even if you do a few more steps. The first two are mutually incompatible. I actually think the version with the first requirement is the most interesting. There are two obvious solutions: read the input in memory order (writing out each element when you read it), and write the output in memory order (reading each element when you need it). I have no idea which is faster. I'm guessing it depends on array sizes and memory architecture and all sorts of low-level details you'd have to measure. I guess both do well by requirement number 4. If it has to be in place but we can iterate multiple times, I like transpose-and-mirror solution. A fun fact of geometry: combining any two reflections always gives you a rotation. I should do the matrix math to work out the rotation as a function of the reflections. It's non-obvious that the particular two reflections do the trick, but hey it works. And it does well by requirement number 4. Lastly, for time and memory efficiency, do it in-place while reading and writing each element at most once. My obvious idea is to pick an index i, move the value from there to its new location j, move the value previously at j to its new location k, move the value at k to m and move the value at m to i (use a variable to temporarily store the value you're overwriting). Then pick the next index you haven't done yet, do that; repeat until you've done all indices. I'm partial to breaking the square matrix into a bunch of concentric square-borders, going outside in. That is, in effect, first you rotate the leftmost N-1 elements into place as the topmost N-1 elements of the right column; the previous right column goes to the bottom row etc.; then you rotate N-3 elements (centered, rounding to the left) of the second row into the second-from-the-right column, etc.; then N-5 elements from the third row, N-(2*k-1) elements from row k, etc. This last solution is not pretty but it gets the job done. So if we have to meet requirement 2, it seems requirements 3 and 4 are also mutually incompatible.

[@The1Jebrim]

It’s not even the best solution, especially once you try to scale this up to really large matrices. It does nothing to leverage SIMD instructions. A fragment shader on the GPU would also be able to handle rotating very large images quite a bit more rapidly than any CPU-based algorithm.

[@nlmaster9811]

First method is significantly faster, it's a space/time trade off.

[@nlmaster9811]

A better solution would involve a row wise algorithm to take advantage of CPU caching.

[@fahadhayat_]

When transposing the matrix rather than for j = i, instead to j=i+1 (this will save you that extra step of swapping same indicies such as 0,0 or 1,1 or 2,2)

[@sznio]

transpose, then mirror.

[@spiderous]

Witam pana z Polski

[@maxmuellerm]

Every rotation is the product of two reflections.

[@fritt_wastaken]

but there is a faster way, you can do it with a single operation per element

[@leondaz]

@@fritt_wastaken care to explain

[@ashleywilkonson386]

@@fritt_wastaken It is still quadratic time so it doesn't matter.

[@abhishekchaudhary2189]

I followed the exact intuition. Though took some time to code. I also saw one interesting approach, where we swap 4 elements starting from corner and moving inwards. It was interesting to see how concise and faster it was.

[@christiansanchez7448]

Mind dropping a link to the other approach?

[@Vertraic]

@@abhishekchaudhary2189 My first thought was to do it the way he showed at the beginning. It does double the space, but the time is relatively short so it depends on how worried you are about space. My second thought was this method. Takes a bit more planning to make it easily loopable, but still only passes through each position once, and maintains space requirements to only a single extra value.

[@MrTortoed]

That was my idea also. Should be less vsriable accesses. And also less readable and understandable

[@marwanssalem]

I had that Idea but could not code it or think of an efficient way to do it :(

[@1234567qwerification]

​@@MrTortoed I think it saves mostly the loop variables access: in two loops you swap 2 numbers n*2 times, in one loop you rotate 4 numbers n times. In many languages, a multiple assignment is possible: a,b = b,a; a,b,c,d = b,c,d,a; (What exactly is done inside depends on the compiler and its optimizations.)

[@beepIL]

11:56 I just did a for loop with a while loop inside it, felt more intuitive to understand (at least for me) Having a left and right pointers, and the while loop is while(left < right) this way you just advance and reduce left++ , left-- at each iteration to bring them together. swapping the values between them as you go, so it would be matrix[i][left] = matrix[i][right]

[@92AkshaySharma]

I find this explanation more intuitive than the one given in cracking the coding interview

[@sammndl9592]

Just started CP a few days ago and arrived at this problem. I initially solved it by storing entire rows and columns in separate vectors and just replaced the original ones with the 90° shifted ones (i.e. for top row, it would be leftmost column and so on...) and looped it for each layer. I spent the night, thinking of ways to improve. And then this exact method struck me. So much better when it comes to time and space complexity both!

[@nasirsiddiqui7573]

interesting question. i'm not a programmer per se, but a physics academic and a lot of my research is coding intensive. tried doing this problem in python for lulz and i got it to work lol def rotate_90(matrix): size = len(matrix) lst_main = np.array([] , dtype = int) for j in range(size): dummy_array = np.array([] , dtype = int) for i in range(size): dummy_array = np.append(dummy_array , matrix[i][j]) lst_main = np.append(lst_main , np.flip(dummy_array)) return lst_main.reshape(size , size)

[@gregorythomas6037]

To solve the same problem in python this is all you need to do: n = len(matrix) return [[matrix[c][r] for c in range(n-1, -1, -1)] for r in range(n)] And that's if you don't just use the transpose function from the numpy package

[@joecamroberon9322]

And this is why I dislike python. Too much abstraction

[@hypnogri5457]

JoeCamRoberon You donˋt need to use this method though?

[@chrishamilton1728]

Yeah python is great, but this creates a new array, like in the first example. I think the challenge came from rotating the array in place.

[@fardinahsan2069]

@@joecamroberon9322 You don't need to use that method, you can do it exactly the way done in the video, which is what I did for i,v in enumerate(a): for j,z in enumerate(v): b[i][j] = a[-(j+1)][i]

[@ArielFamilyRamatGan]

In your solution, every member is swapped twice, that is O(2 x (n^2)). Matrix rotation can also be done in onion layers manner, outer to inner, where each number is placed once, in O( n^2). something like: public class RotateMatrix { public static void main(String[] args) { int[][] m = new int[][] { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, { 21, 22, 23, 24, 25 }, }; printM(m); rotateMatrix(m); printM(m); } static void printM(int[][] m) { System.out.println(" "); for (int x = 0; x < m.length; ++x) { System.out.println(""); int[] row = m[x]; for (int y = 0; y < row.length; ++y) { System.out.print(row[y] + "\t"); } } } static void rotateMatrix(int[][] M) { int N = M.length - 1; if (N HIGH; --index) { int tempUP = M[HIGH][index]; M[HIGH][index] = M[N - index][HIGH]; M[N - index][HIGH] = M[LOW][N - index]; M[LOW][N - index] = M[index][LOW]; M[index][LOW] = tempUP; } --LOW; ++HIGH; if (HIGH + 1 == LOW) return; if (LOW == HIGH) return; } } }

[@PetterPet]

Tetris programmers: “I’ve been waiting for this for my entire life!”

[@BlastinRope]

No joke if you want a good project that can be held to external standards, you can find the official tetris mechanics and even a design manual to guide you in making a tetris clone on the tetris wiki

[@michaellieberman114]

There's a way to save memory by not using a temp variable. for example: swapping ints x and y: x += y; y = x - y; x -= y;

[@stevetodd7383]

That can fail due to arithmetic overflow. Try using binary exclusive OR instead, i.e. x = x ^ y; y = y ^ x; x = x ^ y;

[@user-lc8jd6sn2b]

@@stevetodd7383 how does that work

[@naru235]

@@stevetodd7383 The addition/substraction method does not fail when wrapping overflow arithmetics are used. But I really like your method, because it's more general.

[@sfcs3743]

@@user-lc8jd6sn2b A XOR A = 0 //zero (Truth Table definition) 0 XOR A = A (Truth Table def.) x = x ^ y (The first assignment) //for y: y = y ^ (x ^ y) //This is commutative and associative, thus: y = (y ^ y) ^ x y = 0 ^ x y = x //for x: pretty much the same logic using associative and commutative properties when chaining XOR x = (x ^ y) ^ x x = (x ^ x) ^ y x = 0 ^ y x = y

[@codestorywithMIK]

Use : y = (x+y) - (x=y) ; isn't it cool 😅

[@KEA1902]

Correct me if I wrong, but as far as you use nested loops for processing 2d arrays, your complexity cannot be O(2n). It is rather O(n^2)

[@jugheadjones5473]

I am also thinking about it

[@philnguyen834]

Since it is 2D array, 2 for loops are for running to every elements once.

[@KEA1902]

@@philnguyen834 If you have 3x3 array, for each nested array which amount is 3, you have 3 iterations through it’s elements, so that you receive 9 iterations, not 6.

[@TeiKagome]

The complexity is O(n) with n being the numbers of value in the matrix (n = N^2). When you transpose or flip the matrix, you must read every value to write it back where you want, so the complexity of these operations cannot be any lower than O(n). It's just that n is square of the matrix height/width.

[@OMGclueless]

​@@TeiKagome You're given directly in the problem statement that the input is an n x n grid. n is not the square of the height/width in this problem, it is the height/width itself. And in terms of that dimension, an optimal solution is O(n^2).

[@alek282]

I so prefer this solution as opposed to doing swaps on 4 elements going from outter square to inner. Great video!

[@PaintedPapaya]

This way is easier but outer to inner is twice as fast

[@user-mw1qb5kd9l]

I'm really happy that for once I when and code first instead of just watching and forgetting. I don't know if I miss understood his explanation but I think I did a bit different : I did a loop that would read the values vertically, column by column, and paste them on other matrix horizontally, left to right.

[@ringtone_rhythm]

These videos are A+, love the editing.

[@michaelalbert7662]

Dude your videos are so helpful, I’m still a beginner w coding and watching these lays out so plainly and cleanly the thought process/methods behind all these problems. Helps me so much w knowing how to attack similar problems! So glad ur making this content keep it up my guy, if I weren’t a broke college student I’d be sending money ur way

[@richardgmiami]

Once again, my solution (while workable) isn't quite as good. I do kind of like my method of saving space where the original array gets deleted once part of it is copied. Code (python) below if anyone is interested. Anyways, great solution. These videos are helping me to think beyond just solving the problem (which is usually not all that hard) and get into space and computing efficiency. Keep them coming! def rotate(array): target = [] # create place to store roatated image for i in array: target.append([]) # ensure that target is the same size array for ii in range(len(target)): for i in range(len(target)): target[i].insert(0, array[0][i]) del array[0] # delete part of array already copied (top row) return target

[@iarbainaltainvantdevara]

Your videos are the best! You are an excellent teacher, the choice of problems and the way you go through them makes everything really fun to learn!

[@parthapratimghose173]

For those who are wondering For anti clockwise shift do the same transpose in 1st step Than the swap will be first row line and last row line Done 👍

[@togelian]

I would do it with a fourway swap. It's a little more complex, but I just love the symmetri of it :)

[@dkwroot]

If you want to rotate -90deg, it's almost identical. Just transpose like normal, then mirror vertically using: swap(array[ x ][ y ] , array[ N-1-x ][ y ] )

[@hawsh3066]

look's like youtube algorithm love these thumbnails ++ Congrats on 1 mill vews

[@yackamajez]

Pretty sure this exact question was on one of my exams for my data structures test lol

[@sannge6471]

Your explanation skills have improved a lot. Much better than leetcode series

[@incription]

Fortunately I’ve already done this multiple times when visualising things like bifurcation maps and Mandelbrot sets

[@josephvictory9536]

Took me a fairly long time the very first time i did this. But i figured i could take advantage of python's pointer swapping to swap all 4 corners simultaneously and work around and then inward. 90 degree clockwise rotation for all matrix where height==width: for i in range(len(matrix)//2): for j in range(i, len(matrix) -1 -i) matrix[i][j], matrix[j][-i-1], matrix[-j-1][i], matrix[-i-1][-j-1] = matrix[-j-1][i], matrix[i][j], matrix[-i-1][-j-1], matrix[j][-i-1]

[@Kuraudo_VII]

I remember doing this problem and just swapping the 4 corresponding positions while going through a quarter of the matrix in the double for loop. That way, it only takes 1 double for loop making it O(n^2). Slightly better than O(2n^2) of the solution you are introducing. However, defining the swap was pretty confusing, something like: len = matrix.length size = len - 1 for i in 0..

[@kvozart8437]

8:21 - you swaping diagonal; 10:58 - "j < (N/2)" DO NOT calculate in conditions, at least use "N >> 1"

[@Grassmpl]

Yeah he should have j=i+1

[@04decranjansaha]

This is a great way. It broadens the way we programmers can think. I was thinking of another solution where I think it can be done in one swap. i,j -> j,N-1-i where N is the side of the square or the array length Please let me know if it would solve the problem with lesser time.

[@Blade4dooooom]

best approach i’ve seen yet, i can easily write and explain a solution intuitively now. thank you!

[@robertosoriano9617]

Just by looking at it, I think the formula would something like: arr[row][col] becomes arr[col] [ ( length of array - 1 ) - orig column Index]------------------ in a 4x4, elem in arr[3][2] goes to arr[2][0]. Please Let me know if this is accurate.

[@bhavyajain638]

Yes correct. But how will you implement it.

[@porigonopop]

Changing the data structures may allow constant time and constant space, we just have to change the coordinate system by the number of rotation we want. But it require a new integer that store the rotation to apply when we want to read/write to the array and it change the type int[][] to something new so not what we want I guess, still might be an interesting solution

[@rdoetjes]

Ever heard of matrix multiplication? Matrix multiplied by 2/pi is a rotate 90 degrees. And there are some incredible efficient array multiplication libraries.

[@AllanSavolainen]

Hmm, I would have done this with 4 temp variables and 4 pointers that scan the whole array in spiral manner, this way I would only need to visit and move every cell just once.

[@Grassmpl]

Yes that's what I suggest.

[@harrymuir6625]

Oh man, most of the exercises about 2d arrays are so difficult to solve, well at least for me...

[@xXZian6Xx]

It takes practice bro

[@JaiSaiSriSai]

def rotateImage(arr): m = len(arr) for i in range(m): for j in range(m): arr [i][j] = arr[m-1-j][i] return arr a = [[1,2,3], [4,5,6], [7,8,9]] rotateImage(a)

[@iggy9121]

I presume this was a mistake, but at the end you said that the transpose-reverse solution “its 2N but you drop the constant so it’s actually just N”. However isn’t the overall complexity of this algorithm N*N? In your first loop you have a nested for loop which is definitely N*N but in the second we have N* (N/2) but I’m a Big-Oh sense that’s just N*N. Overall great problem and thanks for proposing this problem for us to think alongside you

[@marwanssalem]

this problem is in crsckig the coding interview, I had a solution where the matrix was split into frames within eqch other and to solve the problem I rotate each frame n-1 times until i reach the innermost frame..but I couldnt code it ... this much more efficient

[@pyroghost11]

OMFG, I had to solve the exact same algorithm in my bootcamp on the first exam after just 1 month !!!

[@brooksgunn5235]

Which bootcamp are you a part of?

[@SweatySockGaming]

pyroghost11 what bootcamp

[@pyroghost11]

@@brooksgunn5235 It was last year, one in Budapest called Greenfox Academy, as I'm Hungarian.

[@lvlinty]

Imo, if we're willing to drop the constant in time complexity it may make sense to drop the constant in space complexity and use the naive approach at O(n) time. Should run twice as fast as the in place method here.

[@tanishqsojwal2370]

The solution seems wrong. The swapping loops, in the beginning, are swapping the elements twice. You could "int j = i + 1" to correct it.

[@erick_ac]

I made a lil Tetris game and to rotate the pieces I just wrote a function that reads the image from different perspectives

[@RaviKishore1993]

How soon did you realize your links are broken ?

[@nareshg7292]

they are fine . what the hell is wrong with you?

[@RaviKishore1993]

@@nareshg7292 😐

[@sajayrrr]

@@nareshg7292 it isnt working tho? You sure about that mate?

[@shinda1020]

In game industry: allocate a UAV of dimension m*n. Kick off a compute shaders of [m, n, 1] thread groups to copy corresponding element. Copy back from graphics memory

[@SoyDelSouth]

The flip horizontally algorithm I still couldn't grasp the n-1-j. So an easier way that I've been doing two pointers is this. Has a bit more lines, but it just makes sense in my head lol: def _flip_horizontally(arr): n = len(arr) for i in range(n): p1 = 0 p2 = n - 1 while p1 < p2: tmp = arr[i][p1] arr[i][p1] = arr[i][p2] arr[i][p2] = tmp p1 += 1 p2 -= 1 return arr

[@ri-gor]

I would probably first ask if the system is going to be using a lot of image transformations, and if it is I would probably just use a structure that encodes a top left and bottom right pixel coordinate so I don't have to actually move any data around other than those indices. Of course, that would only be a good idea if there were a lot of transformations happening to the picture(s), but that reduce the workload on whatever computer is rotating the images with just a few bytes of extra storage per picture.

[@piyushkandwal]

But the time complexity is O(n^2). Is there any better solution available?

[@LeandroSilva-im2bs]

I'm in no way saying that my solution is perfect, but I was able to get it down to O(n): ``` const rotate = arr => { const len = arr.length; const out = Array(len).fill(0).map(_ => []); for (let i = 0, row = 0, col = len; i < len ** 2; i++, row++) { if (i % len === 0) { row = 0; col--; } out[row][col] = arr[len - col - 1][row]; } return out; } ``` In this case, I feel that time complexity is much more valuable than space complexity.

[@piyushkandwal]

@@LeandroSilva-im2bs Thanks

[@sigma4337]

I actually think because it's a square and you have rows and cols equal to the square root of n the flip has a number of swaps equal to root n times by root n over 2 so the big O is actually only n.

[@33alexramirez]

NxM is actually the smallest possible runtime complexity for the problem, even the new matrix solution has NxM time complexity.

[@sigma4337]

@@33alexramirez where is the value for M coming from?

[@jameschen2308]

Group theory baby!!!! You could also do vertical mirror followed by transpose.

[@joaogabriels.f.5143]

Better solution: don't move anything. Just iterate in a way that translate the [I][j] to the indexes of the corresponding rotated matrix, like this: Like the lines become columns, the columns become the lines, so with that we can formulate a iteration that gets the rotated matrix: [N - 1 - j] [i]

[@joaogabriels.f.5143]

The point is: why waste time changing the matrix context when we can just iterate it with the shape we want?

[@itaytabib4665]

It's kind of weird because whatever you do this pretty much has to be around n^2 steps.. So hear me out: There's obviously some kind of equation for figuring out for I,j the new I',j'. So let's put the array in a wrapper object, the object has a get(x,y) function and if it's flipped it will run the equation on the x,y So that's basically O(1). what do y'all think about that right there? some of you might not really like it

[@WizardOfArc]

To go counter clockwise would that just be swap columns first then transpose? (Just did some sketching and the answer is yes 😁)

[@nicadi2005]

8:50 Shouldn't the outer loop actually start from 1 instead of 0, to avoid needlessly processing the main diagonal as well?

[@SeanAlunni]

Inner*

[@eleanazeri8195]

Thank you so much for this video, it helped my team and I get unstuck in a programming project with the flip method!

[@gradientO]

_Make more of these videos!_

[@xle6ywek345]

Java: column row row column x = y - x y = y + x column row row Python: ...zip()?

[@likithr.n9692]

His explanation skill is amazing

[@Temulgeh]

oh, as a student i just assumed that an in place solution wouldn't be accepted and didn't even think about this i thought that the solution was about doing something more cache friendly because accessing this 2D array like that just sounds terrible for the cache, but i don't really see how that would even be possible

[@rdoetjes]

Als these sort of questions prove nothing. You’d use a library now. It doesn’t demonstrate insight and think out of the box. Just applied knowledge.

[@NeerajSharma-oz1mm]

Though I'm a big fan of your approach towards the solution, but I think in this case, below solution is better: void rotate(int a[5][5], int s){ for(int i = 0; i

[@MarvinOGarza]

What is the initial value of s?

[@nathamuni9435]

Why can't we use another for loop And rotate it three times more to get the optimal solution

[@danielmilyutin9914]

1 rotation in 2d is equivalent to 2 reflections. Diagonal and "y-axis" will do. Or do cycle shift over 4 quater triangles.

[@aquilazyy1125]

Yep, good old group theory comes to mind when I read the question. Although the triangular swap is probably more efficient (moving once instead of twice), I still prefer mirroring twice for the understandability.

[@NU6W]

Hey Nick, love your videos - thank you for making them. How do you do the transparency to put yourself on top of the video? Is it some Windows video editing tooling + a green screen?

[@AluohEdits]

It’s a green screen + green chroma keying in a video editing software; you can see his green screen in his previous video with the interview

[@NU6W]

@@AluohEdits Thanks for the info! I was more interested in how the green screen is being used in conjunction with the desktop / browser recording. I can easily imagine how you'd do it if they were recorded separately and stitched together later on, but I can't for the life of me figure out how to do a green-screen while recording the desktop like Nick has done.

[@AluohEdits]

​@@NU6W So with that, I am most likely sure it could be from OBS. I believe Nick streams with OBS, so I actually think you can record entire screen + webcam (depending how you place everything inside OBS). This includes the greenscreen as well. I found this video, maybe this can help? kzbin.info/www/bejne/pZ7FpHt8er-nh5Y

[@ghost_nut]

Pretty helpful! But holy fuck that nested for loop was complicated to understand

[@paulopontovaz]

I would just use [ i ][ j ] -> [ j ][ Math.abs(i - (N-1)) ]. Would be simpler, no? I might be missing something

[@aimachine2310]

I solved it in 1 hour. Wow. I can't believe it. I'm incoming 2nd year college. And I didn't watch the whole video. I paused it in 5:18. Wow. I'm excited for more.

[@aimachine2310]

But in in-efficient way 😂. Ok back to work to improve myself

[@manojrajasekar6035]

Dude, Great Explanation. Your New style of explanation is very good ! keep doing

[@narongsakyooyen9572]

Another approach with 2 loop // Rotate Image let a1 = [ [1,2,3], [4,5,6], [7,8,9]] let rotate_a1 = [[],[],[]] console.log(rotate_a1) a1.forEach((lv1_item, lv1_index) => { lv1_item.forEach((lv2_item, lv2_index) => { rotate_a1[lv2_index][2-lv1_index] = lv2_item; }) }) console.log(rotate_a1)

[@MistaT44]

dude, idk if someone's said it here, but your personality is uniquely amazing and entertaining :D + as always, great quality content

[@9291806697]

very cool solution ever seen for this problem. and now it's clear for me and can be easily rememberable when the actual situation comes. thanks dude.

[@chaitanyatate3242]

We can swap the rows horizontally first and then take transpose

[@tranbao2799]

If anyone want to try this in python: test = [ [1,2,3], [4,5,6], [7,8,9],] def rotate90(arr): n = len(arr) new = [] for k in range(n): new.append([]) for i in range(n,0,-1): new[k].append(arr[i-1][k]) return new print(rotate90(test))

[@SubhashKumar-do6ld]

The way you explain is awesome 👍❤️

[@arhabersham]

This guy sounds like the software developer version of “Entrepreneurs in Cars”

[@OptimisticForce]

lol

[@DanteEhome]

Oh you are hard swapping. I was thinking of putting each circle of element into an array and just move the last two digits to the front, and then map it back. I guess yours is faster?

[@mr_phamtastic]

this was awesome! the book solution didn't really help me understand this but this video did

[@prateeksaxena7808]

Thanks man really helpful. Never understood the solution online that iterate onle once.

[@sudhanwapande2040]

Bro you are awesome the way you explain things really awesome love from india 🇮🇳

[@t1910j]

I failed this question in my interview for front end developer. Thank you so much for the solution

[@JWentu]

Wouldn't it be possible to also make the swaps in place without using "temp"? X := X XOR Y Y := Y XOR X X := X XOR Y

[@bultvidxxxix9973]

Just assume, that the compiler knows that too. Your code should be readable by other programmers, don't assume the code is interpreted they way that you wrote it. If you need your code to run faster, you can benchmark and try out these kinds of micro optimizations, but most likely you'll find out, that it doesn't affect the runtime at all.

[@__-kd8oz]

@@bultvidxxxix9973 you just opened my eyes. XD

[@haha-eg8fj]

I think the interpreter/compiler will do this on the bytecode level so it doesn't really matter if you write it like this or more verbose.

[@BiscuitZombies]

There are two cycles nested. The middle numbers and the corner numbers.

[@assetaden6662]

Or you can just use built-in functions. Like after traversing the array just use for loop and for every nested array use: array[i].Reverse(); Hehe

[@brunosignoriwustro9460]

I don't get why you state the algorithm's time complexity is 2n instead of n^2

[@parthapratimghose173]

Lol no dude He meant the next loop which is the horizontal swap can be done using one loop in o of n but he did in on2 to make it cleaneer to understand that's what he meant not overall time complexity

[@brunosignoriwustro9460]

@@parthapratimghose173 ohh... got it, ty lol

[@calebsteinmetz9471]

I love how this question was on an exam in my Programming fundamentals 1 class in college XD (that was for freshmen).

[@rubenlech7256]

Congrats, your videos are getting better. I

[@skillfulfighter23]

Damn I thought you could just multiply the image matrix by the rotation matrix for that image

[@psychicks3463]

and look how its done in python import numpy as np a = np.arange(16).reshape(4,4) print(a,' ') f = [list(reversed(arr)) for arr in a.T] print(np.array(f))

[@ArjanvanVught]

Outer and inner loops counting to N .. that will take a while for large N. I am pretty sure this swap is CPU and time expensive

[@ajmalkhan2973]

Hi Nick, your videos are amazing.. quick question; could we not open the nested arrays and move each index by the length of the array. First example 1 goes to index 2(position 3) and so on then put that array back in to it's original nests?

[@mad_circuits]

Sorry, I‘m a bit late to the party. I like your video, so I gave it a like. But I want to add: I don‘t like your solution. Even in full scale environments like image manipulation applications or in scientific programs it is very uncommon to modify the actual input elements of the arrays in place. It is better style to leave the input untoched and build the entire output from scratch. This enables you to come up with a much cleaner and faster algorithm: Just walk through the matrix using two cascaded for-loops, outer one from yMax to 0, inner one from 0 to xMax. Build row-arrays in inner and col-arrays in outer loop and store and return the resulting matrix.

[@MdImrulHassan]

Interviewer: Transpose this matrix. Me: `transpose l` in Haskell. `zip(*l)` in Python 2.

[@__ash13__]

Interviewer: Ok good job, we'll call you back, good bye.

[@judgeomega]

wouldnt it be much better to instantiate your temp variable out of scope to save the overhead of creating a new variable each iteration? or do compilers optimize that away?

[@33alexramirez]

It's considered a best practice to declare your variables exactly in the scope you need them to avoid side effects, declaring and accessing single variables is also pretty inexpensive, so code readability wins here.

[@fzlagges5849]

This is what I came up with I am in std 9 so I am not familiar with the arrays syntax so please don't judge me Swap(array[i,j] , array[j,Math.Abs(i-limit)]) Limit being the length of row/column in the given example 2 if first=0 and three if first =1 And in the latter case Swap(array[i,j] , array[j,Math.Abs(i+1-limit)]) I think this saves space Please explain if the calculation of length starts from 1 or 0 in the case of arrays.

[@manishsharma2211]

1

[@Grassmpl]

You didn't go over the one step approach where we rotate over 4 entries simultaneously, an analog of swapping. We would loop over layers, the square boundaries starting from the outermost one. Eg. For 4x4 the layers numbers look like 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0

[@do_chill_regular]

Much better explanation than CTCI

[@svenangerer1840]

Great video. Are there other questions in a job interview which are more complex than that? I did this in the first semester of university...

[@sanguine4039]

Question: are the symmetric dimensions of the image specific to this problem, meaning that this how Amazon defined the problem, as always being n x n? It's a bit unclear to me, cus in real life, images have different X and Y dimensions.

[@minhazulislam4682]

Just tried it myself and I did it! Thanks man. You explain really nicely. btw, I use python(beginner u c).

[@freak4twenty]

answer = [[row[index] for index in range(3) for row in problem[::-1]][splice*3:splice*3+3] for splice in range(3)] before watching, code is in python where problem is the original list. interested in seeing your answer, I'm new to coding so be gentle on my code

[@freak4twenty]

so for larger arrays replace the 3s with len(problem) for non-square arrays ranges should be range(len(problem[0]))

[@jishnudesarkar]

Basically transpose the thing and reverse each row array