kadane’s algorithm: maximum subarray problem

Resources:

1. Wiki Explanation

Problem using Dynamic Programming to save time:

1. 53. Maximum Subarray
2. 121. Best Time to Buy and Sell Stock
3. 122. Best Time to Buy and Sell Stock II
4. 152. Maximum Product Subarray
5. 198. House Robber
6. 213. House Robber II
7. 276. Paint Fence
8. 312. Burst Balloons (Similar Problem: Matrix Chain Multiplication)

Problem like trapping water:

1. 42. Trapping Rain Water
2. 11. Container With Most Water
3. 407. Trapping Rain Water II
4. 238. Product of Array Except Self

Problem using buckets check:

1. 220. Contains Duplicate III
2. 204. Count Primes

Problem using factors:

1. 172. Factorial Trailing Zeroes

Prolbem using elegant pointer solution:

1. 160. Intersection of Two Linked Lists
2. 26. Remove Duplicates from Sorted Array
3. 328. Odd Even Linked List
4. 223. Rectangle Area
5. 28. Implement strStr()
6. 566. Reshape the Matrix
7. 243. Shortest Word Distance
8. 447. Number of Boomerangs
9. 276. Paint Fence
10. 438. Find All Anagrams in a String (Love this Problem, good template)
11. 455. Assign Cookies
12. 475. Heaters
13. 599. Minimum Index Sum of Two Lists
14. 633. Sum of Square Numbers
15. 246. Strobogrammatic Number
16. 594. Longest Harmonious Subsequence
17. 598. Range Addition II
18. 581. Shortest Unsorted Continuous Subarray
19. 624. Maximum Distance in Arrays
20. 228. Summary Ranges

Problem using stack:

1. 150. Evaluate Reverse Polish Notation

Problem using lambda expression:

1. 56. Merge Intervals
2. 179. Largest Number

Problem use matrix/array indexing tricks:

1. 48. Rotate Image
2. 419. Battleships in a Board
3. 242. Valid Anagram
4. 657. Judge Route Circle
5. 345. Reverse Vowels of a String (Reversal is all about swap. Two pointer problem)
6. 414. Third Maximum Number

Problem using recursion:

1. 669. Trim a Binary Search Tree

Problem use resversal:

1. 190. Reverse Bits

Problem using the idea of data engineering:

1. 350. Intersection of Two Arrays II

Problem with easy logic but tricky with details.

1. 69. Sqrt(x)
2. 168. Excel Sheet Column Title
3. 203. Remove Linked List Elements
4. 476. Number Complement
5. 374. Guess Number Higher or Lower
6. 278. First Bad Version
7. 83. Remove Duplicates from Sorted List
8. 35. Search Insert Position
9. 367. Valid Perfect Square
10. 414. Third Maximum Number
11. 475. Heaters
12. 680. Valid Palindrome II
13. 422. Valid Word Square
14. 408. Valid Word Abbreviation
15. 604. Design Compressed String Iterator

Problem using math tricks:

1. 453. Minimum Moves to Equal Array Elements
2. 400. Nth Digit
3. 459. Repeated Substring Pattern

Design Problem:

1. 170. Two Sum III - Data structure design

Problem might fool you:

1. 521. Longest Uncommon Subsequence I
2. 605. Can Place Flowers
3. 665. Non-decreasing Array

Bit Manipulation:

1. 405. Convert a Number to Hexadecimal

Tree Travesal:

1. 671. Second Minimum Node In a Binary Tree

SQL:

1. 603. Consecutive Available Seats

---

Elegant Solution:

1. 2. Add Two Numbers