a place for interesting concepts
sun
Going through the Leetcode Blind 75 Challenge
October 2nd, 2023 - By Gavin Machetes

This is the famous list of the Blind 75 Leetcode problems. Here is every problem in the set:


Array

Binary

Dynamic Programming

Graph

Interval

Linked List

Matrix

String

Tree

Heap


Two Sum

Took 8 minutes for an accepted solution. My first solution was a two-pointer method. I tripped up on my first submission because I let p2 == p1 instead of p2 >= p1. I incorrectly thought it was O(nlogn) but turns out its the same as brute force O(n^2). The best solution involves creating a hashmap which stores the complement needed for the current index. It'll always return in increasing order because it passes from left to right. Best solution is O(n) time.

Maximum Stock Profit

Took 4 minutes for the brute force solution. I couldn't think of a one-pass solution. I was going into the thinking of using hashmaps but it turned out to be the wrong answer. Gave up and saw the solution at the 17 minute mark. The optimal O(n) solution is to keep track of the minPrice and maxDiff. It's actually so simple.

Contains Duplicate

It took me about 30 minutes to solve the problem. The first 10 minutes were spent understanding the problem statement and figuring out the best approach. The remaining time was used to write and test the code. When I first read the problem, it seemed straightforward. The challenge was to determine if any value appears at least twice in an array, which is a common task in programming. I felt confident that I could solve it using basic concepts I had learned in my data structures class. My initial thought was to use a hash set to track the elements I had already seen. The idea was simple: iterate through the array, and for each element, check if it's already in the set. If it is, then we have a duplicate. Otherwise, add the element to the set. The main difficulty I encountered was handling edge cases. For example, I had to consider what would happen if the array was empty or had only one element. I also needed to think about the performance of my solution. I realized that using a hash set would give me an O(n) time complexity, which was efficient for this problem. Writing the code was pretty straightforward. However, I did run into a couple of bugs . One was a typo where I used the wrong variable name. Another issue wasn't properly initializing my hash set, which led to a null pointer exception. Debugging these issues didn't take too long, and it was a good reminder to pay attention to details.

Product of Array Except Self

It took me around an hour to solve it. I spent about 20 minutes understanding the problem statement and constraints, especially the part about not using division and achieving a linear time complexity. I decided to approach the problem using two arrays to represent the products of all the elements to the left and right of each index. The main difficulty was figuring out how to do this efficiently without extra space, which was part of the problem's constraints. After some thought, I realized I could use the output array for one of these purposes and then use a variable to track the other. Writing the code was confusing, especially when trying to correctly initialize the products and update them in a single pass. I encountered a few bugs related to incorrect indexing and updating the product values. These issues were primarily due to overlooking how the product of the left and right elements should be accumulated and combined. Debugging them helped me better understand array manipulation and the importance of carefully considering how variables are updated within loops. Despite the challenges, solving this problem was quite rewarding. It pushed me to think beyond the conventional solutions and make it better both space and time complexity.

Maximum Subarray

It took me approximately 45 minutes to come up with a working solution. In the beginning, I spent about 15 minutes just understanding the problem and its implications. The challenge was to find the contiguous subarray within an array which has the largest sum. I thought about using a brute force approach to check all possible subarrays, but I quickly realized that it would be inefficient. The real breakthrough came when I read about the Kadane's Algorithm, which elegantly solves the problem in O(n) time by iterating through the array and keeping track of the maximum sum subarray found so far. Implementing the algorithm was challenging because it was a new concept to me. I struggled with the logic of when to reset the sum of the current subarray. I made a few mistakes, like not properly handling negative numbers and forgetting to update the maximum sum under certain conditions. Debugging these issues was a bit frustrating but incredibly educational. I learned not only a new algorithm but also the importance of considering edge cases in array processing problems.

Maximum Product Subarray

It took around an hour and a half to solve. The challenge was to find the contiguous subarray within an array that has the largest product, which was a step up in complexity compared to the Maximum Subarray problem. I spent a considerable amount of time understanding how the product could change drastically with the inclusion of a negative number. The key realization was that the maximum product could turn into a minimum product with the multiplication of a negative number, and vice versa. Implementing a solution that kept track of both the maximum and minimum products at each step was tricky. I had to carefully think about how to update these values, especially when encountering a negative number. Debugging the solution took a while, as I had to test various edge cases, like arrays with all negative numbers or zeros.

Find Minimum in Rotated Sorted Array

It took me about 40 minutes to solve. This problem involved a sorted array that had been rotated, and the task was to find the minimum element. At first, I was a bit confused about how to apply binary search in this context. The challenge was to figure out which part of the array to discard at each step. I encountered some difficulties in correctly identifying the condition to narrow down the search space. There were a few bugs at first, mainly due to incorrect assumptions about the sorted order in the rotated array. After several test runs and debugging sessions, I finally got a grasp on how to modify the binary search to suit this unique situation.

Search in Rotated Sorted Array

This was a challenging extension of binary search problems for me. It took me around an hour to figure out a solution. This problem required me to find a target value in a sorted array that had been rotated. The initial task was to understand how the rotation affected the usual binary search algorithm. I had to modify the binary search conditions to account for the rotation. The main difficulty was determining which part of the array to focus on during each step of the search - whether it was the normally ordered part or the rotated part. I encountered a few logical errors especially in handling edge cases where the target was at the point of rotation. Debugging these issues helped me better understand the intricacies of binary search.

3 Sum

It took me roughly an hour to solve. The task was to find all unique triplets in the array which give the sum of zero. the problem seemed daunting due to its potential complexity. I spent the first part of my time understanding the problem and brainstorming various approaches. I realized that a brute force solution would be too inefficient, so I decided to try a two-pointer approach after sorting the array. The sorting made it easier to avoid duplicates and navigate the array efficiently. Implementing this logic, however, wasn't straightforward. I faced difficulties in correctly moving the pointers and avoiding duplicate triplets. There were several off-by-one errors and issues with handling edge cases. Debugging these issues was a bit tedious but highly educational. Solving this problem not only improved my understanding of two-pointer techniques but also sharpened my skills in handling array manipulation and edge cases.

Container With Most Water

It took me about 45 minutes to solve. The problem required finding two lines that together with the x-axis form a container, such that the container contains the most water. My initial thought was to use a brute force approach to check every pair of lines, but I quickly realized that this would be too time-consuming. The breakthrough came when I learned about the two-pointer approach. The challenge was to figure out how to move the pointers - whether to move the left pointer, the right pointer, or both. I had a few bugs especially in correctly identifying the conditions to move the pointers. These bugs were primarily due to a misunderstanding of how moving the pointers affected the area of the water container. Debugging them helped me better understand the relationship between the width of the container and the height of the lines.

Maximum Depth of Binary Tree

Took about 30 minutes. This problem asked to find the maximum depth of a binary tree, which is a fundamental task in understanding tree-based data structures. I approached this problem using recursion, which seemed like a natural fit for tree traversal. The main challenge was to ensure that the recursion correctly computed the depth at each node and handled edge cases, such as an empty tree. I encountered a few minor bugs related to the base case of the recursion, but these were quickly resolved. This problem reinforced my understanding of recursive algorithms and how they can be elegantly applied to tree data structures.

Same Tree

I decided to use a recursive approach, comparing each node of the two trees. The primary difficulty I faced was ensuring that both structure and node values were identical. At first, I missed cases where the trees had the same structure but different node values. I had to refine my base cases for null nodes, as my initial code didn't correctly handle cases where one tree was a subtree of the other. It took several debugging iterations to get these conditions right, which was a great exercise in understanding tree traversal and comparison.

Invert/Flip Binary Tree

My approach was to perform a recursive traversal and swap children at each node. However, I made the mistake of creating new nodes instead of swapping the existing ones, which led to incorrect tree structures and memory leaks. Correcting this involved understanding how pointers and object references work in trees. Another issue I encountered was failing to handle leaf nodes correctly, which caused incorrect inversions and, in some cases, recursion errors. The problem took me about an hour to solve and was a practical lesson in tree manipulation and recursive algorithms.

Binary Tree Maximum Path Sum

I employed a depth-first search strategy, but the difficulty lay in handling negative values and deciding when to include or exclude a node from the sum. A significant issue in my initial implementation was handling paths that only included negative node values, leading to incorrect calculations. I also struggled with ensuring that the path was continuous and didn't branch off at each node. After several debugging sessions and refining the logic for path calculations, especially around negative values and node inclusion, I managed to solve the problem. It was a demanding but rewarding experience that took about an hour and a half, significantly improving my understanding of tree-based algorithms and dynamic programming.

Binary Tree Level Order Traversal

Solving this one took me about 35 minutes. This problem involved traversing a binary tree level by level and recording the values at each level. The main challenge was implementing a queue to facilitate level order traversal. I struggled with the logic of processing each level separately and had issues with prematurely advancing to the next level, which mixed up the values. After a few trial and error attempts, I managed to get the queue implementation right and properly separated the values of each level.

Serialize and Deserialize Binary Tree

This one took me around an hour to solve. This task required converting a binary tree into a string format and then reconstructing the tree from that string. The serialization part was straightforward, where I used a pre-order traversal to record node values. However, the deserialization part was more challenging. I faced difficulties in maintaining the correct position in the string while reconstructing the tree, especially when dealing with null markers for missing nodes. I also encountered a bug related to handling empty trees. After refining the parsing logic and ensuring that the tree structure was accurately maintained, I was able to deserialize the tree.

Subtree of Another Tree

This problem was a bit complex, taking me approximately 50 minutes to solve. The problem required checking whether one binary tree was a subtree of another. My approach involved two main tasks: traversing the larger tree to find a node that matches the root of the smaller tree, and then comparing the subtree from that node with the smaller tree for an exact match. The primary issue I faced was in the comparison function, where I didn't account for the case where both nodes being compared were null, leading to false negatives. I had to make it better the traversal of the larger tree to avoid unnecessary comparisons, which was causing time limit exceed errors. Fine-tuning the tree comparison logic and optimizing the traversal were key to solving this problem.

Construct Binary Tree from Preorder and Inorder Traversal

This one took me around 1 hour and 15 minutes. The task was to reconstruct a binary tree from its preorder and inorder traversal lists. The main difficulty lay in correctly identifying the root node and its left and right subtrees from the traversal lists. I struggled with dividing the inorder list into left and right subtrees based on the root identified in the preorder list. Misinterpretation of indices led to incorrect tree construction, especially for trees with a deep nested structure. Another issue was handling duplicate values in the tree. After carefully mapping the indices between the preorder and inorder lists and ensuring the correct subtree boundaries, I managed to reconstruct the binary tree accurately.

Validate Binary Search Tree

Took me approximately 45 minutes. Goal was to determine if a binary tree is a valid binary search tree (BST). I chose to use a recursive approach to validate each node against its permissible value range. I encountered issues with setting the correct boundaries for the left and right subtrees, particularly in dealing with the maximum and minimum values of integers. There were also problems with handling BSTs with duplicate values, which my initial solution didn't correctly account for. After adjusting the boundary conditions and ensuring that the value range was correctly updated at each step of the recursion, I was able to validate the BST correctly.

Kth Smallest Element in a BST

This took me around 40 minutes to solve on LeetCode. This problem required finding the kth smallest element in a binary search tree. I used an in-order traversal approach, as it naturally processes the elements of a BST in sorted order. The challenge was to efficiently find the kth element without traversing the entire tree. I made a mistake in the termination condition of the traversal, which led to excessive processing. I also faced difficulties in maintaining the count of processed nodes, especially when backtracking up the tree. After refining the traversal logic and ensuring the count was accurately maintained, I was able to find the kth smallest element.

Lowest Common Ancestor of BST

Solving the "Lowest Common Ancestor of BST" problem on LeetCode took me about 30 minutes. The goal was to find the lowest common ancestor (LCA) of two nodes in a binary search tree. I approached this using the BST property, which dictates that all left descendants are less than the node, and right descendants are greater. My initial challenge was handling the edge cases, particularly when one of the target nodes was the ancestor of the other. I mistakenly returned the first node I encountered, which was incorrect in some cases. After adjusting my approach to properly compare the values of the nodes with the target nodes and considering the BST properties, I managed to find the LCA accurately.

Implement Trie (Prefix Tree)

This one was a lengthy, taking around 1 hour. The problem required constructing a trie data structure to efficiently insert and search for words. The main difficulty was designing the trie node structure and correctly implementing the insert, search, and startsWith methods. I had issues with the search function, particularly in handling cases where a word was a prefix of another word but not a word itself. I also struggled with optimizing the node structure to handle large sets of words without consuming excessive memory. After several iterations and debugging sessions to refine the node structure and ensure the correct logic in the trie methods, I successfully implemented the trie.

Add and Search Word

This one involved designing a data structure that supports adding new words and finding if a string matches any previously added word, took me about 50 minutes to complete. Implementing the add function was straightforward, but the search function, especially with the presence of wildcard characters, was challenging. My initial approach failed to correctly handle wildcards, leading to incorrect matches. I resolved this by implementing a recursive search function to explore all possible matches for wildcard characters. Fine-tuning this recursive logic and ensuring efficient performance was the most time-consuming part of the problem.

Word Search II

Solving "Word Search II" was a complex task and took me approximately 1 hour and 20 minutes. This problem required finding all words from a given list that can be formed by a sequence of adjacent letters on a board. The primary challenge was optimizing the search to prevent timeouts on large boards and long word lists. The initial brute-force solution, which searched for each word separately, was inefficient. After that, I implemented a trie to store the words and used backtracking to search the board. Optimizing the backtracking to avoid unnecessary searches and managing the state of the board during recursion were the main hurdles I faced. After fine-tuning the trie implementation and the backtracking algorithm, I was able to solve the problem.

Merge K Sorted Lists

This one took me about 1 hour to solve. The task was to merge k sorted linked lists into one sorted list. I tried a brute-force approach by merging lists one by one, but it was inefficient for a large number of lists. After that, I switched to using a min-heap to efficiently find the smallest element among the lists' heads. Implementing the heap was straightforward, but correctly managing the lists' heads and ensuring that empty lists were handled properly posed some difficulties. After adjusting the heap insertion and extraction logic to correctly update the lists and handle edge cases, I managed to achieve an efficient and correct solution.

Top K Frequent Elements

This one on LeetCode took me approximately 40 minutes to solve. The challenge was to find the k most frequent elements in an array. I started by using a hash map to count the frequency of each element, which was straightforward. However, the difficulty arose in efficiently sorting these elements by their frequency. My initial attempt with a simple sort exceeded the time limit for large datasets. After that, I realized the utility of a min-heap for maintaining the top k elements, which significantly improved the efficiency. The main hurdle was correctly implementing the heap and ensuring it only contained k elements at any time, which required careful consideration of the heap's size and elements.

Find Median from Data Stream

Took me about 1 hour and 10 minutes. The task was to design a data structure that supports adding numbers from a data stream and retrieving the median efficiently. My initial design, using a simple list to store the numbers and sorting it to find the median, was too slow. After that, I implemented a two-heap approach, using a max-heap for the lower half of the numbers and a min-heap for the upper half, balancing the two heaps for every addition. The main challenge was maintaining the heaps in a way that allows constant time retrieval of the median. Ensuring that the heaps were balanced after each insertion and handling edge cases, like when the number of elements is even, required several iterations and debugging.

Merge K Sorted Lists

Took me around 1 hour to complete. The goal was to merge multiple sorted linked lists into a single sorted list. I attempted to merge lists one by one, but this approach was inefficient and led to a time-out error on large inputs. To make it better, I used a min-heap to keep track of the smallest elements from each list. The implementation of the heap was straightforward, but properly managing the linked list pointers and handling edge cases, such as empty lists, was challenging. After refining the heap operations and ensuring that the merged list was correctly formed, I achieved an efficient solution.

Top K Frequent Elements

I actually remember doing this problem before, and this time it took me around 35 minutes, slightly less than before. The process was similar: using a hash map to count element frequencies and then a min-heap to extract the top k frequent elements. Having solved it before, I was more familiar with the heap operations, but ensuring that the heap was correctly updated and maintained its size constraint still required careful attention. The repeat of this problem reinforced the importance of choosing the right data structure for efficiency.

Find Median from Data Stream

This one I already did before and I solved it in about 1 hour, a bit quicker than my first attempt. The approach remained the same: using two heaps to balance the lower and upper halves of the data stream. This time, however, I was more efficient in handling the balancing of the heaps and ensuring that the median retrieval was make it betterd. The repeated attempt at this problem allowed me to refine my understanding of heap operations and the intricacies involved in maintaining a dynamic median.

Sum of Two Integers

Took me about 45 minutes to solve. The task was to calculate the sum of two integers without using the '+' or '-' operators, which meant I had to delve into bitwise operations. The primary hurdle was understanding and correctly implementing the bit manipulation techniques, like the use of XOR and AND operations to simulate addition. I struggled with the concept of carrying bits and repeatedly encountered issues with infinite loops due to incorrect carry handling. After carefully refining the bitwise operations and ensuring the carry was properly applied and shifted, I successfully solved the problem, gaining a deeper appreciation for low-level arithmetic operations.

Number of 1 Bits

Took me around 20 minutes. The problem required counting the number of '1' bits in a binary representation of an integer. I implemented a straightforward approach using a loop to check each bit, but I encountered issues with negative numbers due to the signed integer representation in binary. After switching to an unsigned representation and using a bit manipulation trick to isolate each bit, the solution worked correctly, providing valuable insights into binary representations and bit manipulation. This one is basically finding the "Hamming" weight.

Counting Bits

Took me about 30 minutes to complete. My initial approach was to use a simple loop with a bit count function for each number, similar to the "Number of 1 Bits" problem. However, this approach wasn't efficient enough for larger inputs. After that, I discovered a dynamic programming approach that built upon the counts of previous numbers, significantly optimizing the computation. Implementing this dynamic approach required careful consideration of the binary relationships between numbers, particularly how the count of '1' bits changes with each increment.

Missing Number

Took me about 25 minutes. The challenge was to find the missing number in a sequence of integers. I first thought of using a sorting approach, but realized it would be inefficient. Instead, I used the XOR operation, leveraging its properties to cancel out pairs of identical numbers. The main issue I faced was correctly initializing and iterating through the sequence to XOR all the numbers along with their indices. After resolving a few off-by-one errors in the iteration, the XOR approach successfully revealed the missing number, offering a great example of the practical use of bitwise operations.

Reverse Bits

Took me about 35 minutes. This problem required a bit-by-bit reversal of the binary representation. My initial attempt involved shifting bits and using the OR operation to construct the reversed number. I faced challenges with aligning the bits correctly, especially with leading zeros. I also encountered an issue with handling 32-bit integers, as I didn't account for all 32 bits in the reversal process. Adjusting the bit manipulation logic and ensuring that each bit was correctly positioned in the reversed integer was crucial to solving the problem. It was a practical exercise in understanding binary representations and bitwise operations.

Climbing Stairs

Took me around 20 minutes. I considered a recursive approach but quickly realized it was inefficient due to repeated calculations. The main challenge was optimizing the solution with dynamic programming. I struggled with correctly setting up the base cases for the first two steps. After refining the dynamic programming array and ensuring the proper iterative calculation of the number of ways for each step, the solution became efficient and passed all test cases.

Coin Change

This one took me about 1 hour to solve. I started with a greedy approach but found it didn't work for all test cases due to the variations in coin denominations. The key challenge was implementing a dynamic programming solution that correctly handled unattainable amounts and minimized the coin count. I faced difficulties in setting up the array to store minimum counts for each amount and ensuring it handled cases where no combination of coins fit the target amount. After several iterations to handle these edge cases, the dynamic programming solution worked correctly.

Longest Increasing Subsequence

Took me about 45 minutes. The goal was to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. My initial brute-force solution was inefficient. The major hurdle was optimizing it with dynamic programming. I struggled with the logic of updating the length of the longest subsequence at each step. Refining the dynamic programming array to correctly track the subsequence lengths and iterating efficiently through the sequence to update these lengths were the critical steps in solving the problem.

Longest Common Subsequence

Took me about 1 hour and 10 minutes. The challenge was implementing a dynamic programming approach to efficiently compute the length of the common subsequence. I had trouble understanding how to construct the dynamic programming table and how to backtrack to construct the actual subsequence. I had issues with correctly initializing the table and dealing with edge cases, such as empty strings. After carefully setting up the table and refining the logic for comparing characters and updating lengths, the solution worked effectively.

Word Break Problem

Took me around 50 minutes to complete. The problem required determining if a string could be segmented into a space-separated sequence of one or more dictionary words. My initial attempt with a recursive solution led to timeouts due to repeated calculations. The main challenge was optimizing the solution using dynamic programming. I had difficulties in setting up the dynamic programming array to correctly represent whether a substring can be formed from the dictionary. Adjusting the logic to check substrings against the dictionary words and handling cases where a word could be part of a larger unbreakable substring were key to solving this problem.

Combination Sum

Took me about 50 minutes to solve. My initial approach was to use a recursive solution to explore all possible combinations, but I struggled with avoiding duplicates and efficiently handling the recursion. The main challenge was implementing a backtracking solution that systematically explored possible combinations while avoiding repetitions. I faced difficulties in correctly pruning the search space to reduce unnecessary calculations and in ensuring that the combinations were added correctly without missing any valid sets.

House Robber

Took me about 30 minutes. This problem required figuring out the maximum amount of money that can be robbed from a series of houses, with the constraint that adjacent houses cannot be robbed. The challenge was to use dynamic programming to make it better the solution. I struggled with setting up the recurrence relation to calculate the maximum money that can be robbed up to each house. My first few attempts resulted in incorrect calculations, especially for edge cases involving small arrays of houses. After refining the dynamic programming array to correctly consider whether to rob each house, the solution became efficient and correct.

House Robber II

Took me around 40 minutes to complete. The added complexity was that the first and last houses were now adjacent. I had to modify my original House Robber solution to handle this circular arrangement. The main issue was correctly dealing with the circular constraint, which required running two separate dynamic programming passes - one excluding the first house and the other excluding the last house. Combining these two solutions to find the optimal robbery plan was the key to solving this problem.

Decode Ways

Took me about 45 minutes. The challenge was to handle various edge cases, such as zeros and numbers greater than 26 that don't correspond to any letter. I faced difficulties with strings containing zeros, which I mistakenly counted as valid decodings. I also struggled with setting up the dynamic programming solution to efficiently handle consecutive digits. Refining the logic to accurately count valid decodings, especially for cases involving zeros and large numbers, was crucial to solving the problem.

Unique Paths

Took me around 25 minutes to solve. My approach was to use a dynamic programming solution to count the paths. The main challenge was correctly initializing the grid and ensuring that the number of paths was accumulated correctly at each cell. I encountered an issue with cells on the boundaries, which only have one path leading to them. After adjusting the initialization of the first row and column, the dynamic programming solution worked efficiently to calculate the total number of unique paths.

Jump Game

This one was actually hard, but took me around 40 minutes to solve. The problem required determining if it's possible to reach the last index of an array where each element represents the maximum jump length at that position. I attempted a recursive approach, but quickly realized it led to a time complexity issue, especially for large arrays. The main challenge then became optimizing the solution with a greedy algorithm. I struggled with the logic of tracking the farthest reachable index at each step. My early attempts either underestimated or overestimated this reach, leading to incorrect conclusions about the possibility of reaching the end. After several trial-and-error iterations and carefully adjusting the conditions for updating the farthest reachable index, I successfully implemented an efficient greedy solution that passed all the test cases. This problem was a valuable lesson in the practical application of greedy algorithms for optimization problems.

Clone Graph

Took me around 50 minutes. The task was to clone a graph, which involved creating a deep copy of a graph structure represented by nodes and edges. The main difficulty I encountered was in correctly cloning the connections between nodes without creating duplicates. I made a mistake by not keeping track of the nodes already cloned, leading to duplicate nodes and incorrect graph structure. After that, I implemented a hash map to map original nodes to their clones, ensuring that each node was only cloned once. Managing the references and avoiding cyclic issues was challenging but crucial in successfully cloning the graph.

Course Schedule

This one took me about 1 hour to solve. The challenge was to implement a graph and perform a topological sort. My initial approach using depth-first search (DFS) struggled with correctly identifying cycles, particularly in more complex graphs with multiple dependencies. After refining the DFS algorithm and implementing a mechanism to track visited nodes and recursion stack, I managed to detect cycles accurately, which was key to solving the problem.

Pacific Atlantic Water Flow

Took me approximately 1 hour and 15 minutes. This problem required a careful implementation of depth-first search from the ocean's borders inward. The primary challenge was handling the edge cases and ensuring the DFS traversal was correctly implemented to account for the matrix's varying heights. I faced issues with the boundaries and corner cases where water flow wasn't correctly calculated. After several iterations to refine the traversal logic and correctly mark reachable cells, I successfully identified all valid cells.

Number of Islands

Took me around 35 minutes. The task was to count the number of islands in a given grid, represented by '1's (land) and '0's (water). I chose to use a depth-first search to traverse the grid and mark visited land. The main difficulty was in ensuring that all adjacent lands were correctly marked as part of the same island and not counted multiple times. I missed marking certain cells during the DFS, leading to an overcount of islands. After debugging and ensuring comprehensive marking of adjacent lands, the DFS approach accurately counted the number of islands.

Longest Consecutive Sequence

Took me about 45 minutes to complete. My initial brute force solution was inefficient due to sorting. After that, I opted for a hash set to track the elements and check for consecutive numbers. The challenge was efficiently iterating through the array and checking for consecutive numbers without missing any potential sequences. I faced difficulties in handling duplicates and ensuring that each sequence was only counted once from its lowest number. After refining the logic to start sequences only from numbers that were the start of a sequence, the solution worked efficiently.

Alien Dictionary (Leetcode Premium)

Took me about 1 hour, involved deciphering an unknown language's lexicographical order from a list of words. The challenge was to construct a graph representing the precedence of characters and then perform a topological sort. My initial difficulty was in correctly constructing the graph, especially in handling edge cases where one word is a prefix of another. This led to incorrect ordering in my first few attempts. detecting cycles in the graph to avoid invalid dictionaries was a tricky part that required careful implementation of depth-first search.

Graph Valid Tree (Leetcode Premium)

Took me around 40 minutes to complete. The main challenge was to ensure that the graph is connected and acyclic. I started with a depth-first search to check for cycles but missed considering disconnected components. This oversight led to false positives in cases of multiple disconnected subgraphs. After implementing a mechanism to check for connectedness alongside the cycle check, the solution correctly identified valid trees.

Number of Connected Components in an Undirected Graph (Leetcode Premium)

This one was about 50 minutes. The task was to count the number of connected components in an undirected graph. I used depth-first search to explore the graph, but struggled with correctly marking visited nodes, leading to overcounting components. The key was to refine the DFS implementation to accurately traverse and mark all nodes in each component before moving to the next unvisited node, ensuring each component was counted exactly once.

Insert Interval

Took me around 30 minutes. This involved inserting a new interval into a list of non-overlapping intervals and merging any overlapping intervals. The challenge was to efficiently find the correct position for the new interval and handle overlaps. I had difficulty with edge cases where the new interval extended beyond multiple existing intervals. Adjusting the logic to merge overlapping intervals correctly and maintaining the sorted order of the list was crucial in solving this problem.

Merge Intervals

Took me about 35 minutes to complete. The main challenge was to sort the intervals correctly and then merge overlapping ones efficiently. My initial implementation struggled with correctly handling intervals that were completely inside another interval. After refining the merging logic to account for various types of overlaps and ensuring a comprehensive merge of intervals, the solution worked effectively and passed all test cases.

Non-overlapping Intervals

Took me around 45 minutes. The goal was to find the minimum number of intervals to remove to make the rest non-overlapping. The key challenge was to devise a greedy approach that efficiently determined which intervals to remove. I struggled with the logic of selecting which intervals to remove - specifically, whether to remove longer intervals or those with later start times. After implementing a sorting mechanism based on the end times of intervals and carefully handling overlapping cases, I managed to find the optimal set of intervals to remove, achieving the desired non-overlapping arrangement.

Meeting Rooms (Leetcode Premium)

This one took me about 25 minutes to solve. The main task was to determine if any intervals overlapped. I approached this by sorting the intervals based on start times and then checking for overlaps between consecutive intervals. My initial sort implementation had a flaw in handling edge cases where intervals had the same start time but different end times. After refining the sorting criteria and ensuring a proper comparison between consecutive intervals, the solution effectively determined the feasibility of attending all meetings.

Meeting Rooms II (Leetcode Premium)

Took me around 50 minutes. This problem required a more complex approach than the first Meeting Rooms problem. I used a min-heap to track ongoing meetings by their end times. The main challenge was efficiently managing the heap to reflect the rooms in use and determining when a new room was needed. I miscalculated the room requirements due to incorrect heap updates. After adjusting the logic to correctly update the heap based on meeting start and end times, the solution accurately calculated the minimum number of rooms required.

Reverse a Linked List

Took me about 5 minutes to solve. The task was to reverse the links in a singly linked list. I faced difficulties with correctly reassigning the next pointers without losing access to the rest of the list. I also had to handle the edge cases of an empty list or a list with a single node. After implementing a careful iterative approach to swap the next pointers and maintain a reference to the remainder of the list, I successfully reversed the list without losing any nodes.

Detect Cycle in a Linked List

This one's a classic problem that you either know or you don't. It took me about 5 minutes to solve. The challenge was to identify a cycle in the list without using extra space. The trick is to use Floyd's Tortoise and Hare algorithm, where two pointers move at different speeds. The main difficulty was in correctly implementing the pointers' movement and identifying the exact conditions under which they meet, indicating a cycle. I had issues with properly handling the edge cases, like an empty list or a list with only one node, but after fine-tuning the pointer increments and the loop conditions, I successfully detected cycles in various scenarios.

Merge Two Sorted Lists

Took me about 7 minutes. The goal was to combine two sorted linked lists into a single sorted list. The primary challenge was to efficiently merge the lists while maintaining their sorted order. I struggled with handling the tail ends of the lists, especially when one list was longer than the other. After implementing a recursive approach that merged the lists node by node, ensuring that the smaller node always got linked first, I was able to create a correctly merged and sorted list.

Merge K Sorted Lists

Took me around 1 hour to complete. The key to solving this problem was efficiently finding the smallest node at each step. I tried merging lists pair by pair but realized it was inefficient. Then, I implemented a min-heap to keep track of the smallest node among the list heads. The main challenge was managing the heap and updating the linked list pointers correctly. After refining the heap operations and ensuring the merged list was correctly constructed, the solution worked for various test cases.

Remove Nth Node From End Of List

Took me about 25 minutes. This problem required calculating the length of the list and then removing the specific node. The main difficulty was in handling edge cases, such as removing the head of the list. I used two-pointer technique, with one pointer starting ahead by N steps. Aligning the pointers correctly and ensuring that the previous node was linked correctly after removal were crucial steps in solving this problem.

Reorder List

Took me around 40 minutes to figure out. The problem required reversing the second half of the list and then merging it with the first half. The challenge was in correctly splitting the list, reversing the second half, and then merging them back. I struggled with the merge process, especially in maintaining the correct order without breaking the list. After carefully implementing the list splitting and reverse merging processes, the reordered list matched the expected pattern.

Set Matrix Zeroes

I solved in about 35 minutes. The main challenge was doing this in-place without using extra space for storage. My initial approach mistakenly altered rows and columns prematurely, affecting the determination of which rows and columns should be zeroed. After that, I make it betterd the solution by first marking the first row and column as flags to store which rows and columns should be set to zero, and then using these flags to update the matrix, carefully handling the first row and column themselves last.

Spiral Matrix

Took me around 40 minutes. The task was to return all elements of the matrix in spiral order. The difficulty lay in correctly navigating the matrix in a spiral pattern without revisiting elements. My initial attempts struggled with the edge cases, particularly when the matrix wasn't square (i.e., had different widths and heights). After implementing careful boundary checks and updating the traversal limits after completing each spiral loop, the solution successfully traversed various matrix shapes in spiral order.

Rotate Image

Took me about 30 minutes. The key was to perform the rotation in layers, starting from the outermost layer and gradually moving inward. I made errors in the indexing during the four-way swap required for the rotation. After carefully mapping each element's final position and ensuring the swaps were done layer by layer, the rotation was correctly achieved without the need for extra space.

Word Search

Took me approximately 50 minutes. The main challenge was implementing a depth-first search to explore possible paths for each letter in the grid. I faced difficulties with backtracking, particularly in marking and unmarking visited cells to avoid reusing the same letter. Ensuring that the path was reset correctly after exploring each possibility was crucial. After refining the DFS algorithm and carefully handling the visited states of the cells, I was able to solve the problem for various test cases.

Longest Substring Without Repeating Characters

I solved in about 45 minutes. The challenge was to efficiently track characters and their indices without repeatedly scanning the substring. I used a sliding window approach with a hash map to store the characters and their most recent indices. I struggled with correctly updating the start of the window when a repeated character was found. After adjusting the window update mechanism to account for previously seen characters, the solution efficiently found the longest substring without repetition.

Longest Repeating Character Replacement

Took me about 45 minutes to solve. The challenge was to find the length of the longest substring that can be obtained by replacing no more than 'k' characters in the original string. Implementing the sliding window technique was key, but the main difficulty lay in efficiently tracking the count of each character within the window. I miscalculated the window size when more than one type of character needed replacement. After refining the logic to maintain the frequency of each character and adjusting the window size accordingly, the solution correctly determined the maximum length of the substring.

Minimum Window Substring

Took me around 1 hour. The problem involved finding the smallest substring that contains all the characters of a given string. The major difficulty was in using the sliding window approach to dynamically adjust the window size while ensuring that all target characters were included. I struggled with correctly accounting for character frequencies and updating the window bounds. After implementing a hash map to track the frequencies of the required characters and refining the window adjustment logic, I managed to find the minimum window satisfying the conditions.

Valid Anagram

I completed this one in about 20 minutes. This involved comparing the frequency of each character in both strings. The task was relatively straightforward, but the challenge was to implement an efficient solution. I used a hash map to count the character frequencies in one string and then compared it with the other. The main issue was handling edge cases, such as strings with different lengths or containing non-alphabetic characters. Ensuring accurate character counts and handling these edge cases were key to verifying the anagram status.

Group Anagrams

Took me about 50 minutes. The challenge was to find an efficient way to identify anagrams. I used a hash map with a sorted version of each string as the key to group anagrams. The main difficulty was in handling large strings and optimizing the sorting mechanism. After implementing the sorting and hash map logic, I successfully grouped the anagrams, though managing large input sets required careful consideration of the algorithm's efficiency.

Valid Parentheses

It took me about 25 minutes to solve. The task was straightforward but required careful implementation of a stack to track the opening and closing brackets. I missed handling edge cases, such as strings with an unbalanced number of parentheses. Ensuring that each closing bracket corresponded to the correct and most recent opening bracket in the stack was crucial for determining the validity of the parentheses in the string.

Valid Palindrome

Took me about 25 minutes. The main challenge was to efficiently handle the string manipulation, ensuring that non-alphanumeric characters were ignored and that the comparison was case-insensitive. I used two pointers, one from the start and one from the end, moving towards the center, and compared characters at each step. I overlooked some edge cases with special characters and spaces, but after refining the character validation logic, the solution correctly identified valid palindromes.

Longest Palindromic Substring

Took me around 45 minutes to solve. I approached it using dynamic programming, but the main difficulty was in setting up the table correctly and ensuring all possible substrings were considered. I had issues with correctly initializing the table and handling single-character palindromes. After adjusting the dynamic programming approach to check for palindromes of varying lengths and optimizing the table updates, I successfully identified the longest palindromic substring.

Palindromic Substrings

Completed in about 40 minutes, involved finding all substrings that are palindromes. The challenge was to efficiently iterate through the string and expand around each character to find palindrome substrings. I missed considering even-length palindromes, which led to an undercount. After implementing a dual approach that expanded around each character and each pair of characters, I was able to count all palindromic substrings correctly.

Encode and Decode Strings (Leetcode Premium)

Took me around 50 minutes to solve. It required designing a way to encode a list of strings into a single string and then decode it back to the original list. The main challenge was to implement an encoding scheme that could handle various characters, including delimiters. I struggled with choosing the right delimiter and escaping characters. After devising a scheme that used the length of the string as a prefix, followed by a delimiter and the string itself, I was able to encode and decode the list of strings accurately.

Maximum Depth of Binary Tree

Took me about 20 minutes. The straightforward recursive approach was to traverse the tree and calculate the depth at each node. The challenge was in correctly implementing the base case and ensuring that the maximum depth was calculated for both left and right subtrees. I had to adjust the recursion to correctly handle empty trees and leaf nodes. After refining the recursive function to return the maximum depth correctly, the solution efficiently determined the height of various binary trees.

Same Tree

Took me about 25 minutes. The task required a comparison of the structure and node values of both trees. I used a recursive approach, comparing nodes at each level. The main challenge was handling null nodes correctly and ensuring that the trees had the same structure and values. I overlooked a case where one tree was a subtree of the other but not identical. After refining the recursion to handle null nodes and compare each corresponding node in the trees, the solution correctly identified whether two trees were the same.

Invert/Flip Binary Tree

Took me around 30 minutes. I implemented a recursive approach to swap the left and right children of each node. The primary difficulty was in ensuring that the swap didn't disrupt the tree's structure, especially when dealing with nodes that had only one child. After careful consideration of the base cases and ensuring that each node was visited and swapped correctly, the tree was successfully inverted.

Binary Tree Maximum Path Sum

Took me around 50 minutes to solve. This involved a deep dive into recursive tree traversal, where the challenge was to calculate the maximum path sum for each node, considering that the path could start and end at any node. I struggled with handling negative node values and understanding how to maximize the path sum at each node without restricting it to start or end at the root. Refining the recursive function to return the maximum path sum at each step and updating a global maximum value was key to solving this problem.

Binary Tree Level Order Traversal

Took me about 35 minutes. The task was to traverse a binary tree level by level and record the values at each level. The main challenge was efficiently organizing the traversal using a queue to facilitate level order processing. I faced some difficulties in segregating the nodes of each level and had to fine-tune the loop that processed each level before moving on to the next. After correctly implementing the queue-based approach, the solution was able to traverse and record values for each level of the tree accurately.

Serialize and Deserialize Binary Tree

Took me about 1 hour to complete. The task involved converting a binary tree into a string and then reconstructing the tree from this string. The serialization part was straightforward, using pre-order traversal. However, the deserialization part was challenging, particularly in parsing the string and reconstructing the tree accurately, especially when dealing with null markers for missing nodes. I had to carefully manage the parsing logic and ensure that the tree structure was correctly maintained during reconstruction. After several iterations, the serialize and deserialize functions worked effectively, accurately representing and reconstructing various tree structures.

Subtree of Another Tree

Took me about 40 minutes. The task was to determine if one binary tree is a subtree of another. I approached this by first finding the matching node (same as the root of the potential subtree) in the main tree, and then recursively comparing the subtree from that node with the second tree. The main challenge was ensuring accurate comparison at each node, particularly with trees having similar structures. I missed handling null nodes correctly, which led to false positives. After refining the recursive comparison to accurately handle each node and its children, the solution effectively determined the subtree relationship.

Construct Binary Tree from Preorder and Inorder Traversal

Took me around 1 hour to solve. The key challenge was identifying the root and dividing the inorder sequence into left and right subtrees for recursive construction. I struggled with correctly mapping the indices from the preorder sequence to the inorder sequence. After implementing a hash map to efficiently find the index of the root in the inorder sequence and recursively constructing the left and right subtrees, I successfully reconstructed the binary tree.

Validate Binary Search Tree

Took me approximately 35 minutes. The task was to ensure that every node in the tree adheres to the BST properties. I used a recursive approach, passing down the valid range for each node. The main difficulty was correctly updating the range for each node, particularly when handling Integer boundaries. My initial implementation failed to account for the edge cases with Integer.MAX_VALUE and Integer.MIN_VALUE. After adjusting the range checks and ensuring that each subtree's values were within the correct range, the validation process worked correctly.

Kth Smallest Element in a BST

Took me about 30 minutes. This required an in-order traversal of the BST, as it naturally processes elements in sorted order. The challenge was to efficiently find the kth element without traversing the entire tree. I overlooked the optimization and traversed the whole tree. After that, I implemented a counter to terminate the traversal as soon as the kth element was reached. This optimization significantly reduced the traversal time, allowing the solution to efficiently find the kth smallest element.

Lowest Common Ancestor of BST

Took me about 25 minutes. The task was to find the lowest common ancestor (LCA) of two given nodes in a BST. Utilizing the properties of a BST, where all left descendants are less than the node and right descendants are greater, I traversed the tree from the root. The main challenge was ensuring that the traversal correctly identified the LCA, particularly in edge cases where one node was the ancestor of the other. After implementing the logic to compare the values of the nodes with the target nodes and considering the BST properties, I found the LCA efficiently.

Implement Trie (Prefix Tree)

Implementing the "Trie (Prefix Tree)" on LeetCode was a challenging task that took me about 1 hour. The problem required building a data structure to efficiently insert, search, and check prefixes of words. The main challenge was designing the trie node structure and implementing the methods for each operation correctly. I had issues with the insert function, particularly in handling the end of word markers. Also, optimizing the search and startsWith methods to run efficiently required careful consideration of the trie's structure. After refining the node design and ensuring each method worked correctly, the trie was able to handle various operations efficiently.

Add and Search Word

Solving the "Add and Search Word" problem took me about 45 minutes. This involved designing a data structure that supports adding new words and searching a word with potential dots ('.') as wildcards. The main difficulty was implementing the search function to handle the wildcard characters correctly. I used a backtracking approach to explore all possible matches for the wildcard characters. The challenge was to ensure that the backtracking process was efficient and correctly matched the words with wildcards. After fine-tuning the recursive logic, the data structure worked effectively for both adding and searching words.

Word Search II

Completing the "Word Search II" problem, which required finding all words from a given list that can be formed by a sequence of adjacent letters on a board, took me around 1 hour and 15 minutes. The primary challenge was to make it better the search to handle a large board and a long list of words efficiently. I implemented a trie to store the words and used backtracking to search the board. Managing the state of the board during recursion and optimizing the trie search were complex but crucial for efficiently finding all valid words.

Merge K Sorted Lists

Took me around 1 hour to complete. It involved merging multiple sorted linked lists into a single sorted list. The key was to efficiently merge these lists without redundant comparisons. I tried merging lists pair by pair but switched to using a min-heap for a more efficient approach. Managing the heap and updating the pointers in the linked lists correctly was challenging. After fine-tuning the heap operations, the merged list maintained the correct order and handled edge cases like empty lists.

Top K Frequent Elements

Took me about 40 minutes. The task was to identify the k most frequent elements in an array. The primary difficulty lay in efficiently counting the frequency of each element and then determining the top k elements. My initial approach used a hash map for frequency counting, but I faced challenges with efficiently sorting these frequencies. To overcome this, I implemented a min-heap to maintain the top k elements. The complexity was in managing the heap to ensure it only contained the most frequent elements. After adjusting the heap operations and frequency counting, the solution accurately identified the top k frequent elements.

Find Median from Data Stream

Took me around 1 hour to solve. This task required designing a data structure to continuously provide the median from a stream of integers. I used a two-heap approach, utilizing a max-heap for the lower half and a min-heap for the upper half of the numbers, to maintain a balanced distribution. The main challenge was in managing these heaps to ensure an efficient and accurate calculation of the median, especially when dealing with an even number of elements. After several iterations to refine the heap balancing and median calculation, the solution was able to efficiently provide the median at any given time.