Search a 2D Matrix Python Leetcode

 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

Main thing to note in this problem : row = pivot // cols and col = pivot % cols 

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or len(matrix) == 0:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        
        if rows == 1 and cols ==1:
            if target == matrix[rows-1][cols-1]:
                return True
            else:
                return False
       
        left = 0
        right = rows * cols -1
        
        while left <= right:
            pivot = left + (right-left) // 2
            
            if target == matrix[pivot // cols][pivot % cols]:
                return True
            elif target > matrix[pivot // cols][pivot % cols]:
                    left = pivot + 1
            else:
                right = pivot - 1
        return False

Time Complexity : O(logn(mn))

Space Complexity : O(1)

Search in Rotated Sorted Array - Python Leetcode

 You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        if len(nums) == 1 and target == nums[0]:
            return 0
        
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = left + (right-left) // 2
            
            if nums[mid] == target:
                return mid
            
            elif nums[mid] >= nums[left]:
                if target < nums[mid] and target >= nums[left]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if target > nums[mid] and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1
        

Complexity Analysis
Time complexity: $\mathcal{O}(\log{N})$.
Space complexity: $\mathcal{O}(1)$.

 

Find Minimum in Rotated Sorted Array II - Leetcode Python

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

class Solution:

    def findMin(self, nums: List[int]) -> int:

        if not nums:

            return 

        if len(nums) == 1:

            return nums[0]

        low = 0

        high = len(nums)-1

        

        while low < high:

            mid = low + (high-low) // 2

            

            if nums[mid] < nums[high]:

                high = mid

            elif nums[mid] > nums[high]:

                low = mid + 1

            else:

                high-=1

        return nums[low]

Find Minimum in Rotated Sorted Array - Python Leetcode

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if not nums:
            return 
        # If last element is greater than first element then no rotation happened
        if nums[len(nums)-1] >= nums[0]:
            return nums[0]
        
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = int(left + (right-left)/2)
            
            # if mid > mid +1 there is a flunctuation in the increasing order
            if nums[mid] > nums[mid+1]:
                return nums[mid+1]
            
            #if mid-1 > mid there is a fluctuation happened in increasing order
            if nums[mid-1] > nums[mid]:
                return nums[mid]
            
            if nums[mid] > nums[0]:
                left = mid+1
            else:
                right = mid-1
                
        
Time Complexity : O(logn)

Space Complexity : O(1)

Sort Colors - Python Leetcode

 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
• Could you come up with a one-pass algorithm using only constant space?

class Solution:

    def sortColors(self,nums: List[int]) -> None:

        """ 

        Dutch National Flag Problem

        """

        # For all idx nums[idx < p0] == 0 and idx < p0

        # For all idx idx > p2 : nums[idx > p2] == 2

        # curr is pointing current element

        

        if not nums:

            return 

        curr = p0 = 0

        p2 = len(nums) -1

        

        while curr <= p2:

            if nums[curr] == 0:

                nums[p0],nums[curr] = nums[curr],nums[p0]

                curr = curr+1

                p0 += 1 

            elif nums[curr] == 2:

                nums[curr],nums[p2] = nums[p2],nums[curr]

                p2 -= 1

            else:

                curr+=1

                

Install Node.js and npm using Homebrew on OS X and macOS

 

Install Node.js and npm with Homebrew

First, install Homebrew.

/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Then run brew update to make sure Homebrew is up to date.

brew update

run brew doctor to make sure your system is ready to brew. Run the command below and follow any recommendations from brew doctor.

brew doctor

Next, add Homebrew’s location to your $PATH in your .bash_profile or .zshrc file.

export PATH="/usr/local/bin:$PATH"

Next, install Node (npm will be installed with Node):

brew install node

To test out your Node and npm install, try installing Grunt (you might be asked to run with sudo):

npm install -g grunt-cli

Now you’ve installed Node.js, npm, and Grunt.

How to Uninstall Homebrew on Mac

 

• Open the Terminal app

• Type ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"