February 7, 2024
Problem Statement # Given two strings s1 and s2, return the minimum window in s1 which will contain all the characters in s2 in the order they appear in s2. If there is no such window in s1 that covers all characters in s2, return the empty string. If there are multiple such minimum-length windows, return the one with the left-most starting index.
Solution Approach # The solution involves a two-pointer technique to explore all the substrings of s1 that could potentially cover s2 and then narrowing down to the one with minimum length that satisfies the condition.
...
January 14, 2024
Problem # Given the head of a sorted linked list, delete all nodes that have duplicate numbers (leaving only distinct numbers from the original list) and return the sorted list.
Example:
Input: head = [1, 2, 3, 3, 4, 4, 5] Output: [1, 2, 5] Solution Approach # The solution involves using two pointers, one to iterate through the list (current) and another to ensure the connection between non-duplicate nodes (prev).
...
January 10, 2024
Problem # Given two sorted linked lists, merge them into one sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: list1 = [1, 2, 4], list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] Solution # The solution involves using a two-pointer technique. Create a new linked list and add nodes to it by comparing the current nodes of the two lists, advancing the pointer of the list with the smaller current node.
...
January 8, 2024
Problem # Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis, forms a container, such that the container contains the most water. You may not slant the container.
Example:
Input: [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49.
...
January 2, 2024
Problem # Given an array of integers, find the pair of numbers that has the closest sum to a given target value, without exceeding it. Return the pair of numbers.
Solution: # Algorithm: Two Pointers
Time Complexity: O(n log n) due to sorting Space Complexity: O(1) or O(n) depending on sorting algorithm
Steps:
Sort the array: Sort the array of integers in ascending order. Initialize pointers: Create two pointers, left and right, pointing to the beginning and end of the array, respectively.
...
December 31, 2023
Problem # Given an array of integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Solution # Here’s the Python code for solving the problem of computing how much water can be trapped after raining, given an array of integers representing an elevation map:
def trapRainWater(heights): """ Compute how much water can be trapped after raining in an elevation map.
...
December 29, 2023
Problem # Design a circular deque (double-ended queue) with ‘addFront’, ‘addRear’, ‘deleteFront’, and ‘deleteRear’ operations. The circular deque should support these methods in O(1) time complexity.
Solution # Here’s the Python code for the CircularDeque class:
class CircularDeque: def __init__(self, size): self.size = size self.count = 0 self.front = -1 self.rear = 0 self.deque = [None] * size def isFull(self): return self.count == self.size def isEmpty(self): return self.count == 0 def addFront(self, value): if self.
...
December 26, 2023
Problem # Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration, return the earliest time slot that works for both of them and is of duration.
Solution # To solve this problem, we need to find a common time slot between two schedules (slots1 and slots2) that is at least as long as the given meeting duration. A practical approach is to sort both schedules based on start times and then iterate through them to find overlapping intervals that can accommodate the meeting duration.
...
December 21, 2023
Problem # Given an array of integers, rearrange the elements such that all negative numbers appear before all positive numbers. The original relative order of elements must be preserved.
Solution 1 # def rearrange_negatives_first(arr): """ Rearrange the array so that all negative numbers appear before all positive numbers. The original relative order of the elements is preserved. """ # Separate negative and positive numbers while preserving their order negative_nums = [x for x in arr if x < 0] positive_nums = [x for x in arr if x >= 0] # Combine the separated lists return negative_nums + positive_nums # Example usage arr = [1, -3, 5, -2, 4, -6, 7, -9] rearranged_array = rearrange_negatives_first(arr) print(rearranged_array) This code works as follows:
...