Interval Problems with Code: Insert, Merge, and More

Intervals are a common topic in algorithmic problems. In this post, we’ll tackle five key interval problems: Insert Interval, Merge Intervals, Non Overlapping Intervals, Meeting Rooms, and Meeting Rooms II. Each problem will be solved with code examples and explanations. 1. Insert Interval Problem: Given a set of non-overlapping intervals sorted by their start time, insert a new interval into the intervals (merge if necessary) and return the result. Code Solution (Java): ...

August 19, 2024 · 9 min · 1728 words · PandaC

Coding Problems Cheatsheet

Category Problem Key Concepts/Strategies Detailed Explanation Code Example Arrays & Hashing Contains Duplicate Use a set to track seen numbers Iterate through the array, adding each element to the set; return true if an element is already in the set. Valid Anagram Use a hashmap to count character frequencies Count characters in both strings using hashmaps and compare the counts. Two Sum Use a hashmap to store indices of elements Iterate through the array, for each element, check if the complement (target - element) exists in the hashmap. Two Pointers Valid Palindrome Use two pointers to compare characters from both ends Initialize two pointers at the beginning and end of the string, move towards the center, and compare characters. 3Sum Sort the array, use two pointers to find triplets After sorting, fix one element and use two pointers to find pairs that sum up to the target value. Container With Most Water Use two pointers from both ends, move towards the center Start with two pointers at the ends of the array, calculate area, and move the pointer pointing to the shorter line. Sliding Window Best Time to Buy and Sell Stock Track the minimum price and maximum profit Iterate through prices, keeping track of the minimum price so far and calculating the maximum profit at each step. Longest Substring Without Repeating Characters Use a sliding window and a set to track characters Use a set to keep track of characters in the current window, move the window if a duplicate is found. Stack Valid Parentheses Use a stack to match opening and closing brackets Push opening brackets onto the stack, pop for closing brackets, ensuring they match. Binary Search Search in Rotated Sorted Array Modify binary search to handle rotation Determine which half is sorted, then use binary search logic on the sorted half. Find Minimum in Rotated Sorted Array Use binary search with rotation consideration Similar to searching in a rotated array, adjust the binary search to find the minimum element. Linked List Reverse Linked List Iterate and reverse pointers Use three pointers to reverse the direction of the list iteratively. Merge Two Sorted Lists Use a dummy node to merge iteratively Use a dummy node to simplify merging two lists, iteratively comparing and linking nodes. Reorder List Find middle, reverse second half, merge Split the list, reverse the second half, and merge the two halves by alternating nodes. Trees Binary Tree Inorder Traversal Use recursion or a stack Traverse left subtree, visit the node, then traverse the right subtree. Validate Binary Search Tree Use in-order traversal to check order Perform an in-order traversal and ensure each value is greater than the previous one. Same Tree Use recursion to compare nodes Recursively compare corresponding nodes in both trees. Tries Implement Trie (Prefix Tree) Use a TrieNode class to insert and search Use a nested TrieNode class to represent nodes, with methods for insert, search, and startsWith. Dynamic Programming Climbing Stairs Use DP array or memoization Use an array where each entry represents the number of ways to reach that step. House Robber Use a DP array to track maximum loot Use a DP array where each entry represents the maximum amount of money that can be robbed up to that house. Coin Change Use a DP array to track the minimum coins Use a DP array where each entry represents the minimum number of coins needed for that amount. Graphs Number of Islands Use DFS/BFS to mark visited islands Use DFS or BFS to traverse and mark all connected lands (islands) as visited. Clone Graph Use DFS/BFS and a hashmap for copies Use DFS or BFS with a hashmap to store already cloned nodes. Course Schedule Use DFS to detect cycles Perform a DFS and use a state array to detect cycles in the graph. Intervals Merge Intervals Sort intervals, then merge overlapping ones Sort intervals by start time, then iterate through and merge overlapping intervals. Insert Interval Insert and merge as necessary Insert the new interval into the list, then merge overlapping intervals. Meeting Rooms Sort intervals and check for overlaps Sort intervals by start time, use a min-heap to track end times of ongoing meetings. Strings Longest Substring Without Repeating Characters Use sliding window and a hashmap Use a sliding window to maintain a window of unique characters, updating the start of the window when a duplicate is found. Longest Palindromic Substring Use DP or expand around center approach Use dynamic programming to track palindromes or expand around each character to find the longest palindrome. Longest Common Prefix Compare characters of each string Compare characters of each string one by one until a mismatch is found. Backtracking Subsets Use backtracking to generate all subsets Recursively build subsets, choosing to include or exclude each element. Combination Sum Use backtracking to find combinations Recursively build combinations, subtracting from the target, and avoiding duplicates. Permutations Use backtracking to generate permutations Recursively generate permutations by swapping elements. Heap / Priority Queue Top K Frequent Elements Use a hashmap and a heap Use a hashmap to count frequencies, then use a heap to find the top K elements. Find Median from Data Stream Use two heaps to maintain the median Use a max-heap for the lower half and a min-heap for the upper half of the data stream. Greedy Best Time to Buy and Sell Stock II Sum up all the increasing differences Iterate through the array, summing up all positive differences between consecutive days. Jump Game Track the farthest reach possible Iterate through the array, updating the maximum reachable index and checking if the end is reachable. Bit Manipulation Single Number Use XOR to find the unique number XOR all elements, as XOR of two identical numbers is zero, and XOR of a number with zero is the number itself. Matrix Set Matrix Zeroes Use first row/column as markers Use the first row and column to mark zero rows and columns, then iterate and set zeros accordingly. Spiral Matrix Traverse in layers and change directions Use loops to traverse the matrix in a spiral order, changing direction at boundaries. Rotate Image Transpose and then reverse rows Transpose the matrix (swap rows and columns) and then reverse each row. Miscellaneous LRU Cache Use an ordered dictionary Use an ordered dictionary to maintain insertion order and implement LRU logic. Min Stack Use two stacks for value and minimum Use one stack for all values and another stack to keep track of minimum values.

July 7, 2024 · 6 min · 1081 words · PandaC

Group Anagrams

Question: Given an array of strings strs, group the anagrams together. Answer: To group anagrams together, you can use a dictionary to map sorted strings to their respective groups of anagrams. Here’s how you can do it in Python: def group_anagrams(strs): anagrams = {} for word in strs: sorted_word = ''.join(sorted(word)) if sorted_word in anagrams: anagrams[sorted_word].append(word) else: anagrams[sorted_word] = [word] return list(anagrams.values()) # Example strs = ["eat", "tea", "tan", "ate", "nat", "bat"] print(group_anagrams(strs)) In this code: We iterate through each word in the input array. For each word, we sort its characters and use the sorted string as a key in the anagrams dictionary. If the sorted string already exists in the dictionary, we append the word to its list of anagrams. Otherwise, we create a new entry with the sorted string as the key and a list containing the word as its value. Finally, we return the values of the anagrams dictionary as a list, which contains lists of anagrams. This solution has a time complexity of O(n * k * log(k)), where n is the number of words in the input array and k is the maximum length of a word. The space complexity is O(n * k) due to the dictionary used to store the grouped anagrams. ...

May 24, 2024 · 1 min · 210 words · PandaC

Two Sum

Question: Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the target. Answer: To solve this problem, you can use a dictionary to store the indices of the numbers you’ve seen so far. As you iterate through the array, you can check if the complement of the current number (target - current number) exists in the dictionary. If it does, you’ve found the two indices that add up to the target. ...

May 24, 2024 · 2 min · 291 words · PandaC

Valid Anagram

To solve the “valid anagram” problem, we need to determine if two given strings are anagrams of each other. Two strings are anagrams if they contain the same characters with the same frequencies. Here is a Python function that solves this problem using different approaches, followed by an analysis of each approach to find the best solution. Solution 1: Sorting def is_anagram(s, t): return sorted(s) == sorted(t) Explanation: Sorting: Sort both strings and compare them. If they are anagrams, their sorted versions will be identical. If not, they will differ. Analysis: Time Complexity: O(n log n), where n is the length of the strings (sorting time). Space Complexity: O(n), due to the space required for the sorted strings. Solution 2: Counting Characters with a Dictionary def is_anagram(s, t): if len(s) != len(t): return False count_s = {} count_t = {} for char in s: count_s[char] = count_s.get(char, 0) + 1 for char in t: count_t[char] = count_t.get(char, 0) + 1 return count_s == count_t Explanation: Early Exit: Check if the lengths of the strings are different; if so, return False. Counting: Use two dictionaries to count the frequency of each character in both strings. Comparison: Compare the two dictionaries. If they are equal, the strings are anagrams; otherwise, they are not. Analysis: Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(n), due to the space required for the dictionaries. Solution 3: Counting Characters with a Single Dictionary def is_anagram(s, t): if len(s) != len(t): return False count = {} for char in s: count[char] = count.get(char, 0) + 1 for char in t: if char in count: count[char] -= 1 else: return False return all(value == 0 for value in count.values()) Explanation: Early Exit: Check if the lengths of the strings are different; if so, return False. Counting and Balancing: Count the characters in the first string. Subtract the count while iterating through the second string. If a character in the second string is not in the count dictionary, return False. Final Check: Ensure all counts in the dictionary are zero. Analysis: Time Complexity: O(n), where n is the length of the strings. Space Complexity: O(n), due to the space required for the dictionary. Conclusion The best solution is Solution 3: Counting Characters with a Single Dictionary, due to its optimal time complexity O(n) and efficient space usage. Here’s the final version of the best solution: ...

May 23, 2024 · 3 min · 463 words · PandaC

Array Contains Duplicate

To determine if any value appears more than once in an integer array, the best approach is to use a set due to its optimal balance of time complexity, space complexity, and simplicity. Here’s a comprehensive solution and explanation: Solution def contains_duplicate(nums): seen = set() for num in nums: if num in seen: return True seen.add(num) return False Explanation Initialization: Create an empty set called seen. seen = set() Iteration: Loop through each element in the array. for num in nums: Check for Duplicates: ...

May 23, 2024 · 2 min · 346 words · PandaC