LeetCode: Starting Over NeetCode 150

Introduction

Join me on an adventure of transformation as I navigate the challenging yet rewarding path to mastering problem-solving skills through NeetCode. Whether you're preparing for coding interviews or looking to improve your programming abilities, I believe this structured approach to tackling 150 NeetCode problems is the key to success.

Why Start Over?

After reflecting on my previous attempts, I realized the need for a more organized approach. By categorizing problems and focusing on Data Structures and Algorithms (DSA), I can build a strong foundation and solve challenges more efficiently.

I came to this realization the hard way, while working through 28 Days "Leeter" Part 1 & Part 2 LeetCode problems. This led me to reassess my approach, and I decided to start over. You can read more about my approach solving LeetCode problems.

Categories and Patterns

By categorizing problems into specific problem-solving strategies and algorithms/patterns, it becomes easier to focus on mastering one type of problem at a time. Grouping them in this way leads to a more efficient and effective learning process.

• Understanding Time and Space Complexity
• Arrays & Hashing
• Two Pointers
• Sliding Window
• Stack
• Binary Search
• Backtracking
• Graphs
• Advanced Graphs
• 1-D Dynamic Programming
• 2-D Dynamic Programming
• Greedy
• Intervals
• Math & Geometry
• Bit Manipulation
• Importance of Repetition
• Reference

Understanding Time and Space Complexity

Before diving into the problems, it's essential to understand the concepts of time and space complexity. These concepts help evaluate the efficiency of algorithms and are crucial for optimizing solutions.

• Time Complexity: Refers to the amount of time an algorithm takes to complete as a function of the length of the input. Common notations include $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, and $O(n^2)$.

To understand Time Complexity, let's use a kitchen analogy:

• $O(1)$: Constant Time: The Fixed Task - You have a recipe that takes the same amount of time to prepare, regardless of how many servings $n$ you are making.
• $O(\log n)$: Logarithmic Time: The Efficient Search - You are searching for a specific ingredient in a well-organized Mise en Place. As the number of ingredients $n$ increases, the time it takes to find the ingredient increases logarithmically.
• $O(n)$: Linear Time: The One-by-One Task - You are preparing a meal for $n$ guests, and you need to chop vegetables for each guest. The time it takes increases linearly with the number of guests.
• $O(n \log n)$: Linearithmic Time: The Sorted Preparation - You are preparing a meal for $n$ guests, and you need to sort the ingredients before cooking. The time it takes increases in proportion to $n \log n$.
• $O(n^2)$: Quadratic Time: The Double Task - You are preparing a meal for $n$ guests, and for each guest, you need to prepare a dish that requires interaction with every other guest (like a potluck). The time it takes increases quadratically with the number of guests.

Here’s a quick reference table for common time complexities:

• Space Complexity: (memory usage), Refers to the amount of memory an algorithm uses in relation to the size of the input. Similar to time complexity, it is expressed using Big $O$ notation. Common notations include $O(1)$, $O(n)$, and $O(n^2)$. To understand Space Complexity, let's use the kitchen analogy:
• $O(1)$: Space (Constant) - You are cooking a meal, and no matter how many guests $n$ you have, you only need one big pot to cook the dish. The memory stove space remains the same regardless of the number of guests.
• $O(n)$: Space (Linear) - For every guest $n$, you need a separate plate. As the number of guests increases, the space needed grows linearly.
• $O(n^2)$: Space (Quadratic) - Like having a table with $n$ rows and $n$ columns of plates - as the number of dishes increases, the space needed grows quadratically.

Here's a quick reference table for common space complexities:

Arrays & Hashing

First up, Arrays & Hashing, check out my post on Arrays and Hashing with TypeScript for a brief outline of what they are and why we use them. You can also click the links below to go directly to the NeetCode problems and solutions that I have tackled so far.

• Contains Duplicate checks if there are any duplicates in an array. Use a Set $O(n)$ time, $O(n)$ space to track seen numbers. Looking through the mise en place to see if you've already prepped that ingredient.

• Valid Anagram determines if two strings are anagrams. Instead of sorting $O(n \log n)$, we use a frequency Map $O(n)$ time, $O(1)$ space to count character occurrences. Think of it as counting ingredients rather than alphabetizing them.

• Two Sum finds two numbers in an array that add up to a specific target. Use a Map $O(n)$ time, $O(n)$ space to remember "ingredients" (numbers) you've already seen so you don't have to look for them again. You can think of it as finding two ingredients that combine to make a specific dish.

• Group Anagrams groups anagrams together. Instead of sorting $O(n \cdot k \log k)$, we use a frequency array signature as a Map key to achieve optimal $(n \cdot k)$ time. Think of it as grouping mise en place by their "ingredient counts" rather than alphabetizing their labels.

• Top K Frequent Elements identifies the k most frequent elements in an array. Instead of sorting counts $O(n \log n)$ we use a Bucket Sort to achieve $O(n)$ time. Think of it as checking your order history to find the most used ingredients so you know what to buy in bulk.

• Encode and Decode Strings encodes a list of strings to a single string and decodes it back to the list.

• Product of Array Except Self: Calculates the product of all elements in the array except the current one for each element.

• Valid Sudoku: Validates whether a given Sudoku board configuration is valid.

Two Pointers

• Valid Palindrome
• Two Sum II
• 3Sum
• Container with Most Water
• Trapping Rain Water

Sliding Window

• Best Time to Buy & Sell Stock
• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Permutation in String
• Minimum Window Substring
• Sliding Window Maximum

Stack

• Valid Parentheses
• Min Stack
• Evaluate Reverse Polish Notation
• Generate Parentheses
• Daily Temperatures
• Car Fleet
• Largest Rectangle in Histogram

Binary Search

• Search a 2D Matrix
• Koko Eating Bananas
• Search Rotated Sorted Array
• Find Minimum in Rotated Sorted Array
• Time Based Key-Value Store
• Binary Search Find Median of Two Sorted Arrays

Backtracking

• Reverse Linked List
• Merge Two Linked Lists
• Reorder List
• Remove Nth Node from End of List
• Copy List with Random Pointer
• Add Two Numbers
• Linked List Cycle
• Find the Duplicate Number
• LRU Cache
• Merge K Sorted Lists
• Reverse Nodes in K-Group

Graphs

• Number of Islands
• Clone Graph
• Max Area of Island
• Pacific Atlantic Waterflow
• Surrounded Regions
• Rotting Oranges
• Walls and Gates
• Course Schedule
• Course Schedule II
• Redundant Connection
• Number of Connected Components in Graph
• Graph Valid Tree
• Word Ladder

Advanced Graphs

• Reconstruct Itinerary
• Min Cost to Connect all Points
• Network Delay Time
• Swim in Rising Water
• Alien Dictionary
• Cheapest Flights with K Stops

1-D Dynamic Programming

• Climbing Stairs
• Min Cost Climbing Stairs
• House Robber
• House Robber II
• Longest Palindroming Substring
• Palindrome Substrings
• Decode Ways
• Coin Change
• Maximum Product Subarray
• Word Break
• Longest Increasing Subsequence
• Partition Equal Subset Sum

2-D Dynamic Programming

• Unique Paths
• Longest Common Subsequence
• Best Time to Buy/Sell Stock With Cooldown
• Coin Change II
• Target SUm
• Interleaving String
• Longest Increasing Path in a Matrix
• Distinct Subsequences
• Edit Distance
• Burst Balloons
• Regular Expression Matching

Greedy

• Maximum Subarray
• Jump Game
• Jump Game II
• Gas Station
• Hand of Straights
• Merge Triplets to Form Target Triplet
• Partition Labels
• Valid Parenthesis String

Intervals

• Insert Interval
• Merge Intervals
• Non-Overlapping Intervals
• Meeting Rooms
• Meeting Rooms II
• Minimum Interval to Include Each Query

Math & Geometry

• Rotate Image
• Spiral Matrix
• Set Matrix Zeroes
• Happy Number
• Plus One
• Pow(x, n)
• Multiply Strings
• Detect Squares

Bit Manipulation

• Single Number
• Number of 1 Bits
• Counting Bits
• Reverse Bits
• Missing Number
• Sum of Two Integers
• Reverse Integer

Importance of Repetition

As highlighted in the NeeCode video on learning maths, and something that resonated with me (how I certainly learned maths), repetition plays a crucial role in reinforcing concepts and techniques. The same principle applies to learning coding problems. By repeatedly practicing various types of problems, you can achieve the following benefits:

Understanding Patterns: Recognizing common patterns and techniques used in solving problems.

Improving Efficiency: Developing the ability to solve problems more quickly and accurately.

Building Confidence: Gaining confidence in tackling new and complex problems by building a strong foundation.

This structured and repetitive approach ensures a comprehensive understanding and mastery over different types of LeetCode problems.

Reference

• google docs
• NeetCode.io/practice
• YT NC How I would learn Leetcode if I could start over

Photo by Lin Mei on Unsplash