leetcode

README

LeetCode

My submissions for LeetCode Oj.

Tags

• Array
• Linked List
• Depth First Search
• Breadth First Search
• Two Pointers
• Sliding Window
• Bit
• Stack
• HashMap
• Heap
• Random
• DP
• Design
• Binary Search
• Math
• String
• Tree
• Graph

Categories

Array

Title	Solution	Difficulty
1. Two Sum	use hashmap	Easy
719. Find K-th Smallest Pair Distance	Bucket Sort, Binary Search	Hard
581. Shortest Unsorted Continuous Subarray	four passes	Easy
34. Find First and Last Position of Element in Sorted Array	use lowerBound	Medium
238. Product of Array Except Self	use two additional product array	Medium
283. Move Zeros	use two pointers	Easy
215. Kth Largest Element in an Array	use sort	Medium
26. Remove Duplicates from Sorted Array	simple traverse	Easy
135. Candy	use one array two passes	Hard
1046. Last Stone Weight	use bucket	Easy
1424. Diagonal Traverse II	use #hashmap	Medium
278. First Bad Version	use binary search	Easy
739. Daily Temperatures	use stack	Medium
1277. Count Square Submatrices with All Ones	use dp	Medium
1035. Uncrossed Lines	use dp same approach as longest common sequences	Medium
1338. Reduce Array Size to The Half	use hashmap	Medium
368. Largest Divisible Subset	use dp	Medium
1535. Find the Winner of an Array Game	use one pass with constant space	Medium

Bit

Title	Solution	Difficulty
342. Power Of Four	Use loop, Bit Manipulation	Easy
136. Single Number	xor	Easy

Linked List

Title	Solution	Difficulty
148. Sort List	Bottom Up Merge Sort	Medium
92. Reverse Linked List II	Use Dummmy node to iterator the list	Medium
2. Add Two Numbere	Use Sentinel Node	Medium
21. Merge Two Sorted List	Using golang channel	Easy
23. Merge K Sorted Lists	Divide and Conquer	Hard
138. Copy List With Random Pointer	Extend List with copied Nodes	Medium
141. Linked List Cycle	Two Pointers	Easy
24. Swap Nodes In Pairs	Use dummy node to iterator the list	Medium
234. Palindrome Linked List	Two Pointers	Easy
328. Odd Even Linked List	dummy node	Medium
147. Insertion Sort List	dummy node	Medium
445. Add Two Numbers II	reverse the list	Medium
143. Reorder List	Two Pointers	Medium
19. Remove Nth Node from end of List	Two Pointers with n+1 gap	Medium
86. Partition List	Two pointers	Medium
369. Plus One Linked List	Dummy Node	Medium
82. Remove Duplicates From Sorted Linkde List II	Dummy Node with recursive helper func, Dummy Node in place	Medium
876. Middle of the Linked List	Two Pointers	Easy
61. Rotate List	reverse list	Medium
1171. Remove Zero Sum Consecutive Nodes from Linked List	Two passes preSum with hashmap	Medium
25. Reverse Nodes in k-Groups	using iterator	Hard
1290. Convert Binary Number to Integer	strconv.ParseUInt's implementation	Easy
707. Design Linked List	Single Linked List with Count	Medium
725. Split Linked List In Parts	Two passes	Medium
817. Linked List Components	iterator+set	Medium
430. Flatten a Multilevel Doubly Linked List	preOrder use recursion	Medium
426. Convert Binary Search Tree to Sorted Doubly Linked List	inOrder traversal using stack	Medium

Sliding Window

Title	Solution	Difficulty
719. Find K-th Smallest Pair Distance	Binary Search+Sliding Window	Hard

Stack

Title	Solution	Difficulty
636. Exclusive Time of Functions	Use stack to track function id	Medium
394. Decode String	use two stacks	Medium
901. Online Stock Span	use stack	Medium

HashMap

Title	Solution	Difficulty
1048. Longest String Chain	hashmap + DFS + Memorization	Medium
36. Valid Sudoku	use hashmaps	Medium
380. Insert Delete GetRandom O(1)	hashmap and array	Medium
381. Insert Delete GetRandom O(1) - Duplicates allowed	use hashmap and unordered_set	Hard
525. Contiguous Array	use hashmap	Medium
560. Subarray Sum Equals K	use hashmap	Medium

Breadth First Search

Title	Solution	Difficulty
200. Number OfIslands	use BFS	Medium

Depth First Search

Title	Solution	Difficulty
200. Number OfIslands	use DFS	Medium
100. Same Tree	use DFS	Easy
101. Symmeetric Tree	use DFS	Easy
104. Max Depth of Binary Tree	DFS	Easy
124. Binary Tree Maximum Path Sum	use DFS and a global max	Hard
1192. Critical Connections in a Network	Tarjan's algorithm	Hard
301. Remove Invalid Parentheses	use backtracking	Hard
105. Construct Binary Tree from Preorder and Inorder Traversal	use DFS	Medium
106. Construct Binary Tree From Inorder and Postorder Traversal	use DFS	Medium
1026. Maximum Difference Between Node and Ancestor	use dfs with min and max node	Medium
1008. Construct Binary Search Tree from Preorder Traversal	use dfs with sliced orders	Medium
993. Cousins in Binary Tree	use dfs	Easy

Heap

Title	Solution	Difficulty
973. K Closest Points to Origin	use max-k-heap, use quick select	Medium

Random

Title	Solution	Difficulty
528. Random Pick with Weight	use rand.Intn and binary search	Medium

DP

Title	Solution	Difficulty
123. Best Time to Buy and Sell Stock III	use dp[k][j] to represent at day j's max profit with at most k transactions	Hard
97. Interleaving String	Use a 2D array, dp[i][j] represents whether s1[:i], s2[:j] and s3[:i+j] are interleaving strings	Hard
64. Minimum Path Sum	dp[i] = min(dp[i],dp[i-1]) + grid[j][i]	Medium
1143. Longest Common Subsequence	use dp with less space	Medium

Design

Title	Solution	Difficulty
146. LRU Cache	use doubly linked list with hashmap	Medium

Binary Search

Title	Solution	Difficulty
5. Longest Palindromic Substring	parity binary search	Meidum
33. Search in Rotated Sorted Array	use binary search with one pass	Medium
202. Happy Number	use floyed's algorithm	Easy
Leftmost Column with at least a One	use binary search (lower bound)	Meidum
540. Single Element in a Sorted Array	use binary search	Medium
1231. Divide Chocolate	answer in the range min(chocolate), sum(chocolate)	Medium

String

Title	Solution	Difficulty
844. Backspace String Compare	use two pointers	Easy
316. Remove Duplicate Letters	use stack and hashmap	Hard
678. Valid Parenthesis String	greedy	Medium
771. Jewels and Stones	use #hashmap	Easy
383. Ransom Note	use hashmap	Easy
402. Remove K Digits	use greedy with stack	Medium
451. Sort Characters By Frequency	use hashmap	Medium
856. Score of Parentheses	use stack to store the score	Medium
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence	onepass use strings.Fields and strings.HasPrefix	Easy
1456. Maximum Number of Vowels in a Substring of Given Length	use slide window	Medium

Tree

Title	Solution	Difficulty
1457. Pseudo-Palindromic Paths in a Binary Tree	use backtracking	Meidum
1466. Reorder Routes to Make All Paths Lead to the City Zero	convert to a tree like problem then use dfs	Medium
236. Lowest Common Ancestor of a Binary Tree	use dfs	Medium

Graph

Title	Solution	Difficulty
1462. Course Schedule IV	use floyd wrashall	Medium