Blind 75 Must Do Leetcode Python 3 Solutions

Hashing to Solutions:

1. Two Sum
2. Longest Substring Without Repeating Characters
3. Longest Palindromic Substring
4. Container With Most Water
5. 3Sum
6. Remove Nth Node From End of List
7. Valid Parentheses
8. Merge Two Sorted Lists
9.  Merge k Sorted Lists
10. Search in Rotated Sorted Array
11. Combination Sum
12. Rotate Image
13. Group Anagrams
14. Maximum Subarray
15. Spiral Matrix
16. Jump Game
17. Merge Intervals
18. Insert Interval
19. Unique Paths
20. Climbing Stairs
21. Set Matrix Zeroes
22. Minimum Window Substring
23. Word Search
24. Decode Ways
25. Validate Binary Search Tree
26. Same Tree
27.  Binary Tree Level Order Traversal
28. Maximum Depth of Binary Tree
29. Construct Binary Tree from Preorder and Inorder Traversal
30. Best Time to Buy and Sell Stock
31. Binary Tree Maximum Path Sum
32. Valid Palindrome
33. Longest Consecutive Sequence
34. Clone Graph
35. Word Break
36. Linked List Cycle
37. Reorder List
38. Maximum Product Subarray
39. Find Minimum in Rotated Sorted Array
40. Reverse Bits
41. Number of 1 Bits
42. House Robber
43. Number of Islands
44. Reverse Linked List
45. Course Schedule
46. Implement Trie (Prefix Tree)
47. Design Add and Search Words Data Structure
48. Word Search II
49. House Robber II
50. Contains Duplicate
51. Invert Binary Tree
52. Kth Smallest Element in a BST
53.  Lowest Common Ancestor of a Binary Search Tree
54. Lowest Common Ancestor of a Binary Tree
55. Product of Array Except Self
56. Valid Anagram
57. Meeting Rooms
58. Meeting Rooms II
59. Graph Valid Tree
60. Missing Number
61. Alien Dictionary
62. Encode and Decode Strings
63. Find Median from Data Stream
64. Longest Increasing Subsequence
65. Coin Change
66. Number of Connected Components in an Undirected Graph
67. Counting Bits
68. Top K Frequent Elements
69. Sum of Two Integers
70. Pacific Atlantic Water Flow
71. Longest Repeating Character Replacement
72. Non-overlapping Intervals
73. Serialize and Deserialize BST
74. Subtree of Another Tree
75. Palindromic Substrings
76. Longest Common Subsequence

 1. Two Sum

This code looks through a list to find two different numbers that add up to a specific target number. It does this by using two loops. The first loop starts at the beginning of the list. For each number in the first loop, the second loop looks at the numbers that come after it in the list. If it finds two numbers that add up to the target, it gives back their positions in the list.

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for num_first in range(len(nums)): for num_second in range(num_first+1,len(nums)): if nums[num_first]+nums[num_second] == target: return [num_first,num_second]

Time Complexity: O(n^2)

This is because for each element in the list (and there are 'n' elements), we are potentially looking at every other element in the list to find a match (which in the worst case is 'n-1' other elements), resulting in 'n' times 'n-1' operations.

Space complexity: O(1)

This code only uses a fixed amount of extra space (for the indices), no matter how big the list gets.

 2. Longest Substring Without Repeating Characters

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last_idx = {} max_len = 0 # starting index of current # window to calculate max_len start_idx = 0 for i in range(0, len(s)): # Find the last index of str[i] # Update start_idx (starting index of current window) # as maximum of current value of start_idx and last # index plus 1 if s[i] in last_idx: start_idx = max(start_idx, last_idx[s[i]] + 1) # Update result if we get a larger window max_len = max(max_len, i-start_idx + 1) # Update last index of current char. last_idx[s[i]] = i return max_len

• Time Complexity: O(n + d) where n is the length of the input string and d is the number of characters in the input string alphabet. 
• Space Complexity: O(d)

Counting Valleys - Hackerrank Solution

 Check out the counting valleys question here: Hackerrank question

The picturization of the problem:

Suppose the input is: UDDDUDUU

Then, 

Answer: Valley level is 1. Because hiker stepped this way only.

To solve this problem:

Initially, assumed U = 1, D = -1 & altitude=0

Then, iterated till total steps-1. Whenever altitude(height) that is sea level is 0 & the last step is 'U" I have incremented the valley by 1 (because valley level is considered only when hiker's last step is 'U" & at the sea level).

When all the elements are traversed it returned the final valley's value that's our final result.

Solution:

def countingValleys(steps, path):

    # Write your code here

    

    altitude = 0

    valley = 0

    dict = {

        "U": 1,

        "D": -1

    }

    for eachstep in range(steps):

        altitude += dict[path[eachstep]] # calculating hiker's each step

        if altitude == 0 and path[eachstep] == "U":

            valley += 1

    return valley

Sales by Match -Hackerrank solution

Check out the question here - Sales by Match

def sockMerchant(n, ar):

    pairs = 0

    for element in set(ar):

        pairs += ar.count(element) // 2

    

    return pairs

if __name__ == '__main__':

    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    ar = list(map(int, input().rstrip().split()))

    result = sockMerchant(n, ar)

    fptr.write(str(result) + '\n')

    fptr.close()

How to show code on blogger / blogspot with a copy snippet button

To show copy code snippet button for any code. Do the following steps:

1. Go to HTML View of blog post's editor.
2. Paste the below lines inside HTML editor & replace the Your Actual Code with the desired code.

<textarea style="border-style: solid; border-width: 1px 1px 1px 20px; border-color: #4072a1; width: 100%; height: 321px; line-height: 16px; resize: none;" id="html1" readonly> Your Actual Code</textarea><div style="font-size:13px; font-family: comic sans ms; color: blue;"><button onclick="copyThis1()">Copy code snippet</button></div>

<script>

function copyThis1() {

  var copyText = document.getElementById("html1");

  copyText.select();

  copyText.setSelectionRange(0, 99999)

  document.execCommand("copy");

  alert("Code snippet copied to clipboard");

}

</script>

Turtle Race : Python Project for Beginners

Game Rules:

1. 5 turtles of unique colors compete against each other.

2. User gets a chance to guess which color turtle will win the race.

3. If the user's guess is right it says you've won otherwise you lose!

Few screenshots of the game:

CODE:

from turtle import Turtle,Screen, penup, xcor import turtle import random colors=['yellow','blue','red','pink','orange'] all_turtles=[] y_positions=[-60,-30,0,30,60] screen=Screen() screen.setup(width=500,height=300) user_input=screen.textinput('Turtle Race','Make a bet. Which color will win win the race?').lower() #Background Customizations screen.bgcolor("grey") Tim=Turtle() Tim.color('green') Tim.penup() Tim.write('Turtle Race', move=False, align="left", font=("Arial", 25, "normal")) Tim.goto(x=190,y=100) Tim.color('Black') Tim.write('END', move=False, align="left", font=("Arial", 10, "normal")) Tim.goto(x=220,y=150) Tim.right(90) Tim.pendown() Tim.color('Black') #Background Customization Ends Tim.forward(300) for turtle_index in range(5): next_turtle=Turtle(shape='turtle') next_turtle.color(colors[turtle_index]) next_turtle.penup() next_turtle.goto(x=-230,y=y_positions[turtle_index]) all_turtles.append(next_turtle) if user_input: is_race_on=True while is_race_on: for move_turtle in all_turtles: if move_turtle.xcor() > 200: is_race_on=False winning_color=move_turtle.pencolor() if user_input==winning_color: print(f" You've won! The {winning_color} turtle wins the race.") else: print(f" You lose! The {winning_color} turtle wins the race.") move_turtle.forward(random.randint(0,10)) move_turtle.speed(0) screen.exitonclick()

Doodle it: Imagine, Draw, Erase and Repeat - Python Project for Beginners

 Doodle it: Imagine, Draw, Erase and Repeat

In order to create this game first step is to know a way of being able to listen to things the user does, like when a user taps a specific key on the keyboard. And the code that allows us to do this are called  Event Listeners.

Go to python documentation > listen method()

It has a whole bunch of section-on-screen events, including listening to key presses or listening to a click or other things that you can listen to. So the important thing is this listen method.

This allows turtle screen to start listening and waiting for the events that the user might trigger, like tapping on a key.

So for this first thing, we'll be going to do is we'll import the turtle class and the screen class from the turtle module. And then, we'll use them to create our Ted the turtle, and also create a screen object.

from turtle import Turtle,Screen

ted=Turtle()

screen=Screen()

This is basically going to control the window when we run our code.

Now in order to start listening for events, we have to get hold of the screen object and then tell it to start listening.

from turtle import Turtle,Screen

ted=Turtle()

screen=Screen()

screen.listen()

And once it starts listening, we have to bind a function that will be triggered when a particular key is pressed on the keyboard. Now, in order to bind a keystroke to an event in our code, we have to use an event listener.

So the one that we're going to be using is this onkey method. And you can see it expects a function with no arguments and also a key, like the 'a' key on your keyboard or a key symbol, so the space or up or down.

So I'm going to say screen.onkey and then I have to bind some sort of function to this method.

So let's create a function named ted_move_right and all that this function is going to do is it's going to get Ted to go forward by 10 paces. 

from turtle import Turtle,Screen

ted=Turtle()

screen=Screen()

def ted_move_right():

    ted.forward(10)

screen.listen()

screen.onkey() 

Now, coming back to our onkey method, we are going to say when the 'w', is pressed, then trigger the function move_forward.

def move_forward():

    ted.forward(10)

screen.listen()

screen.onkey(key='w',fun=move_forward)

Next, added the concerning triggered function move_backward to move backward when the 's' key is pressed.

from turtle import Turtle,Screen

ted=Turtle()

screen=Screen()

def move_forward():

    ted.forward(10)

def move_backward():

    ted.backward(10)

    

screen.listen()

screen.onkey(key='w',fun=move_forward)

screen.onkey(key='s',fun=move_backward)

screen.exitonclick()

Such that, functions to move counter-clockwise(left), clockwise(right) and to clear screen(reset screen) are written and binded them with the following keys 'a','d', & 'c' respectively.

from turtle import Turtle,Screen

ted=Turtle()

screen=Screen()

def move_forward():

    ted.forward(10)

def move_backward():

    ted.backward(10)

    

def move_left():

    new_heading= ted.heading()+10

    ted.setheading(new_heading)

def move_right():

    new_heading= ted.heading()-10

    ted.setheading(new_heading)

def clear_screen():

    ted.clear()

    ted.penup()

    ted.home()

    ted.pendown()

screen.listen()

screen.onkey(key='w',fun=move_forward)

screen.onkey(key='s',fun=move_backward)

screen.onkey(key='a',fun=move_left)

screen.onkey(key='d',fun=move_right)

screen.onkey(key='c',fun=clear_screen)

screen.exitonclick()

And now what I'm going to try is when I hit the 'w' key on the keyboard, you should see my turtle move forwards by 10 paces each time. And, when 's' key is pressed it moves backward. So we're now controlling our turtle using a keystroke. That's pretty much in Doodle it: just imagine,draw & repeat.

Full key list for python's turtle- screen events ( Event Listeners )

Screen events 

turtle.onkey(fun=function_name, key='Backspace')

turtle.onkeyrelease(fun=function_name, key='Left')

Parameters

• fun – a function with no arguments or None

• key – a string: key (e.g. “a”) or key-symbol (e.g. “space”)

.keysym	.keycode	.keysym_num	Key

Alt_L	64	65513	The left-hand alt key
Alt_R	113	65514	The right-hand alt key
BackSpace	22	65288	backspace

Caps_Lock	66	65549	CapsLock
Control_L	37	65507	The left-hand control key
Control_R	109	65508	The right-hand control key
Delete	107	65535	Delete
Down	104	65364	↓
End	103	65367	end
Escape	9	65307	esc

F1	67	65470	Function key F1
F2	68	65471	Function key F2
Fi	66+i	65469+i	Function key Fi
F12	96	65481	Function key F12
Home	97	65360	home
Insert	106	65379	insert ( ins)
Left	100	65361	←

K0	90	65438	0 on the keypad
1	87	65436	1 on the keypad
2	88	65433	2 on the keypad
3	89	65435	3 on the keypad
4	83	65430	4 on the keypad
5	84	65437	5 on the keypad
6	85	65432	6 on the keypad
7	79	65429	7 on the keypad
8	80	65431	8 on the keypad
9	81	65434	9 on the keypad
+	86	65451	+ on the keypad

.	91	65439	Decimal (.) on the keypad
Delete	91	65439	delete on the keypad
/	112	65455	/ on the keypad
Down	88	65433	↓ on the keypad

Enter	108	65421	enter on the keypad
Home	79	65429	home on the keypad

Left	83	65430	← on the keypad
*	63	65450	× on the keypad

Prior	81	65434	PageUp on the keypad
Right	85	65432	→ on the keypad
-	82	65453	- on the keypad
Up	80	65431	↑ on the keypad
Next	105	65366	PageDown / pg dn
Num_Lock	77	65407	NumLock
Pause	110	65299	pause
Print	111	65377	PrintScrn / prt sc

Right	102	65363	→
Scroll_Lock	78	65300	ScrollLock
Shift_L	50	65505	The left-hand shift key
Shift_R	62	65506	The right-hand shift key
Tab	23	65289	The tab key

Turtle's random walk - Python

How to let turtle making random movements in the East, North, South, or West in Python?

Rules for Python's Turtle:

1. Each time it moves in a random direction.

2. In each direction it chooses a random color 

3. Each time line's thickness increases

4. Each time it covers the same distance

5. Walks on screen in its fastest mode

Solution:

from turtle import Turtle import random from turtle import Turtle,Screen colours = ["orange","CornflowerBlue", "DarkOrchid", "IndianRed", "DeepSkyBlue", "LightSeaGreen", "wheat", "SlateGray", "SeaGreen"] to_angle=[0,90,180,270] #0 - east, 90 - north, 180 - west & 270 - south tim=Turtle() tim.speed(0) #set to fastest speed mode thickness=0.1 #set to initial thickness 0.1 screen=Screen() screen.setup(420, 420) #non-scrollable screensize for i in range(400): tim.pen(pencolor=random.choice(colours)) #assigns random color tim.pensize(width=thickness) #line;s thickness assigned tim.setheading(random.choice(to_angle)) # Angle/direction(E,N,W & S) tim.forward(20) thickness+=0.07 #line's thickness incremented on each step's end screen.exitonclick()

Draw different shapes like triangle, square, pentagon, hexagon in python using turtle

 How to draw a triangle, square, pentagon, hexagon, heptagon, octagon, nonagon, and decagon in one go using turtle class of python?

Code:

from turtle import Turtle,Screen

import random

# to take the turtle up on screen so that all the shapes can get enough space

tim=Turtle()

tim.penup()

tim.left(90)

tim.forward(100)

tim.left(90)

tim.forward(150)

tim.right(90)

tim.forward(50)

tim.right(90)

tim.pendown()

# Now turtle is at the right place

# Main code begins now:

colours = ["orange","CornflowerBlue", "DarkOrchid", "IndianRed", "DeepSkyBlue", 

"LightSeaGreen", "wheat", "SlateGray", "SeaGreen"]

def draw_shape(num_of_sides,color):

    tim.color(color)

    angle=360/num_of_sides #will find out the angle according to the given shape

    for _ in range(num_of_sides):

        

        tim.forward(100)

        tim.right(angle)

for shape_of_side_n in range(3,11):

    color=random.choice(colours) #Selects the color randomly for each shape

    draw_shape(shape_of_side_n,color) #will draw shapes from triangle to decagon

screen=Screen()

screen.exitonclick()

How to draw a dashed line in python?

 

In python, to draw a dashed line on a screen, first, turtle module's Turtle class is imported to the program. The turtle is an extensive module that provides turtle graphics primitives, in both object-oriented and procedure-oriented ways. Because it uses tkinter for the underlying graphics, it needs a version of Python installed with Tk support.

It's part of core python libraries so, turtle comes by default with basic python. Just need to import and use.

After importing the turtle, we use the penup and pendown to draw a dashed line. Penup simply means not drawing & Pendown is drawing a line. Like in the code below turtle module's penup & pendown are used to draw a black dashed line.

from turtle import Turtle,Screen #turtle is imported

timmy_the_turtle=Turtle()

timmy_the_turtle.shape('classic')

timmy_the_turtle.color('black')

for i in range(20):

    

    # penup or pu means pick pen up, 

    # so you can move turtle 

      without leaving tracks. 

    # pendown or pd means pick pen down, 

    # so you can move the turtle 

      and leave tracks.

    

    timmy_the_turtle.forward(10)

    # picking up pen

    timmy_the_turtle.penup()

    timmy_the_turtle.forward(10)

    # picking pen down to draw

    timmy_the_turtle.pendown()

    

screen=Screen()

#Allows to exit when user clicks on screen

screen.exitonclick()

Solution to Techgig 30 Days Python Challenge - Day 7 (HARD)

 

Count special numbers between boundaries (100 Marks)

For this challenge, you are given a range and you need to find how many prime numbers lying between the given range.

Input Format

For this challenge, you need to take two integers on separate lines. These numbers defines the range. 

Constraints

1 < = ( a , b ) < = 100000

Output Format

output will be the single number which tells how many prime numbers are there between given range. 

Sample TestCase 1

Input

1

20

Output

8

Explanation

There are 8 prime numbers which lies in the given range.
They are 2, 3, 5, 7, 11, 13, 17, 19

Time Limit(X):

1.00 sec(s) for each input.

Memory Limit:

512 MB

Source Limit:

100 KB

Allowed Languages:

C, C++, C++11, C++14, C#, Java, Java 8, PHP, PHP 7, Python, Python 3, Perl, Ruby, Node Js, Scala, Clojure, Haskell, Lua, Erlang, Swift, VBnet, Js, Objc, Pascal, Go, F#, D, Groovy, Tcl, Ocaml, Smalltalk, Cobol, Racket, Bash, GNU Octave, Rust, Common LISP, R, Julia, Fortran, Ada, Prolog, Icon, Elixir, CoffeeScript, Brainfuck, Pypy, Lolcode, Nim, Picolisp, Pike

SOLUTION DAY-07: (100 Marks)

def main():

        num1=int(input("Enter num 1:"))

        num2=int(input("Enter num2: "))

        c=0

        for num in range(num1,num2+1):

                if num>1:

                        for i in range(2,num):

                                if num%i==0:

                                        break

                        else:

                                c+=1

                

        print(c)

main()