My Complete solutions to the Blind 75 problems

All my solutions are written in Python3 & Golang. This discussion will be updated gradually as I progress through the list.
The complete list of all Blind 75 problems on LeetCode.

• Two Sum

  • Time Complexity: O(n)

  • Space Complexity: O(n)

    #Python3
    class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    	table = {}
    
    	for i, elem in enumerate(nums):
    		diff = target-elem
    		if elem in table:
    			return [table[elem], i]
    		else:
    			table[diff] = i
    

    //Go
    func twoSum(nums []int, target int) []int {
    	table := make(map[int]int)
    
    	for i, elem := range nums {
    		if idx, ok := table[elem]; ok {
    			return []int{idx, i}
    		} else {
    			table[target-elem] = i
    		}
    	}
    	return []int{}
    }

• Longest Substring Without Repeating Characters
  • Time Complexity: O(n)
  • Space Complexity: O(n)

    #Python3
    class Solution:
    	def lengthOfLongestSubstring(self, s: str) -> int:
    		p2, p1 = 0, 0
    		maxi_len = 0
    		seen = {}
    
    		while p2 < len(s):
    			if s[p2] in seen and seen[s[p2]] == True:
    				maxi_len = max(maxi_len, p2-p1)
    				while p1 < p2 and s[p1] != s[p2]:
    					seen[s[p1]] = False
    					p1+=1
    				p1+=1
    			else:
    				seen[s[p2]] = True
    			p2+=1
    
    		return max(maxi_len, p2-p1)

    //Go
    func lengthOfLongestSubstring(s string) int {
    	seen := make(map[byte]bool)
    	maxi_len := 0
    	p2, p1 := 0,0
    
    	for p2 < len(s) {
    		if val, ok := seen[s[p2]]; ok && val == true {
    			maxi_len = max(maxi_len, p2 - p1)
    			for p1 < p2 && s[p1] != s[p2]{
    				seen[s[p1]] = false
    				p1++
    			}
    				p1++
    		} else {
    			seen[s[p2]] = true
    		}
    		p2++
    	}
    	return max(maxi_len, p2 - p1)
    }

• Longest Palindromic Substring 🔂
  • Time Complexity: O(n²)
  • Space Complexity: O(1)

    #Python3
    class Solution:
    	def longestPalindrome(self, s: str) -> str:
    		longest_palindrome = s[0]
    		maxi_len = 1
    		n = len(s)
    
    		#Even length palindromes
    		for i in range(0, n-1):
    			j = 0
    			while i-j >= 0 and i+j+1 < n and s[i-j] == s[i+j+1]:
    				if 2*(j+1) > maxi_len:
    					longest_palindrome = s[i-j:i+j+2]
    					maxi_len = 2*(j+1)
    				j+=1
    
    
    		#Odd length palindromes
    		for i in range(0, n-1): #Center idx
    			j = 1
    			while i-j >= 0 and i+j < n and s[i-j] == s[i+j]: #See which corner we hit first, left or right
    				if 2*j + 1 > maxi_len:
    					longest_palindrome = s[i-j:i+j+1]
    					maxi_len = 2*j + 1
    				j+=1
    
    		return longest_palindrome

• Container With Most Water
  • Time Complexity: O(n)
  • Space Complexity: O(1)

    #Python3
    class Solution:
    def maxArea(self, height: List[int]) -> int:
    	left, right = 0, len(height) - 1
    	max_area = 0
    
    	while left < right:
    		h = min(height[left], height[right])
    		w = right - left
    
    		if height[left] > height[right]:
    			right -= 1
    		else:
    			left += 1
    
    		max_area = max(max_area, h*w)
    
    	return max_area

    //Go
    func maxArea(height []int) int {
    	left, right := 0, len(height) - 1
    	maxArea := 0
    
    	for left < right {
    		h := min(height[right], height[left])
    		w := right - left
    
    		if height[right] > height[left] {
    			left++
    		} else {
    			right--
    		}
    
    		maxArea = max(maxArea, h*w)
    	}
    	return maxArea
    }

• 3Sum
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

    #Python3
    class Solution:
    	def threeSum(self, nums: List[int]) -> List[List[int]]:
    		nums.sort()  # Sort the array to handle duplicates and simplify the solution
    		res = []
    
    		for i in range(len(nums) - 2):
    			if i > 0 and nums[i] == nums[i - 1]:  # Skip duplicates
    				continue
    			left = i + 1
    			right = len(nums) - 1
    
    			while left < right:
    				total = nums[i] + nums[left] + nums[right]
    				if total == 0:
    					res.append([nums[i], nums[left], nums[right]])
    					# Skip duplicates
    					while left < right and nums[left] == nums[left + 1]:
    						left += 1
    					while left < right and nums[right] == nums[right - 1]:
    						right -= 1
    					left += 1
    					right -= 1
    				elif total < 0:
    					left += 1
    				else:
    					right -= 1
    
    		return res

• Remove Nth Node From End of List

  • Time Complexity: O(n)
  • Space Complexiity: O(1)

    #Python3
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
    	def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    		dummy = ListNode(0)
    		dummy.next = head
    		p1 = p2 = dummy
    
    		for _ in range(n + 1):
    			p2 = p2.next
    
    		while p2:
    			p1 = p1.next
    			p2 = p2.next
    
    		p1.next = p1.next.next
    		return dummy.next

    //Go
    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func removeNthFromEnd(head *ListNode, n int) *ListNode {
    	dummy := &ListNode{Val: 0, Next: head}
    	p1, p2 := dummy, dummy
    
    	for i := 0; i < n+1; i++ {
    		p2 = p2.Next
    	}
    
    	for p2 != nil {
    		p2 = p2.Next
    		p1 = p1.Next
    	}
    
    	p1.Next = p1.Next.Next
    	return dummy.Next
    }

  ---

• Valid Parentheses

  • Time Complexity: O(n)
  • Space Complexity: O(n)

    #Python3
    class Solution:
    	def isValid(self, s: str) -> bool:
    		mapping = {'{': '}', '[': ']', '(': ')'}
    		queue = deque()
    
    		for bracket in s:
    			if bracket in mapping:
    				queue.append(bracket)
    
    			elif len(queue) == 0 or mapping[queue.pop()] != bracket:
    				return False
    
    		return True if len(queue) == 0 else False

    //Go
    func isValid(s string) bool {
    	mapping := map[rune]rune{
    		'(': ')',
    		'{': '}',
    		'[': ']',
    	}
    	stack := make([]rune, 0)
    
    	for _, bracket := range s {
    		switch bracket {
    		case '(', '{', '[':
    			stack = append(stack, bracket)
    		case ')', '}', ']':
    			if len(stack) == 0 || mapping[stack[len(stack)-1]] != bracket {
    				return false
    			}
    			stack = stack[:len(stack)-1]
    		default:
    			// Ignore non-bracket characters
    		}
    	}
    	return len(stack) == 0
    }
    

• Merge Two Sorted Lists

  • Time Complexity: O(n)

  • Space Complexity: O(1)

    #Python3
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
    	def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    		curr = list3 = ListNode()
    
    		while list1 and list2:
    			if list1.val <= list2.val:
    				curr.next = list1
    				list1 = list1.next
    			else:
    				curr.next = list2
    				list2 = list2.next
    
    			curr = curr.next
    
    		if list1 or list2:
    			curr.next = list1 if list1 else list2
    
    		return list3.next

    //Go
    func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    	list3 := new(ListNode)
    	curr := list3
    
    	for list1 != nil && list2 != nil {
    		if list1.Val < list2.Val {
    			curr.Next = list1
    			list1 = list1.Next
    		} else {
    			curr.Next = list2
    			list2 = list2.Next
    		}
    		curr = curr.Next
    	}
    
    	if list1 != nil {
    		curr.Next = list1
    	} else if list2 != nil {
    		curr.Next = list2
    	}
    	return list3.Next
    }

• Merge k Sorted Lists
  • Time Complexity: O(n)
  • Space Complexity: O(1)

    #Python3
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
    	def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    		def merge(left, right):
    			if not left: return right
    			if not right: return left
    			dummy = curr = ListNode()
    			while left and right:
    				if left.val < right.val:
    					curr.next = left
    					left = left.next
    				else:
    					curr.next = right
    					right = right.next
    				curr = curr.next
    			curr.next = left if left else right
    			return dummy.next
    
    		if len(lists) == 1: return lists[0]
    		if len(lists) == 0: return None
    		mid = len(lists) // 2
    		left = self.mergeKLists(lists[:mid])
    		right = self.mergeKLists(lists[mid:])
    		return merge(left, right)

• Search in Rotated Sorted Array
  Note: The Python3 solution is a more intuitive solution that more or less displays how the Golang solution functions

  • Time Complexity: O(log n)
  • Space Complexity: O(1)

    #Python3
    class Solution:
    	def search(self, nums: List[int], target: int) -> int:
    		left, right = 0, len(nums) - 1 
    		pivot = 0
    
    		if len(nums) == 1:
    			return 0 if nums[0] == target else -1
    
    		while left <= right:
    			mid = left + (right - left) // 2
    			if nums[mid] < nums[mid-1]:
    				pivot = mid
    				break
    			elif nums[left] < nums[left-1]:
    				pivot = left
    				break
    			elif nums[right] < nums[right-1]:
    				pivot = right
    				break
    
    			if nums[mid] >= nums[left]: #Pivot idx is to the right
    				left = mid + 1
    
    			else:                       #Pivot idx is to the left
    				right = mid - 1
    
    
    
    		left, right = 0, pivot - 1
    		while left <= right:
    			mid = left + (right-left) // 2
    			if nums[mid] == target:
    				return mid
    
    			elif nums[mid] > target:
    				right = mid - 1
    
    			else:
    				left = mid + 1
    
    		left, right = pivot, len(nums) - 1
    		while left <= right:
    			mid = left + (right-left)//2
    			if nums[mid] == target:
    				return mid
    
    			elif nums[mid] > target:
    				right = mid -1
    
    			else:
    				left = mid + 1
    
    		return -1

    //Go
    func search(nums []int, target int) int {
    	left, right := 0, len(nums) - 1
    
    	for left <= right {
    		mid := left + int((right - left) / 2)
    
    		if nums[mid] == target {
    			return mid
    		}
    
    		if nums[mid] > nums[right] {
    			if nums[left] <= target && target < nums[mid] {
    				right = mid - 1
    			} else {
    				left = mid + 1
    			}
    		} else {
    			if nums[mid] < target && target <= nums[right] {
    				left = mid + 1
    			} else {
    				right = mid - 1
    			}
    		}
    	}
    
    	return -1
    }

  ---

• Combination Sum

  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

    #Python3
    class Solution:
    	def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    		def backtrack(start, target, path):
    			if target == 0:
    				result.append(path)
    				return
    			if target < 0:
    				return
    			for i in range(start, len(candidates)):
    				backtrack(i, target - candidates[i], path + [candidates[i]])
    
    		result = []
    		candidates.sort()
    		backtrack(0, target, [])
    		return result

• Rotate Image
  • Time Complexity: O(n²)
  • Space Complexity: O(1)

    #Python3
    class Solution:
    	def rotate(self, matrix: List[List[int]]) -> None:
    		#Transpose
    		n = len(matrix)
    		for i in range(n):
    			for j in range(i):
    				matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    		#Swap columns
    		for i in range(n):
    			matrix[i] = matrix[i][::-1]

    //Go
    func reverse(array []int) []int {
    	m := len(array)
    	for i := 0; i < m/2; i++ {
    		array[i], array[m-i-1] = array[m-i-1], array[i]
    	}
    	return array
    }
    
    func rotate(matrix [][]int)  {
    	n := len(matrix)
    	for i := 0; i < n; i++ {
    		for j := 0; j < i; j++ {
    			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    		}
    	}
    
    	for i := 0; i < n; i++ {
    		matrix[i] = reverse(matrix[i])
    	}
    
    }

• Group Anagrams
  • Time Complexity: O(n ⋅ k log k) -|- k = length of longest anagram
  • Space Complexity: O(n)

    #Python3
    class Solution:
    	def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    		mapper = {}
    
    		for string in strs:
    			sorted_str = str(sorted(string))
    			if sorted_str in mapper:
    				mapper[sorted_str].append(string)
    			else:
    				mapper[sorted_str] = [string]
    
    		return list(mapper.values())