The Blind 75 Leetcode Series: The First Trimester Review

Photo by Chris Ried on Unsplash

We have gone through the first third of the blind 75 list. It’s a good time to review what we’ve done so far and techniques we’ve used. We also want to see if we can identify any relationship between type of problem and techniques we can use.

Referring back to this list, for the first 25 questions, I’ll list the link to each one of them:

1. Two Sum
2. Longest Substring Without Repeating Characters
3. Longest Palindromic Substring
4. Container With Most Water
5. 3Sum
6. Remove Nth Node From End of List
7. Valid Parentheses
8. Merge Two Sorted Lists
9. Merge k Sorted Lists
10. Search in Rotated Sorted Array
11. Combination Sum
12. Rotate Image
13. Group Anagrams
14. Maximum Subarray
15. Spiral Matrix
16. Jump Game
17. Merge Intervals
18. Insert Interval
19. Unique Paths
20. Climbing Stairs
21. Set Matrix Zeroes
22. Minimum Window Substring
23. Word Search
24. Decode Ways
25. Validate Binary Search Tree

Types of Problem

Then we look at the type of problems:

• Array/String:

- Two Sum
- Longest Substring Without Repeating Characters
- Longest Palindromic Substring
- Container With Most Water
- 3Sum
- Valid Parentheses
- Search in Rotated Sorted Array
- Combination Sum
- Rotate Image
- Group Anagrams
- Maximum Subarray
- Spiral Matrix
- Jump Game
- Merge Intervals
- Insert Interval
- Set Matrix Zeroes
- Minimum Window Substring
- Word Search
- Decode Ways

• Linked List:

- Remove Nth Node From End of List
- Merge Two Sorted Lists
- Merge k Sorted Lists

• Numbers/Math

- Unique Paths
- Climbing Stairs

• Tree

- Validate Binary Search Tree

As you can see, we have awful lot of array type of problem. Yet not every array problem is asking for similar things and we cannot simply use one technique to solve them. It’s better if we take a dive into what exactly these questions are asking for.

Types of Question Asks

• Sliding Window

- Longest Substring Without Repeating Characters
- Minimum Window Substring
- Maximum Subarray

• Math Calculation

- Two Sum
- 3 Sum
- Combination Sum
- Maximum Subarray
- Container With Most Water
- Jump Game
- Climbing Stairs

• String manipulation

- Longest Palindromic Substring
- Valid Parentheses
- Rotate Image
- Group Anagrams
- Spiral Matrix
- Unique Paths
- Set Matrix Zeroes
- Minimum Window Substring
- Decode Ways

• List Traversal & Merge

- Remove Nth Node From End of List
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Merge Intervals
- Insert Interval

• Search

- Search in Rotated Sorted Array
- Word Search

• Trees

- Validate Binary Search Tree

if we list out the techniques we use to solve these problems to find a better relationship between problem types and solution. If you remember, we used several different ways to solve for a lot of problems, so you will see some repeated problems in the lists below.

Techniques

• Two-pointers:

- Two Sum
- Longest Palindromic Substring
- Container With Most Water
- 3 Sum
- Remove Nth Node From End of List

• Hash Map

- Two Sum
- Longest Substring Without Repeating Characters
- Group Anagrams
- Minimum Window Substring

• Dynamic Programming

- Longest Palindromic Substring
- Combination Sum
- Maximum Subarray
- Jump Game
- Unique Paths
- Climbing Stairs
- Decode Ways

• Stack

- Valid Parentheses
- Merge Intervals
- Insert Interval

• Recursion

- Merge Two Sorted Lists
- Search in Rotated Sorted Array
- Combination Sum
- Decode Ways

• Priority Queue (heap)

- Merge k Sorted Lists

• Divide & Conquer

- Merge k Sorted Lists
- Maximum Subarray

• Binary Search

- Search in Rotated Sorted Array

• Matrix

- Rotate Image
- Spiral Matrix
- Unique Paths
- Set Matrix Zeroes
- Word Search

• Backtracking

- Word Search

• Tree Traversal

- Validate Binary Search Tree

To be honest, no relationship stands out right away, but after looking into it, you can see that

1. sliding window problem requires some sort of two-pointer (since it’s constantly moving and we need to keep track of the window)
2. maze type of problem requires backtracking
3. When something requires “building up from simpler, smaller problems”, it probably uses dynamic programming
4. If you need to track something, whether it’s the location of certain element, the count of some letters, or existence of certain element, use a hash table (dict) to keep track of it
5. If there are multiple elements that require operations and you realize you can do 2 of them at a time, it’s possible you can use a divide and conquer method

As we reach the 1/3 benchmark, it’s a good time to go back and review what we have done so far. Practice makes perfect, and practice takes several goes before we can master a problem.

Next time, we will continue with the next problem: 100. Same Tree

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz