Skip to main content

Rotate Image - Leetcode 48 - Python

 


Rotate Image



You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.


class Solution:

    def rotate(self, m: List[List[int]]) -> None:

        

        """

        Do not return anything, modify matrix in-place instead.

        """

        

        l, r = 0, len(m)-1

        

        while l < r :

            for i in range(r-l): 

                t, b = l, r

                

                # tl in temp

                temp = m[t][l+i]

                

                # bl -> tl

                m[t][l+i] = m[b-i][l]

                

                # br -> bl

                m[b-i][l] = m[b][r-i]

                

                #  tr -> br

                m[b][r-i] = m[t+i][r]

                

                # temp -> tr

                m[t+i][r] = temp

                

            r -= 1

            l += 1



Explaintion :



Labels:

Comments

Post a Comment

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :
Post a Comment
Read more

Leetcode 338. Counting Bits. Python (Bubble Sort)

Given an integer  n , return  an array  ans  of length  n + 1  such that for each  i   ( 0 <= i <= n ) ,  ans[i]  is the  number of  1 's  in the binary representation of  i .   Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101   Constraints: 0 <= n <= 10 5   Follow up: It is very easy to come up with a solution with a runtime of  O(n log n) . Can you do it in linear time  O(n)  and possibly in a single pass? Can you do it without using any built-in function (i.e., like  __builtin_popcount  in C++)?   Solution : class Solution:     def countBits(self, n: int) -> List[int]:         dp = [0] * (n+1)         c = 1        ...
Post a Comment
Read more

Leetcode 347. Top K Frequent Elements. Python (Bubble Sort)

Top K Frequent Elements Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1]   Constraints: 1 <= nums.length <= 10 5 -10 4  <= nums[i] <= 10 4 k  is in the range  [1, the number of unique elements in the array] . It is  guaranteed  that the answer is  unique .   Follow up:  Your algorithm's time complexity must be better than  O(n log n) , where n is the array's size. Solution : class Solution:     def topKFrequent(self, n: List[int], k: int) -> List[int]:                  # [1,1,1,2,2,3] &  k = 2                  f = [[] for i in range(len(n) + 1)]         # f = [...
Post a Comment
Read more