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!
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.
> 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.
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.
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)
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.
@@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 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.)
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]
@@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.
@@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
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 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]
@@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.
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.
@@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).
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)
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
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!
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; } } }
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 ] )
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.
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.
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
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.
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.
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
Ever heard of matrix multiplication? Matrix multiplied by 2/pi is a rotate 90 degrees. And there are some incredible efficient array multiplication libraries.
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
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
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.
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.
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..
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?
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.
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]
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.
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
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.
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.
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
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
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
Why wouldn’t you use a double nested for loops with the first one reading the column and the second one reading the lines starting from the bottom ? That should work with way less complexity.
@@ITR This, in Javascript, for instance, solves the issue only by looping on the matrix using two nested For and 4 indexes. It works with any square size. Did I miss something or is it really a better solution? ----- const input = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; let result = []; const len = input.length; //square size for (let i = 0, y = 0; i < len; i++, y++) { result[y] = []; for (let j = len - 1, z = 0; j >= 0; j--, z++) { result[y][z] = input[j][i]; } }
@@Ceyesse One of the constraints on the task is that you're not allowed to copy it over to a separate array. Also, you don't need to have 4 variables to loop, you can just do result[-j][i] = input[i][j];
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
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.
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?
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
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]
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
not exactly that but something like identity matrix(which in turn is obtained by putting theta = 90⁰ in the sin and cosine expansion of e^i∅ (ig)), but as elegant as it may seem Matrix Multiplication takes O(N³) time And time is costly; that online judge bitch throws TLE on the face right off the fucking screen
I'm a beginner about this time complexity, but wouldn't it be better if you use 2 nested loops? Or is 2 loops better in time complexity than 2 nested loops?
it's not about whether 2 nested for loops were used compared to 2 single loops. It's about the type of operations in the loops along with how many times each element undergoes that certain operation. I also made this mistake when I first learned time complexity and thought that whenever I see a nested for loop, I would think it's O(n^2).
What if we use a.T for transposing the matrix in python?...and then mirror it....will the solution be acceptable...also the whole problem can be done by using open cv functions.....will that be acceptable? In respect of time complexity and all.
Ok a bit confused here. Won't your transpose code just undo itself? Say you go through loop you at 0,1 so your code swap 0,1 with 1,0. Then won't the code reach 1,0 later and swap them back giving you the same matrix you started with?
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)
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
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 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.
@@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? th-cam.com/video/ombsHFEZtQ4/w-d-xo.html
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))
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?
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
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.
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.
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!
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.
> 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.
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.
First method is significantly faster, it's a space/time trade off.
A better solution would involve a row wise algorithm to take advantage of CPU caching.
transpose, then mirror.
Witam pana z Polski
Every rotation is the product of two reflections.
but there is a faster way, you can do it with a single operation per element
@@fritt_wastaken care to explain
@@fritt_wastaken It is still quadratic time so it doesn't matter.
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)
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.
Mind dropping a link to the other approach?
@@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.
That was my idea also. Should be less vsriable accesses. And also less readable and understandable
I had that Idea but could not code it or think of an efficient way to do it :(
@@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.)
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]
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;
That can fail due to arithmetic overflow. Try using binary exclusive OR instead, i.e.
x = x ^ y;
y = y ^ x;
x = x ^ y;
@@stevetodd7383 how does that work
@@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.
@@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
Use : y = (x+y) - (x=y) ; isn't it cool 😅
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
And this is why I dislike python. Too much abstraction
JoeCamRoberon You donˋt need to use this method though?
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.
@@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]
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)
I am also thinking about it
Since it is 2D array, 2 for loops are for running to every elements once.
@@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.
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.
@@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).
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)
Tetris programmers: “I’ve been waiting for this for my entire life!”
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
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!
I find this explanation more intuitive than the one given in cracking the coding interview
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;
}
}
}
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 ] )
8:21 - you swaping diagonal;
10:58 - "j < (N/2)" DO NOT calculate in conditions, at least use "N >> 1"
Yeah he should have j=i+1
I would do it with a fourway swap. It's a little more complex, but I just love the symmetri of it :)
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.
These videos are A+, love the editing.
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.
Yes correct. But how will you implement it.
8:50 Shouldn't the outer loop actually start from 1 instead of 0, to avoid needlessly processing the main diagonal as well?
Inner*
look's like youtube algorithm love these thumbnails ++
Congrats on 1 mill vews
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!
The solution seems wrong. The swapping loops, in the beginning, are swapping the elements twice. You could "int j = i + 1" to correct it.
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
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.
I so prefer this solution as opposed to doing swaps on 4 elements going from outter square to inner. Great video!
This way is easier but outer to inner is twice as fast
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 👍
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.
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
Pretty sure this exact question was on one of my exams for my data structures test lol
To go counter clockwise would that just be swap columns first then transpose? (Just did some sketching and the answer is yes 😁)
Ever heard of matrix multiplication? Matrix multiplied by 2/pi is a rotate 90 degrees. And there are some incredible efficient array multiplication libraries.
Your explanation skills have improved a lot. Much better than leetcode series
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
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
But the time complexity is O(n^2). Is there any better solution available?
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.
@@LeandroSilva-im2bs Thanks
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.
NxM is actually the smallest possible runtime complexity for the problem, even the new matrix solution has NxM time complexity.
@@33alexramirez where is the value for M coming from?
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..
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?
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.
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]
1 rotation in 2d is equivalent to 2 reflections. Diagonal and "y-axis" will do.
Or do cycle shift over 4 quater triangles.
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.
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
We can swap the rows horizontally first and then take transpose
Fortunately I’ve already done this multiple times when visualising things like bifurcation maps and Mandelbrot sets
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.
Yes that's what I suggest.
Why can't we use another for loop
And rotate it three times more to get the optimal solution
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.
best approach i’ve seen yet, i can easily write and explain a solution intuitively now. thank you!
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
Oh man, most of the exercises about 2d arrays are so difficult to solve, well at least for me...
It takes practice bro
OMFG, I had to solve the exact same algorithm in my bootcamp on the first exam after just 1 month !!!
Which bootcamp are you a part of?
pyroghost11 what bootcamp
@@brooksgunn5235 It was last year, one in Budapest called Greenfox Academy, as I'm Hungarian.
I made a lil Tetris game and to rotate the pieces I just wrote a function that reads the image from different perspectives
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
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
What is the initial value of s?
Why wouldn’t you use a double nested for loops with the first one reading the column and the second one reading the lines starting from the bottom ?
That should work with way less complexity.
Can you elaborate what you mean?
@@ITR This, in Javascript, for instance, solves the issue only by looping on the matrix using two nested For and 4 indexes. It works with any square size. Did I miss something or is it really a better solution?
-----
const input = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
let result = [];
const len = input.length; //square size
for (let i = 0, y = 0; i < len; i++, y++) {
result[y] = [];
for (let j = len - 1, z = 0; j >= 0; j--, z++) {
result[y][z] = input[j][i];
}
}
@@Ceyesse One of the constraints on the task is that you're not allowed to copy it over to a separate array. Also, you don't need to have 4 variables to loop, you can just do result[-j][i] = input[i][j];
@@ITR I missed this constraint, my bad. Good work.
I don't get why you state the algorithm's time complexity is 2n instead of n^2
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
@@parthapratimghose173 ohh... got it, ty lol
How soon did you realize your links are broken ?
they are fine . what the hell is wrong with you?
@@nareshg7292 😐
@@nareshg7292 it isnt working tho? You sure about that mate?
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.
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?
Isn't the time complexity O(2n^2)
When you say O(whatever), it means that your runtime is (eventually) _proportional_ to whatever. That means that O(2n^2) is the same as O(n^2)
Group theory baby!!!! You could also do vertical mirror followed by transpose.
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
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]
The point is: why waste time changing the matrix context when we can just iterate it with the shape we want?
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
Can’t you just multiply each coordinate by e^i theta when treating them as complex numbers?
not exactly that
but something like identity matrix(which in turn is obtained by putting theta = 90⁰ in the sin and cosine expansion of e^i∅ (ig)),
but as elegant as it may seem Matrix Multiplication takes O(N³) time
And time is costly; that online judge bitch throws TLE on the face right off the fucking screen
I'm a beginner about this time complexity, but wouldn't it be better if you use 2 nested loops? Or is 2 loops better in time complexity than 2 nested loops?
it's not about whether 2 nested for loops were used compared to 2 single loops. It's about the type of operations in the loops along with how many times each element undergoes that certain operation. I also made this mistake when I first learned time complexity and thought that whenever I see a nested for loop, I would think it's O(n^2).
How is this n complexity? If it involves two for loops i guess then the complexity is n^2 right? Am i missing anything?
Why does the matrix stay as it is if you initialize j in the inner for loop to 0 instead of 1 when transposing?
Tried tracing it and didn't see why..
What if we use a.T for transposing the matrix in python?...and then mirror it....will the solution be acceptable...also the whole problem can be done by using open cv functions.....will that be acceptable?
In respect of time complexity and all.
I believe you're not allowed to use external modules
This guy sounds like the software developer version of “Entrepreneurs in Cars”
lol
Ok a bit confused here. Won't your transpose code just undo itself? Say you go through loop you at 0,1 so your code swap 0,1 with 1,0. Then won't the code reach 1,0 later and swap them back giving you the same matrix you started with?
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)
I would just use [ i ][ j ] -> [ j ][ Math.abs(i - (N-1)) ]. Would be simpler, no? I might be missing something
_Make more of these videos!_
The way you explain is awesome 👍❤️
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
The time complexity should be N^2 as j loop is in i loop(nested) why did you say the time complexity of the code is N can you explain please
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?
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
@@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.
@@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?
th-cam.com/video/ombsHFEZtQ4/w-d-xo.html
Thank you so much for this video, it helped my team and I get unstuck in a programming project with the flip method!
Hi, can someone explain why it’s only O(2n) for time complexity and not O(n^2)?
looks like each row is from greatest to least after transpose, couldn't we sort each row instead?
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
His explanation skill is amazing
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))
Dude, Great Explanation. Your New style of explanation is very good ! keep doing
There are two cycles nested. The middle numbers and the corner numbers.
the metod or function swap ho it made? it still needs to create 1 variable to swap between 2 integers.
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?
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...
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
so for larger arrays replace the 3s with len(problem)
for non-square arrays ranges should be range(len(problem[0]))
How did you arrive at that transpose/mirror idea? I've seen several solutions to this question and this is by far the most unusual.
Its a linear algebra concept
Bro you are awesome the way you explain things really awesome love from india 🇮🇳
Hi Nick, what software are you using as the blackboard?
What are the time and space complexity?
what is the temp variable for?
and thanks for the video!
Are these not nested loops though? Or is that not valid because the nested loop only loops through half of N?
Thanks man really helpful. Never understood the solution online that iterate onle once.
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
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.
@@bultvidxxxix9973 you just opened my eyes. XD
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.
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
just outsource the function to MATLAB
rot90(matrix,-1) or fliplr(matrix')
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.
1