February 10, 2024
Problem Statement # You are given a 2D integer grid terrain representing the elevation of a landscape. Imagine that rain falls uniformly across the area and is trapped depending on the terrain’s shape. Calculate the total volume of water that would be trapped.
Example:
Input: terrain = [ [2, 3, 5, 1], [6, 5, 3, 4], [3, 1, 2, 5] ] Output: 7 Solution Approach # This problem can be effectively solved using a combination of Breadth-First Search (BFS) and a priority queue (Min-Heap).
...
February 7, 2024
Problem Statement # Design a class to calculate the median of a number stream at any time. The class should support two operations: addNum(int num) which adds an integer to the data structure, and findMedian() which returns the median of all elements so far.
Solution Approach # The solution involves using two heaps: a max heap for the lower half of the numbers and a min heap for the upper half.
...
February 4, 2024
Problem Statement # You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists. Your algorithm’s complexity must be better than brute force, meaning you can’t just check every possible range.
Solution Approach # The solution involves using a min-heap to keep track of the minimum value across the k lists and expanding the range until it covers at least one number from each list.
...
January 26, 2024
Problem Statement # There is a special apple tree that grows several types of apples at different rates. The apples mature at different times, and they rot at different times after maturing. You are given two integer arrays apples and days, both of the same length. The i-th element of each array represents the number of apples that mature and the number of days they stay fresh, respectively, starting from the i-th day.
...
January 25, 2024
Problem Statement # Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Example:
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13. Solution Approach # The solution involves using a min heap to efficiently find the kth smallest element.
...
January 25, 2024
Problem Statement # A car travels from a starting position to a destination, a distance of target miles. There are gas stations along the way. The car starts with an initial tank of fuel, and it can travel startFuel miles on a full tank. You are given an integer target, an integer startFuel, and an array stations where stations[i] = [position_i, fuel_i] indicates that the i-th gas station is position_i miles along the way and has fuel_i liters of gas.
...
January 23, 2024
Problem Statement # You have some sticks with positive integer lengths. You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You must connect all the sticks until there is only one stick remaining. Return the minimum cost to connect all the given sticks into one stick in this way.
Example:
Input: sticks = [2, 4, 3] Output: 14 Explanation: You start with sticks = [2,4,3].
...
January 20, 2024
Problem # Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string.
Example:
Input: s = “aabbcc”, k = 3 Output: “abcabc” or “bacbac” Explanation: The same characters are at least distance 3 from each other. Solution Approach # The solution involves using a max heap to ensure the most frequent characters are placed first.
...
January 6, 2024
Problem: # Design a class to find the kth largest element in a stream of numbers. The class should have the following two methods:
add(num): Adds the number num to the stream. getKthLargest(): Returns the kth largest element in the stream. Example:
Initialize an instance with k=3 and the stream stream = [4, 5, 8, 2]. getKthLargest() should return 4. After adding 3, 5, 10, and 9 to the stream, getKthLargest() should return 5.
...
December 28, 2023
Problem # You are given an array nums of n positive integers. You can perform two types of operations on any element of the array any number of times: If the element is even, divide it by 2. If the element is odd, multiply it by 2. The deviation of the array is the maximum difference between any two elements in the array. Find the minimum deviation the array can have after performing some number of operations.
...
December 20, 2023
Problem # Given an unsorted list of integers, find the k most frequent elements in the list. Return them as a list with each element’s frequency.
Solution # To solve the problem of finding the k most frequent elements in an unsorted list of integers, you can use a combination of a hash map (dictionary in Python) to store the frequency of each element and a heap to efficiently find the k most frequent elements.
...
December 20, 2023
Problem # Given an array of integers and a sliding window of size k, find the maximum value in each window. The window slides one position to the right at a time.
Solution # import collections def max_sliding_window(nums, k): n = len(nums) if n == 0 or k == 0: return [] deque = collections.deque() result = [-1] * (n - k + 1) for i in range(n): while deque and deque[0] < i - k + 1: deque.
...