Leetcode Study Guide

Table of Contents

• Background
• Preface
• Java Syntax Notes
• Question List
  • Arrays
  • Backtracking
  • Dynamic Programming
  • Fast & Slow Pointers
  • In-place Reversal of a Linked List
  • K-Way Merge
  • Merge Intervals
  • Modified Binary Search
  • Sliding Window
  • Topological Sort
  • Tree Breadth First Search
  • Tree Depth First Search
  • Top K Elements
  • Two Heaps
  • Two Pointers
• Tips to Consider
• Acknowledgements

Background

This list is intended to be used as a study guide for any individual wanting to improve their problem solving skills for Software Engineering interviews. It separates problems into their subtopic, so you can focus on a specific approach over a range of difficulties.

All questions are available on leetcode.com with some requiring leetcode premium.

Preface

It is highly recommended to read chapters 1, 2, 3, 4, 8, and 10 of Cracking The Coding Interview to familiarize yourself with the following data structures and their operations:

• Arrays
  • Single and two dimensional
• Maps
• Sets
• Linked Lists
  • Single/doubly linked
• Heaps
  • Min/max heap
• Stacks
• Binary (Search) Trees
  • Trie
• Graphs
• Queue

In addition, you should have a good grasp on common algorithms such as:

• Breadth-first search
• Depth-first search
• Binary search
• Recursion

Java Syntax Notes

This pdf contains useful information for the built-in data structures in Java.

Question List

Pattern: Sliding Window

Medium:

1. Minimum Size Subarray Sum: https://leetcode.com/problems/minimum-size-subarray-sum/
2. Fruit Into Baskets: https://leetcode.com/problems/fruit-into-baskets/
3. Permutation in String: https://leetcode.com/problems/permutation-in-string/
4. Longest Repeating Character Replacement: https://leetcode.com/problems/longest-repeating-character-replacement/

Hard:

1. Sliding Window Maximum: https://leetcode.com/problems/sliding-window-maximum/
2. Longest Substring Without Repeating Characters: https://leetcode.com/problems/longest-substring-without-repeating-characters/
3. Minimum Number of K Consecutive Bit Flips: https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
4. Unique Letter String: https://leetcode.com/problems/unique-letter-string/
5. Minimum Window Substring: https://leetcode.com/problems/minimum-window-substring/
6. Substring with Concatenation of All Words: https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Pattern: Two Pointers

Easy:

1. Two Sum: https://leetcode.com/problems/two-sum/
2. Remove Duplicates from Sorted List: https://leetcode.com/problems/remove-duplicates-from-sorted-list/
3. Squares of a Sorted Array: https://leetcode.com/problems/squares-of-a-sorted-array/
4. Backspace String Compare: https://leetcode.com/problems/backspace-string-compare

Medium:

1. 3 Sum: https://leetcode.com/problems/3sum/
2. 3 Sum Closest: https://leetcode.com/problems/3sum-closest/
3. Subarrays with Product Less than K: https://leetcode.com/problems/subarray-product-less-than-k/
4. Sort Colours: https://leetcode.com/problems/sort-colors/

Hard:

1. Minimum Window Substring: https://leetcode.com/problems/minimum-window-substring/
2. Trapping Rain Water: https://leetcode.com/problems/trapping-rain-water/
3. Container With Most Water: https://leetcode.com/problems/container-with-most-water/

Pattern: Fast & Slow Pointers

Easy:

1. Linked List Cycle: https://leetcode.com/problems/linked-list-cycle/
2. Middle of the Linked List: https://leetcode.com/problems/middle-of-the-linked-list/
3. Palindrome Linked List: https://leetcode.com/problems/palindrome-linked-list/
4. Remove Linked List Elements: https://leetcode.com/problems/remove-linked-list-elements/
5. Remove Duplicates from Sorted List: https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Medium:

1. Linked List Cycle II: https://leetcode.com/problems/linked-list-cycle-ii/
2. Add Two Numbers: https://leetcode.com/problems/add-two-numbers/,
3. Sort List: https://leetcode.com/problems/sort-list/

Pattern: Merge Intervals

Easy:

1. Meeting Rooms: https://leetcode.com/problems/meeting-rooms

Medium:

1. Merge Intervals: https://leetcode.com/problems/merge-intervals/
2. Interval List Intersections: https://leetcode.com/problems/interval-list-intersections/
3. Non-overlapping Intervals: https://leetcode.com/problems/non-overlapping-intervals/
4. Meeting Rooms II: https://leetcode.com/problems/meeting-rooms-ii/
5. Task Scheduler: https://leetcode.com/problems/task-scheduler/
6. Minimum Number of Arrows to Burst Balloons: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

Hard:

1. Insert Interval: https://leetcode.com/problems/insert-interval/
2. Employee Free Time: https://leetcode.com/problems/employee-free-time/

Pattern: Arrays

Easy:

1. Missing Number: https://leetcode.com/problems/missing-number/
2. Find All Numbers Disappeared in an Array: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
3. Single Number: https://leetcode.com/problems/single-number/

Medium:

1. Find the Duplicate Number: https://leetcode.com/problems/find-the-duplicate-number/
2. Find All Duplicates in an Array: https://leetcode.com/problems/find-all-duplicates-in-an-array/

Hard:

1. First Missing Positive: https://leetcode.com/problems/first-missing-positive/

Pattern: In-place Reversal of a Linked List

Easy:

1. Reverse Linked List: https://leetcode.com/problems/reverse-linked-list/

Medium:

1. Reverse Linked List II: https://leetcode.com/problems/reverse-linked-list-ii/
2. Rotate List: https://leetcode.com/problems/rotate-list/
3. Swap Nodes in Pairs: https://leetcode.com/problems/swap-nodes-in-pairs/
4. Odd Even Linked List: https://leetcode.com/problems/odd-even-linked-list/

Hard:

1. Reverse Nodes in k-Group: https://leetcode.com/problems/reverse-nodes-in-k-group/

Pattern: Tree Breadth First Search

Easy:

1. Binary Tree Level Order Traversal II: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
2. Average of Levels in Binary Tree: https://leetcode.com/problems/average-of-levels-in-binary-tree/
3. Minimum Depth of Binary Tree: https://leetcode.com/problems/minimum-depth-of-binary-tree/

Medium:

1. Binary Tree Level Order Traversal: https://leetcode.com/problems/binary-tree-level-order-traversal/
2. Binary Tree Zigzag Level Order Traversal: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
3. Populating Next Right Pointers in Each Node: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
4. Populating Next Right Pointers in Each Node II: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
5. Binary Tree Right Side View: https://leetcode.com/problems/binary-tree-right-side-view/
6. Number of Islands: https://leetcode.com/problems/number-of-islands/
7. All Nodes Distance K in Binary Tree: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
8. Boundary of Binary Tree: https://leetcode.com/problems/boundary-of-binary-tree

Pattern: Tree Depth First Search

Easy:

1. Same Tree: https://leetcode.com/problems/same-tree/
2. Path Sum: https://leetcode.com/problems/path-sum/
3. Diameter of Binary Tree: https://leetcode.com/problems/diameter-of-binary-tree/
4. Merge Two Binary Trees: https://leetcode.com/problems/merge-two-binary-trees/
5. Maximum Depth of Binary Tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/
6. Lowest Common Ancestor of a Binary Search Tree: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
7. Subtree of Another Tree: https://leetcode.com/problems/subtree-of-another-tree/
8. Invert Binary Tree: https://leetcode.com/problems/invert-binary-tree/

Medium:

1. Path Sum II: https://leetcode.com/problems/path-sum-ii/
2. Path Sum III: https://leetcode.com/problems/path-sum-iii/
3. Lowest Common Ancestor of a Binary Tree: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
4. Maximum Binary Tree: https://leetcode.com/problems/maximum-binary-tree/
5. Maximum Width of Binary Tree: https://leetcode.com/problems/maximum-width-of-binary-tree/
6. Construct Binary Tree from Preorder and Inorder Traversal: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
7. Validate Binary Search Tree: https://leetcode.com/problems/validate-binary-search-tree/
8. Kth Smallest Element in a BST: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Hard:

1. Binary Tree Maximum Path Sum: https://leetcode.com/problems/binary-tree-maximum-path-sum/
2. Serialize and Deserialize Binary Tree: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Pattern: Two Heaps

Hard:

1. Find Median from Data Stream: https://leetcode.com/problems/find-median-from-data-stream/
2. Sliding Window Median: https://leetcode.com/problems/sliding-window-median/
3. IPO: https://leetcode.com/problems/ipo/

Pattern: Backtracking

Easy:

1. Letter Case Permutation: https://leetcode.com/problems/letter-case-permutation/

Medium:

1. Subsets: https://leetcode.com/problems/subsets/
2. Subsets II: https://leetcode.com/problems/subsets-ii/
3. Permutations: https://leetcode.com/problems/permutations/
4. Permutations II: https://leetcode.com/problems/permutations-ii/
5. Combinations: https://leetcode.com/problems/combinations/
6. Combination Sum: https://leetcode.com/problems/combination-sum/
7. Combination Sum II: https://leetcode.com/problems/combination-sum-ii/
8. Combination Sum III: https://leetcode.com/problems/combination-sum-iii/
9. Generate Parentheses: https://leetcode.com/problems/generate-parentheses/
10. Target Sum: https://leetcode.com/problems/target-sum/
11. Palindrome Partitioning: https://leetcode.com/problems/palindrome-partitioning/
12. Letter Combinations of a Phone Number: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
13. Generalized Abbreviation: https://leetcode.com/problems/generalized-abbreviation/

Hard:

1. Sudoku Solver: https://leetcode.com/problems/sudoku-solver/
2. N-Queens: https://leetcode.com/problems/n-queens/

Pattern: Modified Binary Search

Easy:

1. Binary Search: https://leetcode.com/problems/binary-search/
2. Find Smallest Letter Greater Than Target: https://leetcode.com/problems/find-smallest-letter-greater-than-target/
3. Peak Index in a Mountain Array: https://leetcode.com/problems/peak-index-in-a-mountain-array/

Medium:

1. Find Peak Element: https://leetcode.com/problems/find-peak-element/
2. Search in Rotated Sorted Array: https://leetcode.com/problems/search-in-rotated-sorted-array/
3. Search in Rotated Sorted Array II: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
4. Search a 2D Matrix: https://leetcode.com/problems/search-a-2d-matrix/
5. Search a 2D Matrix II: https://leetcode.com/problems/search-a-2d-matrix-ii/

Hard:

1. Count of Range Sum: https://leetcode.com/problems/count-of-range-sum/

Pattern: Top 'K' Elements

Medium:

1. Kth Smallest Element in a BST: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
2. K Closest Points to Origin: https://leetcode.com/problems/k-closest-points-to-origin/
3. Top K Frequent Elements: https://leetcode.com/problems/top-k-frequent-elements/
4. Sort Characters By Frequency: https://leetcode.com/problems/sort-characters-by-frequency/
5. Kth Largest Element in an Array: https://leetcode.com/problems/kth-largest-element-in-an-array/
6. Find K Closest Elements: https://leetcode.com/problems/find-k-closest-elements/
7. Reorganize String: https://leetcode.com/problems/reorganize-string/

Hard:

1. Rearrange String k Distance Apart: https://leetcode.com/problems/rearrange-string-k-distance-apart
2. Course Schedule III: https://leetcode.com/problems/course-schedule-iii/
3. Maximum Frequency Stack: https://leetcode.com/problems/maximum-frequency-stack/

Pattern: K-Way Merge

Medium:

1. Kth Smallest Element in a Sorted Matrix: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
2. Find K Pairs with Smallest Sums: https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

Hard:

1. Merge k Sorted Lists: https://leetcode.com/problems/merge-k-sorted-lists/
2. Smallest Range Covering Elements from K Lists: https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/

Pattern : Dynamic Programming

Easy:

1. Climbing Stairs: https://leetcode.com/problems/climbing-stairs/
2. House Robber: https://leetcode.com/problems/house-robber/
3. Maximum Subarray: https://leetcode.com/problems/maximum-subarray/
4. Range Sum Query - Immutable: https://leetcode.com/problems/range-sum-query-immutable/

Medium:

1. Coin Change: https://leetcode.com/problems/coin-change/
2. Longest Increasing Subsequence: https://leetcode.com/problems/longest-increasing-subsequence/
3. Number of Longest Increasing Subsequence: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
4. Partition Equal Subset Sum: https://leetcode.com/problems/partition-equal-subset-sum/
5. Partition to K Equal Sum Subsets: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
6. Best Time to Buy and Sell Stock with Cooldown: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
7. Counting Bits: https://leetcode.com/problems/counting-bits/

Pattern: Topological Sort

Medium:

1. Course Schedule: https://leetcode.com/problems/course-schedule/
2. Course Schedule II: https://leetcode.com/problems/course-schedule-ii/
3. Minimum Height Trees: https://leetcode.com/problems/minimum-height-trees/

Hard:

1. Alien Dictionary: https://leetcode.com/problems/alien-dictionary
2. Sequence Reconstruction: https://leetcode.com/problems/sequence-reconstruction

Tips to Consider

If input array is sorted then
    - Binary search
    - Two pointers

If asked for all permutations/subsets then
    - Backtracking

If given a tree then
    - DFS
    - BFS

If given a graph then
    - DFS
    - BFS

If given a linked list then
    - Two pointers

If recursion is banned then
    - Stack

If asked for maximum/minumum subarray/subset/options then
    - Dynamic programming

If asked for top/least K items then
    - Heap

If asked for common strings then
    - Map
    - Trie

Else
    - Map/Set for O(1) time & O(n) space
    - Sort input for O(nlogn) time and O(1) space

Acknowledgements

This list is heavily inspired from Grokking the Coding Interview with additional problems extracted from the Blind 75 list and this medium article on 14 patterns to ace any coding interview question.