algorithm leetcode

Leetcode Progress Summary

Posted by Luna's Blog on February 6, 2022

DP

Problem Title Status notes
167. Two Sum II - Input Array Is Sorted ✅ left & right pointer
11.Container With Most Water ✅ left & right pointer
15. 3 Sum ✅ Solution left & right pointer
16. 3 Sum Closest    
18. 4 Sum ✅ Solution  
19. Remove Nth Node From End of List    
26. Remove Duplicates From Sorted Array Given a sorted array, remove the duplicates in the array such that each element appears only once. ✅ similar problem
82. Remove Duplicates from Sorted List II
83. Remove Duplicates from Sorted List
1836. Remove Duplicates From an Unsorted Linked List
28. Implement strStr() Return the index of the first occurrence of substring in a string ✅ KMP will be better
42. Traping Rain Watter ✅ Left & right pointer, Need more practice
11. Container With Most Water
75. Sort Colors ✅Solution Left & Right pointer
80. Remove Duplicates from Sorted Array II Given a sorted array, remove the duplicates in the array such that each unique element appears at most twice ✅  
125. Valid Palindrome ✅ Useful Python string methods: s.lower() s.isalpha() s.isnumeric() s.isalnum() Left & right pointer.
345. Reverse Vowels in String ✅ Left & right pointer s is not changable, we should us s = list(s)
532. K-diff Pairs in an Array Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array. ✅ fast & slow pointer
557. Reverse Words in a String III ✅ fast & slow pointer, s[slow:fast] = reversed(s[slow:fast])
Leetcode 905. Sort Array By Parity ✅ fast & slow pointer
Leetcode 922. Sort Array By Parity II ✅ even & odd pointer
Leetcode 977 Squares of a Sorted Array ✅ Solution left & right pointer.

Linked List

ProblemTitle Content Status notes
258. Add Digits Given an integer num, repeatedly add all its digits until the result has only one digit, and return it. ✅ $nums = d_0 + d_1*10 + … + d_k * 10 ^ k$
$ = (d_0 + d_1 + … + d_k) + 9 * m$
$(d_0 + d_1 + … + d_k) \% 9 = nums \% 9$
50. Pow(x, n) Solution ✅ Divide and Conquer
191. Number of 1 Bits Solution similar problems: https://leetcode.com/problems/power-of-two/ Bit manipulation: n&(n-1)
190. Reverse Bits     Bit manipulation: n & 1 | ans « 1

String Problems

Problem Title Status Notes
14. Longest Common Prefix ✅ LCP(S1…Sn) = LCP(LCP(LCP(S1,S2), S3)… Sn)
151. Reverse Words in a String ✅ ” “.join(reversed(s.split()))

Sweep Line

Title Solution Notes
252. Meeting Rooms Solution  
253. Meeting Rooms II Solution  
56. Merge Intervals Solution  
57. Insert Interval Solution  
1094. Car Pooling Solution  
1272.Remove Intervals Solution  
435. Non-overlapping Intervals Sweep Line Solution
DP Solution		  
452. Minimum Number of Arrows to Burst Balloons Solution Similar to the non-overlapping problem
1288. Remove Covered Intervals Solution  

Diff Array

diff[i] means nums[i] - nums[i-1] => nums[i] = nums[i-1] + diff[i]

Title Solution Notes
370. Range Addition   ✅
1094. Car Pooling Solution ✅ Can also be solved via sweep line
1109. Coporate Flight Bookings solution ✅Can also be solved via sweep line

DP

Title Solution Notes
413. Arithmetic Slices    

Tree Problems

BST

DFS

Others

DFS

Graph DFS

  • 133. Clone Graph

  • 207. Course Schedule
    • construct a dict from prerequisites <course, List[pre]>
    • go through courses,
      • return True if no prerequisites
      • return False if visit already
      • add course into visit set and dfs its children
      • set pre to [] if the course can be completed to avoid duplicate dfsß
      • remember to remove the course from visit
  • 130. Surrounded Regions
    • dfs and mark boarder ‘O’s, other ‘O’s can be changed to ‘X’

Islands

Topological Sort

Backtracking

Stack

Monotonic Stack (单调栈)

Greedy

Heap

Some Tricks

​

CATALOG
    FEATURED TAGS
    Japanese algorithm cpsc340 leetcode machine learning ubc frontend binary search