This repository contains my solutions to LeetCode problems. I will be adding more solutions as I solve more problems.
This category focuses on problems that leverage arrays and hash-based data structures (e.g., hash maps, hash sets) to optimize lookups, store frequency counts, or handle data efficiently.
[DONE] Uses a hash map to subtract the remainder in order to find the solutions.
[DONE] Uses a two-pointer approach with a sorted array to find quadruplets that sum to a target value.
[DONE] Groups anagrams by sorting each string and using a hash map to collect them.
[DONE] Uses a hash set to track consecutive sequences by checking for the start of each sequence and counting its length.
[DONE] Counts the maximum number of balls in a box based on their colors and positions. Uses a hash map to track counts.
[DONE] Counts items that match a given rule using a hash map to filter based on criteria.
[DONE] Finds the closest dessert cost to a target by exploring combinations of two dessert costs. Uses a set to track possible costs and find the closest one.
[DONE] Calculates the product of all elements except self using two arrays to store left and right products, avoiding division.
[DONE] Uses a hash set to track seen numbers and find the first duplicate in an array.
[DONE] Uses hash sets to find the intersection of two arrays, returning unique elements.
This category involves problems solved using two pointers to traverse arrays or lists, often to optimize solutions by reducing time complexity or to handle sorted data efficiently.
[DONE] Uses two pointers to maximize area between heights in an array.
[DONE] Uses two pointers with a sorted array to find triplets summing to zero.
[DONE] Uses two pointers to overwrite duplicates in a sorted array.
[DONE] Uses two pointers to move all zeroes to the end of an array while maintaining order.
Sliding window techniques are used for problems involving contiguous subarrays or substrings, maintaining a "window" that expands or contracts to meet conditions.
[DONE] Uses a sliding window with a hash set to track the longest substring without duplicates.
[DONE] Uses a sliding window to find the minimum substring containing all characters of a target string.
[DONE] Uses a deque to maintain the maximum values in a sliding window over an array.
[DONE] Uses a sliding window to find the longest substring with at most k replacements of characters.
[DONE] Solution: Use a sliding window and subtract and add the characters from sliding hash to be compared with anagram hash.
Dynamic programming solves problems by breaking them into overlapping subproblems and storing results to avoid redundant computations, often used for optimization problems.
[DONE] Expands around centers to find the longest substring that reads the same forward and backward.
[DONE] Uses dynamic programming to match a string against a pattern with wildcards.
[DONE] Uses Kadane's algorithm to find the contiguous subarray with the maximum sum.
Kadane's Algorithm
- Initialize two variables:
max_currentandmax_globalto the first element of the array.- Iterate through the array starting from the second element.
- For each element, update
max_currentto be the maximum of the current element and the sum ofmax_currentand the current element.- If
max_currentis greater thanmax_global, updatemax_global.- After iterating through the array,
max_globalwill contain the maximum subarray sum.
[DONE] Uses dynamic programming to count the number of unique paths from the top-left corner to the bottom-right corner of a grid.
[DONE] Uses dynamic programming to find the minimum path sum from the top-left to the bottom-right of a grid by accumulating the minimum sums from adjacent cells.
[DONE] Uses dynamic programming to count the number of distinct ways to reach the nth step by summing the ways to reach the previous two steps.
[DONE] Uses dynamic programming to find the contiguous subarray with the maximum product by tracking both maximum and minimum products at each step.
[DONE] Uses dynamic programming to determine the maximum amount of money that can be robbed from a series of houses without robbing two adjacent houses.
[DONE] Uses dynamic programming to find the length of the longest increasing subsequence in an array by maintaining an array of lengths of increasing subsequences.
[DONE] Uses dynamic programming to find the minimum number of coins needed to make a given amount.
[DONE] Uses dynamic programming to determine if a set can be partitioned into two subsets with equal sum by checking if a subset with half the total sum exists.
[DONE] Uses dynamic programming to find the number of combinations to make a given amount with a set of coins.
[DONE] Uses a hash map to count the number of subarrays that sum to a given value k by tracking cumulative sums.
[DONE] Uses dynamic programming to count all palindromic substrings in a string by expanding around centers and checking for palindromes.
[DONE] Uses dynamic programming with recursion to find the maximum amount of money that can be robbed from a binary tree of houses, ensuring no two adjacent houses (parent-child) are robbed.
Backtracking involves exploring all possible solutions by building candidates incrementally and abandoning invalid paths, often used for combinatorial problems.
[DONE] Uses backtracking to find all unique combinations of numbers that sum to a target value, allowing for repeated use of numbers.
[DONE] Uses backtracking to generate all permutations of a list of numbers.
[DONE] Place N queens on an NxN board. Classic recursion and backtracking problem.
[DONE] Counts the number of distinct solutions for the N-Queens problem. Tests backtracking and recursion.
[DONE] Generate all subsets of a set. Tests recursive backtracking.
[DONE] Uses backtracking to search for a word in a 2D board by exploring all possible paths.
Sorting problems involve arranging data to enable efficient processing, often as a preprocessing step for other algorithms like binary search or two pointers.
[DONE] Merges two sorted arrays and finds the median by tracking middle elements.
[DONE] Sorts an array of colors (0s, 1s, 2s) using a three-pointer approach (Dutch National Flag problem).
[DONE] Sorts meeting intervals by start time and end time to determine the maximum number of meeting rooms required at any time.
Stack-based solutions are used for problems requiring last-in-first-out processing, while monotonic stacks maintain elements in a sorted order for efficient lookups.
[DONE] Uses a stack to check if parentheses are balanced and properly nested.
[DONE] Uses a stack to calculate the amount of water trapped between heights in an array.
[DONE] Uses a stack to find the next greater element for each element in an array, returning results based on indices.
[DONE] Uses a monotonic stack to find the number of days until a warmer temperature for each day in an array of temperatures.
Heap-based solutions use priority queues to efficiently manage elements based on priority, often for problems requiring top-k elements or scheduling.
[DONE] Uses a priority queue to merge k sorted linked lists into one sorted list.
[DONE] Uses a min heap to find the kth largest element in an array by maintaining a heap of size k and returning the root.
[DONE] Uses a max heap and a min heap to maintain the median of a data stream in O(log n) time for insertion and O(1) time for finding the median.
[DONE] Uses a priority queue to find the k most frequent elements in an array by counting frequencies and maintaining a heap of size k.
[DONE] Uses a priority queue to schedule tasks with cooldown periods, ensuring tasks are executed in the order of their frequencies.
Greedy algorithms make locally optimal choices at each step to achieve a globally optimal solution, often for problems involving resource allocation or scheduling.
[DONE] Uses a greedy approach to determine if you can reach the last index of an array by checking the maximum reachable index at each step.
[DONE] Uses a greedy approach to find the maximum profit from buying and selling stock by tracking the minimum price seen so far and calculating potential profits.
[DONE] Uses a greedy approach (Boyer-Moore Voting Algorithm) to find the majority element in an array, which appears more than n/2 times.
Divide and conquer breaks problems into smaller subproblems, solves them recursively, and combines results, often used for tree or array-based problems.
[DONE] Constructs a binary tree from preorder and inorder traversal arrays by recursively dividing the arrays into left and right subtrees.
Inorder and Preorder Theory Notes
- Inorder traversal visits nodes in the order: left, root, right.
- Preorder traversal visits nodes in the order: root, left, right.
[DONE] Divide and conquer approach to convert an integer to English words by breaking it down into thousands, hundreds, tens, and units.
Binary search efficiently finds elements or boundaries in sorted data by repeatedly dividing the search space in half.
[DONE] Uses binary search with left and right pointers to find an element in a rotated sorted array.
[DONE] Uses binary search to find the first and last positions of a target element in a sorted array, handling edge cases for duplicates.
[DONE] Uses binary search to find the minimum element in a rotated sorted array by checking midpoints and adjusting search boundaries based on comparisons.
[DONE] Implements binary search to find a target value in a sorted array, returning its index or -1 if not found.
Linked list problems involve manipulating or traversing singly or doubly linked lists, often requiring pointer manipulation or dummy nodes.
[DONE] Iterates through two linked lists, adding digits and carrying over to sum them.
[DONE] Uses two pointers with a gap of n to remove the nth node from the end.
[DONE] Uses a dummy node to merge two sorted linked lists into one sorted list.
[DONE] Uses a slow and fast pointer approach (Floyd's Cycle Detection) to determine if a linked list has a cycle.
[DONE] Uses a slow and fast pointer approach to find the starting node of a cycle in a linked list, if it exists.
[DONE] Uses merge sort to sort a linked list by recursively splitting and merging sorted sublists.
[DONE] Uses two pointers to find the intersection node of two linked lists by aligning their lengths and traversing together.
[DONE] Uses a three-pointer approach to reverse a singly linked list in place.
[DONE]
- Uses a two-pointer approach to check if a linked list is a palindrome by reversing the second half and comparing it with the first half.
- Alternatively, it can use a stack to store the first half and compare it with the second half.
[DONE]
- Rearranges a linked list such that all odd-indexed nodes come before even-indexed nodes while maintaining their relative order.
- Uses two pointers to separate odd and even nodes, then connects them at the end.
[DONE] Use a slow and fast pointer to find the middle node of a linked list.
Tree problems involve traversing or manipulating binary trees or binary search trees, often using recursion or iterative approaches with stacks/queues.
[DONE] Validates a binary search tree by checking if each node's value is within the valid range defined by its ancestors.
[DONE] Recursively finds the lowest common ancestor of two nodes in a binary tree by checking if the current node is one of the nodes or if both nodes are in different subtrees.
Trie (prefix tree) problems involve storing and retrieving strings efficiently, often for prefix-based or dictionary-based searches.
Implement a trie with insert, search, and startsWith methods. Core trie problem.
Find all words in a board that exist in a dictionary. Tests trie with DFS.
Graph problems involve traversing graphs (DFS/BFS) or detecting cycles, while union-find is used for connectivity or grouping problems.
[DONE] Uses DFS to count connected components in a grid representing islands.
[DONE] Uses topological sorting to determine if all courses can be finished given prerequisites, testing cycle detection in directed graphs.
[DONE] Returns the order of courses to take based on prerequisites using topological sorting.
[DONE] Uses DFS to count connected components in a graph representing provinces.
[DONE] To solve it uses union-find to detect cycles in a graph, identifying the redundant edge that creates a cycle.
Interval problems involve manipulating or merging time or range-based intervals, often requiring sorting as a preprocessing step.
[DONE] Sorts intervals by start time and merges overlapping intervals into a single interval.
Matrix problems involve manipulating 2D arrays, often requiring traversal in specific patterns or in-place modifications.
[DONE] Rotates a 2D matrix by transposing it and then reversing each row.
[DONE] Uses a layer-by-layer approach to traverse a 2D matrix in spiral order.
Bit manipulation problems use bitwise operations (e.g., XOR, AND, OR) to solve problems efficiently, often for low-level data processing.
Find the number that appears once in an array. Tests XOR operations.
Count the number of 1s in a binary number. Tests bit manipulation basics.
Math problems involve numerical computations, number theory, or mathematical properties to derive solutions.
[DONE] Converts an integer to Roman numerals using a mapping of values to symbols.
[DONE] Sums values of Roman numeral characters, adjusting for subtractive cases.
[DONE] Implement power function with exponentiation. Tests fast exponentiation.
String problems involve parsing, manipulating, or validating strings, often using stacks, pointers, or character frequency counts.
[DONE] Converts a string to a zigzag pattern based on a given number of rows and reads it row by row.
[DONE] Reverses the digits of an integer while handling overflow and negative signs.
[DONE] Converts a string to an integer while handling leading/trailing spaces, signs, and overflow.
[DONE] Checks if an integer is a palindrome by comparing digits from both ends.
[DONE] Compares characters across strings to find the longest shared prefix.
Simplify a Unix-style file path (e.g., "/a/./b/../../c/" to "/c"). Tests string parsing and stack-based processing.
Decode a string with nested brackets (e.g., "3[a]2[bc]" to "aaabcbc"). Tests stack and recursive parsing.
Design problems focus on implementing data structures or systems with specific functionality, often simulating real-world applications.
Design a simplified Twitter with follow and newsfeed features. Tests system design in coding.
Implement a parking lot system to manage vehicle parking and availability. Tests object-oriented design and system thinking.
Design a logger that limits message printing based on timestamps. Tests system design with time-based constraints.
Queue problems involve implementing or using FIFO data structures, often for scheduling or buffering tasks.
Implement a circular queue. Tests queue implementation and edge cases.
These problems involve complex data structures like segment trees or binary indexed trees for efficient range queries or updates.
Update and query sum of a range in an array. Tests binary indexed tree.
Count smaller numbers to the right. Tests segment tree or BIT.
Design a hit counter to record hits in the last 5 minutes. Tests queue or array with timestamps.
- System design problems focus on designing scalable systems or components, often requiring object-oriented or time-based logic.
- Concurrency problems involve managing multiple threads or processes, ensuring proper synchronization and order of execution.
Ensure three threads print in a specific order using synchronization primitives (e.g., locks, semaphores). Tests thread coordination.
Implement a thread-safe bounded queue for producer-consumer scenarios. Tests synchronization and queue design.
This category includes problems that don't fit neatly into other categories, often combining multiple techniques or unique approaches.
[DONE] Evaluates expressions in Reverse Polish Notation using a stack to handle operands and operators.
[DONE] Rotates an array in place by reversing segments of the array.
[DONE] Reverses a string in place using two pointers.
[DONE] Generates a FizzBuzz sequence based on divisibility rules for 3 and 5.
[DONE] Finds the length of the longest substring without repeating characters using a sliding window technique with a hash set to track characters.
[DONE] Uses a two-pointer approach with a sorted array to find the sum of three integers closest to a target value, iterating through pairs and adjusting pointers based on comparisons.
[DONE] Uses backtracking to generate all possible letter combinations for a given phone number based on the mapping of digits to letters.