TECHYIELD

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)"

Installing Homebrew on a Mac

Installation Steps

Open the Terminal app.
Type ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

It will ask for password provide your mac password.

After it run and executed few scripts you should see

==> Installation successful!

satyagokavarapu@Satyanarayanas-MacBook-Pro ~ % ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Warning: The Ruby Homebrew installer is now deprecated and has been rewritten in

Bash. Please migrate to the following command:

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)"

Password:

==> This script will install:

/usr/local/bin/brew

/usr/local/share/doc/homebrew

/usr/local/share/man/man1/brew.1

/usr/local/share/zsh/site-functions/_brew

/usr/local/etc/bash_completion.d/brew

/usr/local/Homebrew

Press RETURN to continue or any other key to abort

==> Downloading and installing Homebrew...

remote: Enumerating objects: 192, done.

remote: Counting objects: 100% (192/192), done.

remote: Compressing objects: 100% (15/15), done.

remote: Total 266 (delta 184), reused 181 (delta 177), pack-reused 74

Receiving objects: 100% (266/266), 80.68 KiB | 519.00 KiB/s, done.

Resolving deltas: 100% (193/193), completed with 55 local objects.

From https://github.com/Homebrew/brew

* [new branch] issyl0-patch-1 -> origin/issyl0-patch-1

9bbd866fc..f260b6e7b master -> origin/master

* [new branch] tapioca-update -> origin/tapioca-update

* [new tag] 2.4.15 -> 2.4.15

* [new tag] 2.4.16 -> 2.4.16

HEAD is now at f260b6e7b Merge pull request #8328 from reitermarkus/desc-cop

Updated 3 taps (homebrew/cask-versions, homebrew/core and homebrew/cask).

==> New Formulae

periscope sponge

==> Updated Formulae

act checkstyle editorconfig ghz-web helm libphonenumber mutt pdfcpu scrypt vim

anime-downloader code-server enchant gitleaks helmfile librealsense nasm pgformatter seal wtf

babel conan eslint gleam hexedit lmod nativefier pmd sqlite-utils xmrig

ballerina dartsim exploitdb gnupg htop logtalk navi pnpm step xxh

benthos deno fastlane gomplate ipython lsd netlify-cli ponyc swiftformat zbar

bundletool diffoscope feh google-java-format ispc mame nuget pulumi talisman

cadence duckdb folly gravity jfrog-cli meilisearch owfs qrencode trafficserver

cartridge-cli dvc gatsby-cli harfbuzz kustomize mikutter packer rebar3 uptimed

cdktf dxpy ghz hcloud liblouis mockolo patchelf rom-tools v8

==> New Casks

aleph-one flying-carpet nocturn pb toolreleases

==> Updated Casks

aerial cookie id3-editor microsoft-edge quail tg-pro

alt-tab datadog-agent ivideonclient missive redisinsight thunderbird

anki dbeaver-community jabref nextcloud ringcentral tuxera-ntfs

app-cleaner decrediton jamovi nrlquaker-winbox runjs visual-studio-code-insiders

aquaskk dropbox-beta jellyfin obsidian sabnzbd voov-meeting

beekeeper-studio elpass kafka-tool ocenaudio screen webcatalog

blender epichrome keka-beta oolite segger-embedded-studio-for-arm webtorrent

blitz exodus keysmith pagico sensei whale

brave-browser-dev extraterm kubernetic pastebot signal-beta whatsapp

busycal feishu lark pcoipclient silentknight wormhole

busycontacts fsnotes lockrattler propresenter softorino-youtube-converter yojimbo

c0re100-qbittorrent funter loom prowritingaid stats zappy

cacher grids lrtimelapse proxyman superproductivity zotero

chromium hstracker marathon publish-or-perish swiftformat-for-xcode

clipgrab icollections metasploit qiyimedia telegram

==> Deleted Casks

alephone sound-blaster-command

==> Installation successful!

How to Update Homebrew on Mac

Open terminal and type brew update command.

satyagokavarapu@Satyanarayanas-MacBook-Pro ~ % #brew update