leetcode-cpp-practices

Including problem statement, solution, runtime and complexity analysis.

DSA

HassanElDesouky/AwesomeLeetCodeDiscussions

Important and Useful links from all over the Leetcode

Interview Preparation for Beginners - [ DS | Algorithms | OS | System Design ]

A few helpful links to posts which tell you HOW to grind leetcode

Comprehensive Data Structure and Algorithm Study Guide

My System Design Template

BFS

Bidirectional BFS

127. Word Ladder.cpp

126. Word Ladder II.cpp

Tree

Binary tree traversal

Preorder, Inorder, and Postorder Iteratively Summarization

94. Binary Tree Inorder Traversal.cpp

173. Binary Search Tree Iterator.cpp

144. Binary Tree Preorder Traversal.cpp

145. Binary Tree Postorder Traversal.cpp

Threaded binary tree, Morris Traversal

Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）

94. Binary Tree Inorder Traversal.cpp

99. Recover Binary Search Tree.cpp

538. Convert BST to Greater Tree.cpp

Tree diameter

Diameter of a tree using DFS

1617. Count Subtrees With Max Distance Between Cities.cpp

1405D - Tree Tag.md

Graph

Graph Problems For Beginners Practice [Problems and Sample Solutions]

Single Source Shortest Path

Bellman Ford

relax for V-1 times, works for negative weighted edges, time complexity: O(VE)

Bellman Ford(including proof)

SPFA(Shortest Path Faster Algorithm)

Dijkstra

greedy, not work for negative weighted edges

DS	time complexity
adjacency matrix	O(V^2)
adjacency list + binary heap	O(ElogV)
adjacency list + Fabonacci heap	O(VlogV + E)

Dijkstra’s algorithm - theorem

Dijkstra's algorithm - C++ implementation

All Pairs Shortest Path

Floyd Warshall

399. Evaluate Division.cpp

Tarjan's algorithm

Articulation Points (or Cut Vertices) in a Graph

1568. Minimum Number of Days to Disconnect Island.cpp

Bridges in a graph

1192. Critical Connections in a Network.cpp

Cycle detection

Cycle detection in directed graph

Detect Cycle in a Directed Graph

207. Course Schedule.cpp

1591. Strange Printer II.cpp

Cycle detection in undirected graph

Detect cycle in an undirected graph: the text description is wrong, watch the video

1559. Detect Cycles in 2D Grid.cpp

Minimum spanning tree, Prim's algorithm(Greedy)

Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5

Minimum cost to connect all cities

1584. Min Cost to Connect All Points.cpp

Two pointers

11. Container With Most Water

15. 3Sum

16. 3Sum Closest

18. 4Sum

26. Remove Duplicates from Sorted Array.cpp

80. Remove Duplicates from Sorted Array II.cpp

27. Remove Element.cpp

28. Implement strStr().cpp

42. Trapping Rain Water.cpp

75. Sort Colors.cpp

76. Minimum Window Substring.cpp

88. Merge Sorted Array.cpp

125. Valid Palindrome.cpp

141. Linked List Cycle.cpp

142. Linked List Cycle II.cpp

167. Two Sum II - Input array is sorted.cpp

214. Shortest Palindrome.cpp

234. Palindrome Linked List.cpp

283. Move Zeroes.cpp

287. Find the Duplicate Number.cpp

344. Reverse String.cpp

345. Reverse Vowels of a String.cpp

349. Intersection of Two Arrays.cpp

350. Intersection of Two Arrays II.cpp

424. Longest Repeating Character Replacement.cpp

524. Longest Word in Dictionary through Deleting.cpp

763. Partition Labels.cpp

838. Push Dominoes.cpp

844. Backspace String Compare.cpp

881. Boats to Save People.cpp

925. Long Pressed Name.cpp

977. Squares of a Sorted Array.cpp

986. Interval List Intersections.cpp

1004. Max Consecutive Ones III.cpp

1248. Count Number of Nice Subarrays.cpp

1574. Shortest Subarray to be Removed to Make Array Sorted.cpp

Sliding Window

Sliding Window for Beginners [Problems | Template | Sample Solutions]

713. Subarray Product Less Than K.cpp

Monotonic stack

Python solution using monotonic stack, similar pattern questions listed

84. Largest Rectangle in Histogram.cpp

85. Maximal Rectangle.cpp

503. Next Greater Element II.cpp

901. Online Stock Span.cpp

1475. Final Prices With a Special Discount in a Shop.cpp

1504. Count Submatrices With All Ones.cpp

Monotonic queue(Deque)

Monotonic Queue Summary

Monotonic Queue Explained with LeetCode Problems

45. Jump Game II.cpp

122. Best Time to Buy and Sell Stock II.cpp

239. Sliding Window Maximum.cpp

918. Maximum Sum Circular Subarray.cpp

1425. Constrained Subsequence Sum.cpp

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.cpp

1499. Max Value of Equation.cpp

Multiset

It serves as Self-balancing Binary Search Trees (like an AVL Tree).

218. The Skyline Problem.cpp

295. Find Median from Data Stream.cpp

332. Reconstruct Itinerary.cpp

480. Sliding Window Median.cpp

645. Set Mismatch.cpp

Bit manipulation

Detailed explanation and generalization of the bitwise operation method for single numbers

136. Single Number.cpp

137. Single Number II.cpp

260. Single Number III.cpp

169. Majority Element.cpp

187. Repeated DNA Sequences.cpp

190. Reverse Bits.cpp

191. Number of 1 Bits.cpp

239. Sliding Window Maximum.cpp

268. Missing Number.cpp

338. Counting Bits.cpp

342. Power of Four.cpp

477. Total Hamming Distance.cpp

Binary Search

二分查找详解

Binary Search for Beginners [Problems | Patterns | Sample solutions]

"378. Kth Smallest Element in a Sorted Matrix" and its variant

Summary of solutions for problems "reducible" to LeetCode 378

378. Kth Smallest Element in a Sorted Matrix.cpp

373. Find K Pairs with Smallest Sums.cpp

668. Kth Smallest Number in Multiplication Table.cpp

719. Find K-th Smallest Pair Distance.cpp

786. K-th Smallest Prime Fraction.cpp

find local maximum/minimum

162. Find Peak Element.cpp

---

35. Search Insert Position.cpp

69. Sqrt(x).cpp

74. Search a 2D Matrix.cpp

167. Two Sum II - Input array is sorted.cpp

230. Kth Smallest Element in a BST.cpp

240. Search a 2D Matrix II.cpp

287. Find the Duplicate Number.cpp

349. Intersection of Two Arrays.cpp

350. Intersection of Two Arrays II.cpp

367. Valid Perfect Square.cpp

374. Guess Number Higher or Lower.cpp

392. Is Subsequence.cpp

441. Arranging Coins.cpp

454. 4Sum II.cpp

704. Binary Search.cpp

744. Find Smallest Letter Greater Than Target.cpp

852. Peak Index in a Mountain Array.cpp

981. Time Based Key-Value Store.cpp

1011. Capacity To Ship Packages Within D Days.cpp

1111. Maximum Nesting Depth of Two Valid Parentheses Strings.cpp

1235. Maximum Profit in Job Scheduling.cpp

1237. Find Positive Integer Solution for a Given Equation.cpp

Backtracking

A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partioning)

39. Combination Sum.cpp

40. Combination Sum II.cpp

216. Combination Sum III.cpp

46. Permutations.cpp

47. Permutations II.cpp

78. Subsets.cpp

90. Subsets II.cpp

131. Palindrome Partitioning.cpp

---

51. N-Queens.cpp

52. N-Queens II.cpp

211. Add and Search Word - Data structure design.cpp

401. Binary Watch.cpp

784. Letter Case Permutation.cpp

980. Unique Paths III.cpp

1079. Letter Tile Possibilities.cpp

1219. Path with Maximum Gold.cpp

1286. Iterator for Combination.cpp

Dynamic Programming

Dynamic Programming Patterns

DP for Beginners [Problems | Patterns | Sample Solutions]

Checking for "Overlapping subproblem" property

How to solve DP - String? Template and 4 Steps to be followed.

My experience and notes for learning DP

DP problem categories

Dynamic Programming Patterns

303. Range Sum Query - Immutable.cpp

312. Burst Balloons.cpp

338. Counting Bits.cpp

392. Is Subsequence.cpp

413. Arithmetic Slices.cpp

486. Predict the Winner.cpp

647. Palindromic Substrings.cpp

746. Min Cost Climbing Stairs.cpp

838. Push Dominoes.cpp

931. Minimum Falling Path Sum.cpp

983. Minimum Cost For Tickets.cpp

1025. Divisor Game.cpp

1027. Longest Arithmetic Sequence.cpp

1048. Longest String Chain.cpp

1074. Number of Submatrices That Sum to Target.cpp

1130. Minimum Cost Tree From Leaf Values.cpp

1143. Longest Common Subsequence.cpp

1147. Longest Chunked Palindrome Decomposition.cpp

1235. Maximum Profit in Job Scheduling.cpp

1277. Count Square Submatrices with All Ones.cpp

1289. Minimum Falling Path Sum II.cpp

1314. Matrix Block Sum.cpp

1359. Count All Valid Pickup and Delivery Options.cpp

1388. Pizza With Slices.cpp

1397. Find All Good Strings.cpp

1402. Reducing Dishes.cpp

1405. Longest Happy String.cpp

Stock series

Leetcode discussion - Most consistent ways of dealing with the series of stock problems

121. Best Time to Buy and Sell Stock.cpp

122. Best Time to Buy and Sell Stock II

123. Best Time to Buy and Sell Stock III.cpp

188. Best Time to Buy and Sell Stock IV.cpp

309. Best Time to Buy and Sell Stock with Cooldown.cpp

714. Best Time to Buy and Sell Stock with Transaction Fee.cpp

House bobber seires

198. House Robber.cpp

213. House Robber II.cpp

337. House Robber III.cpp

Knapsack problem

0/1 knapsack problem

416. Partition Equal Subset Sum.cpp

494. Target Sum.cpp

Unbounded knapsack problem

322. Coin Change.cpp

518. Coin Change 2.cpp

Two-constraint knapsack problem

474. Ones and Zeroes.cpp

LIS

300. Longest Increasing Subsequence.cpp

354. Russian Doll Envelopes.cpp

368. Largest Divisible Subset.cpp

DP + Tree

124. Binary Tree Maximum Path Sum.cpp

337. House Robber III.cpp

543. Diameter of Binary Tree.cpp

Digits

233. Number of Digit One.cpp

902. Numbers At Most N Given Digit Set.cpp

1015. Smallest Integer Divisible by K.cpp

Counting

62. Unique Paths.cpp

63. Unique Paths II.cpp

96. Unique Binary Search Trees.cpp

Recursion

70. Climbing Stairs.cpp

509. Fibonacci Number.cpp

935. Knight Dialer.cpp

957. Prison Cells After N Days.cpp

1137. N-th Tribonacci Number.cpp

Probability

808. Soup Servings.cpp

837. New 21 Game.cpp

Game

Nim game

292. Nim Game.cpp

Stone game

877. Stone Game.cpp

1140. Stone Game II.cpp

1406. Stone Game III.cpp

1510. Stone Game IV.cpp

Tic Tac Toe game

794. Valid Tic-Tac-Toe State.cpp

1275. Find Winner on a Tic Tac Toe Game.cpp

DFS + memorization

329. Longest Increasing Path in a Matrix.cpp

576. Out of Boundary Paths.cpp

Dynamic Programming + Bitmask

A simple tutorial on this bitmasking problem

464. Can I Win.cpp

526. Beautiful Arrangement.cpp

698. Partition to K Equal Sum Subsets

1349. Maximum Students Taking Exam.cpp

1434. Number of Ways to Wear Different Hats to Each Other.cpp

1494. Parallel Courses II.cpp

1595. Minimum Cost to Connect Two Groups of Points.cpp

KMP

KMP Algorithm for Pattern Searching

28. Implement strStr().cpp

187. Repeated DNA Sequences.cpp

214. Shortest Palindrome.cpp

796. Rotate String.cpp

1392. Longest Happy Prefix.cpp

1397. Find All Good Strings.cpp

1408. String Matching in an Array.cpp

Manacher's algorithm

Longest Palindromic Substring O(N) Manacher's Algorithm

Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 4

[译]最长回文子串(Longest Palindromic Substring) Part I

[译+改]最长回文子串(Longest Palindromic Substring) Part II

5. Longest Palindromic Substring.cpp

214. Shortest Palindrome.cpp

647. Palindromic Substrings.cpp

Greedy

Greedy for Beginners [Problems | Sample solutions]

Interval

56. Merge Intervals.cpp

435. Non-overlapping Intervals.cpp

452. Minimum Number of Arrows to Burst Balloons.cpp

1589. Maximum Sum Obtained of Any Permutation.cpp

1109. Corporate Flight Bookings.cpp

Rolling hash, Rabin-Karp

Why is the base used to compute hashes in Rabin–Karp always primes?

686. Repeated String Match.cpp

1044. Longest Duplicate Substring.cpp

1147. Longest Chunked Palindrome Decomposition.cpp

Regex

591. Tag Validator.cpp

1071. Greatest Common Divisor of Strings.cpp

Trie

Article on Trie. General Template and List of problems.

208. Implement Trie (Prefix Tree).cpp

211. Add and Search Word - Data structure design.cpp

212. Word Search II.cpp

336. Palindrome Pairs.cpp

1268. Search Suggestions System.cpp

648. Replace Words.cpp

676. Implement Magic Dictionary.cpp

720. Longest Word in Dictionary.cpp

Suffix Tree

Trie, Suffix Tree, Suffix Array

Ukkonen's suffix tree algorithm in plain English

1408. String Matching in an Array.cpp

Union Find

Union find problems look alike graph problems, if we only care whether two nodes are connected, not their distance, we should use union find.(?, inspired by 1627)

959. Regions Cut By Slashes.cpp

547. Friend Circles.cpp

1391. Check if There is a Valid Path in a Grid.cpp

399. Evaluate Division.cpp

130. Surrounded Regions.cpp

128. Longest Consecutive Sequence.cpp

1559. Detect Cycles in 2D Grid.cpp

1562. Find Latest Group of Size M.cpp

1627. Graph Connectivity With Threshold

Union by rank

684. Redundant Connection.cpp

Segment Tree

307. Range Sum Query - Mutable(solution)

A Recursive approach to Segment Trees, Range Sum Queries & Lazy Propagation

307. Range Sum Query - Mutable Medium.cpp

315. Count of Smaller Numbers After Self.cpp

850. Rectangle Area II.cpp

673. Number of Longest Increasing Subsequence.cpp

218. The Skyline Problem.cpp

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits.cpp

Binary Indexed Tree

Java using Binary Indexed Tree with clear explanation

Topcode binary indexed trees tutorial

307. Range Sum Query - Mutable Medium.cpp

315. Count of Smaller Numbers After Self.cpp

1395. Count Number of Teams.cpp

218. The Skyline Problem.cpp

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits.cpp

Binary Indexed Tree : Range Updates and Point Queries

1589. Maximum Sum Obtained of Any Permutation.cpp

Line Sweep

850. Rectangle Area II.cpp

218. The Skyline Problem.cpp

1109. Corporate Flight Bookings.cpp

1589. Maximum Sum Obtained of Any Permutation.cpp

Angular Sweep

1453. Maximum Number of Darts Inside of a Circular Dartboard.cpp