shrutikp70/Leetcode-Patterns

A curated list of 160+ leetcode questions grouped by their common patterns

Leetcode Patterns

Table of Contents

• Background
• Preface
• Notes
• Question List
• Solutions
• Leetcode Discuss
• Tips to Consider
• Suggestions
• Acknowledgements

Background

This repo is intended for any individual wanting to improve their problem solving skills for software engineering interviews.

Problems are grouped under their respective subtopic, in order to focus on repeatedly applying common patterns rather than randomly tackling questions.

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
• Maps
• Linked Lists
• Queues
• Heaps
• Stacks
• Trees
• Graphs

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

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

Notes

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

Other useful methods to know include substring(), toCharArray(), Math.max(), Math.min(), and Arrays.fill().

Question List [website]

The entire question list can be found here: https://seanprashad.com/leetcode-patterns/.

In addition to viewing the question list, companies that have previously asked the question in the past 6 months (as of January 2020) will be listed. You can also use the checkboxes to mark which questions you've completed!

Question List [manual]

-Using the website above is the best option, I'm adding the list below just incase!

Arrays

Easy:

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

Medium:

1. Product of Array Except Self: https://leetcode.com/problems/product-of-array-except-self/
2. Find the Duplicate Number: https://leetcode.com/problems/find-the-duplicate-number/
3. 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/
2. Longest Consecutive Sequence: https://leetcode.com/problems/longest-consecutive-sequence/

Backtracking

The backtracking technique can be found under 10. Subsets here.

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. Partition to K Equal Sum Subsets: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
13. Letter Combinations of a Phone Number: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
14. 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/

Dynamic Programming

Dynamic programming guides can be found on topcoder and the Back To Back SWE YouTube channel.

Easy:

1. Climbing Stairs: https://leetcode.com/problems/climbing-stairs/
2. House Robber: https://leetcode.com/problems/house-robber/
3. Best Time to Buy and Sell Stock: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
4. Maximum Subarray: https://leetcode.com/problems/maximum-subarray/
5. Range Sum Query - Immutable: https://leetcode.com/problems/range-sum-query-immutable/

Medium:

1. House Robber II: https://leetcode.com/problems/house-robber-ii/
2. Coin Change: https://leetcode.com/problems/coin-change/
3. Maximum Product Subarray: https://leetcode.com/problems/maximum-product-subarray/
4. Longest Increasing Subsequence: https://leetcode.com/problems/longest-increasing-subsequence/
5. Longest Palindromic Substring: https://leetcode.com/problems/longest-palindromic-substring/
6. Word Break: https://leetcode.com/problems/word-break/
7. Combination Sum: https://leetcode.com/problems/combination-sum-iv/
8. Decode Ways: https://leetcode.com/problems/decode-ways/
9. Unique Paths: https://leetcode.com/problems/unique-paths/
10. Palindromic Substrings: https://leetcode.com/problems/palindromic-substrings/
11. Number of Longest Increasing Subsequence: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
12. Partition Equal Subset Sum: https://leetcode.com/problems/partition-equal-subset-sum/
13. Best Time to Buy and Sell Stock with Cooldown: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
14. Counting Bits: https://leetcode.com/problems/counting-bits/

Hard:

1. Longest Valid Parentheses: https://leetcode.com/problems/longest-valid-parentheses/

Fast & Slow Pointers

The fast & slow pointer approach can be found under 3. Fast and Slow pointers here.

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. Remove Nth Node From End Of List: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
4. Sort List: https://leetcode.com/problems/sort-list/
5. Reorder List: https://leetcode.com/problems/reorder-list/

Graph Traversals

Medium:

1. Clone Graph: https://leetcode.com/problems/clone-graph/
2. Course Schedule: https://leetcode.com/problems/course-schedule/
3. Pacific Atlantic Water Flow: https://leetcode.com/problems/pacific-atlantic-water-flow/
4. Number of Islands: https://leetcode.com/problems/number-of-islands/
5. Graph Valid Tree: https://leetcode.com/problems/graph-valid-tree/
6. Number of Connected Components in an Undirected Graph: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

In-place Reversal of a Linked List

The in-place reveral technique can be found under 6. In-place reversal of linked list here.

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/

K-Way Merge

The k-way merge technique can be found under 13. K-way Merge here.

Easy:

1. Merge Two Sorted Lists: https://leetcode.com/problems/merge-two-sorted-lists/

Hard:

1. Merge k Sorted Lists: https://leetcode.com/problems/merge-k-sorted-lists/

Matrices

Medium:

1. Set Matrix Zeroes: https://leetcode.com/problems/set-matrix-zeroes/
2. Spiral Matrix: https://leetcode.com/problems/spiral-matrix/
3. Rotate Image: https://leetcode.com/problems/rotate-image/
4. Word Search: https://leetcode.com/problems/word-search/
5. Kth Smallest Element in a Sorted Matrix: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

Intervals

The merge interval approach can be found under 4. Merge Intervals here.

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/

Modified Binary Search

The modified binary search algorithm can be found under 11. Modified binary search here.

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 Minimum in Rotated Sorted Array: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
2. Find Peak Element: https://leetcode.com/problems/find-peak-element/
3. Search in Rotated Sorted Array: https://leetcode.com/problems/search-in-rotated-sorted-array/
4. Search in Rotated Sorted Array II: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
5. Search a 2D Matrix: https://leetcode.com/problems/search-a-2d-matrix/
6. 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/

Sliding Window

The sliding window approach can be found under 1. Sliding Window here.

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/
5. Longest Substring Without Repeating Characters: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Hard:

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

Top 'K' Elements

The top K element technique can be found under 12. Top K elements here.

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/

Topological Sort

The topological sort algorithm can be found under 14. Topological sort here.

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

Tree Breadth First Search

The tree BFS technique can be found under 7. Tree BFS here.

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. All Nodes Distance K in Binary Tree: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
7. Boundary of Binary Tree: https://leetcode.com/problems/boundary-of-binary-tree

Tree Depth First Search

The tree DFS technique can be found under 8. Tree DFS here.

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/
9. Implement Trie (Prefix Tree): https://leetcode.com/problems/implement-trie-prefix-tree/

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/
3. Word Search II: https://leetcode.com/problems/word-search-ii/

Two Heaps

The two heaps approach can be found under 9. Two heaps here.

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/

Two Pointers

The two pointer approach can be found under 2. Two Pointers or Iterators here.

Easy:

1. Two Sum II - Input array is sorted: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
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/

Solutions

Solutions written in Java can be found in the solutions branch.

Leetcode Discuss

Leetcode discuss is an amazing resource and features previous interview questions, as well as compensation and general career advice.

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

Suggestions

Think a question should/shouldn't be included? Wish there was another feature? Feel free to open an issue with your suggestion!

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.