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)