Question 1: Finding the Median from a Data Stream in Java
We’ll explore how to find the median from a data stream using Java. This is a common problem in data analysis and statistics, and it can be solved efficiently using a data structure called a heap. You can find this problem at Leetcode.
Find Median from Data Stream
https://leetcode.com/problems/find-median-from-data-stream/description/
Problem Statement
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
We need to implement a class MedianFinder that can add integers from a data stream to a data structure and find the median of all elements so far.
Solution using Heaps
One efficient solution to this problem is to use two heaps: a max heap to store the smaller half of the numbers, and a min heap to store the larger half. The median is then either the top of the max heap (when the total number of numbers is odd) or the average of the tops of the two heaps (when the total number of numbers is even).
Here’s the Java code for this solution:
import java.util.*;
class MedianFinder {
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;
public MedianFinder() {
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (maxHeap.size() < minHeap.size()){
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
}
Time Complexity
The time complexity of the addNum method is O(log n), where n is the total number of numbers added so far. This is because adding a number to a heap takes logarithmic time.
The time complexity of the findMedian method is O(1), because looking at the top of a heap takes constant time.
Sure, here’s a simple blog post on how to find the maximum value in a sliding window using Java:
Question 2: Finding the Maximum Value in a Sliding Window in Java
How to find the maximum value in a sliding window using Java. This is a common problem in data analysis and statistics, and it can be solved efficiently using a data structure called a PriorityQueue.
Sliding Window Maximum
https://leetcode.com/problems/sliding-window-maximum/
Problem Statement
Given an array of integers and a number k, we need to find the maximum value in each sliding window of size k.
Solution using PriorityQueue
One efficient solution to this problem is to use a PriorityQueue that stores the indices of the elements in the array, and sorts these indices based on their corresponding values in the array. The top of the PriorityQueue is always the index of the maximum value in the current window.
Here’s the Java code for this solution:
package array;
import java.util.PriorityQueue;
public class MaxSlidingWindow {
public static void main(String[] args) {
int [] nums = {1,3,-1,-3,5,3,6,7};
int k = 3;
int [] result = maxSlidingWindow(nums, k);
for(int num: result){
System.out.print(num+", ");
}
}
public static int[] maxSlidingWindow1(int[] nums, int k) {
int [] result = new int [nums.length - k +1];
PriorityQueue<Integer> priorityQueueIndexBased = new PriorityQueue<>(
(index1, index2) -> nums[index1] != nums[index2] ?
Integer.compare(nums[index2], nums[index1]) : Integer.compare(index2, index1));
for(int i=0; i< nums.length; i++){
while (!priorityQueueIndexBased.isEmpty() && priorityQueueIndexBased.peek() <= i - k){
priorityQueueIndexBased.poll();
}
priorityQueueIndexBased.offer(i);
if(i >= k-1){
result[i - k +1] = nums[priorityQueueIndexBased.peek()];
}
}
return result;
}
public static int[] maxSlidingWindow(int[] nums, int k) {
int [] result = new int [nums.length - k +1];
PriorityQueue<Integer> priorityQueueIndexBased = new PriorityQueue<>(
(index1, index2) -> nums[index1] != nums[index2] ?
Integer.compare(nums[index2], nums[index1]) : Integer.compare(index2, index1));
int i=0;
int count = 0;
for(; i< 3; i++){
priorityQueueIndexBased.offer(i);
}
result[count++] = nums[priorityQueueIndexBased.peek()];
for(; i< nums.length; i++){
int queueIndex = priorityQueueIndexBased.peek();
while( !priorityQueueIndexBased.isEmpty() && priorityQueueIndexBased.peek() <=i -k){
priorityQueueIndexBased.poll();
}
priorityQueueIndexBased.offer(i);
result[count++] = nums[priorityQueueIndexBased.peek()];
}
return result;
}
}
Time Complexity
The time complexity of the maxSlidingWindow method is O(n log n), where n is the length of nums. This is because for each number, we add it to the PriorityQueue (which takes log n time), and we potentially remove the maximum number from the PriorityQueue (which also takes log n time).
Conclusion
Finding the maximum value in a sliding window is a common problem that can be solved efficiently using PriorityQueue. This solution is fast, uses a reasonable amount of memory, and is easy to understand and implement in Java.
Question 3: Longest Valid Parentheses
Longest Valid Parentheses
https://codetechsummit.com/longest-valid-parentheses/
Question 3: Asteroid Collision.
package array;
import java.util.Stack;
public class AsteroidCollision {
public static void main(String[] args) {
int [] num = {-2, -1, 1, 2};
int [] result = asteroidCollision(num);
for(int data: result){
System.out.print(data+ ",");
}
}
public static int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for(int asteroid : asteroids){
if(asteroid < 0){
while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < Math.abs(asteroid)){
stack.pop();
}
if(!stack.isEmpty() && stack.peek() > 0 && stack.peek() == Math.abs(asteroid)){
stack.pop();
}else if(stack.isEmpty() || stack.peek() <0 ){
stack.push(asteroid);
}
}else{
stack.push(asteroid);
}
}
return stack.stream().mapToInt(Integer::intValue).toArray();
}
}
I hope you find this blog post helpful! If you have any questions or comments, feel free to leave them below. Happy coding! 😊
Merge Intervals
Ref: leetcode-java/en at 578ee6c415eb6075952f7b326148340a663a965f · andavid/leetcode-java · GitHub
Question:
- Input:
- You have a list of lists (
arrayList) containing sublists of integers. - Each sublist represents an interval or a set of elements.
- You have a list of lists (
- Objective:
- The goal is to sort these sublists based on their sizes (number of elements) in descending order.
- You want to limit the result to a specific number of top sublists (specified by the
sizevariable).
- Explanation:
- The code snippet achieves this by:
- Using
arrayList.stream()to create a stream of sublists. - Sorting the sublists based on their sizes (largest to smallest) using the comparator
(list1, list2) -> list2.size() - list1.size(). - Limiting the result to the specified size using
.limit(size). - Collecting the sorted sublists into a new list using
.collect(Collectors.toList()).
- Using
- The code snippet achieves this by:
- Example:
- Suppose you have the following input:
[[2, 3, 4], [1, 2], [3, 2, 1, 0, 5], [1]] - After sorting by size in descending order and limiting to the top 3 sublists, the result would be:
[[3, 2, 1, 0, 5], [2, 3, 4], [1, 2]]
- Suppose you have the following input:
List<List<Integer>> result = arrayList.stream().sorted((list1, list2) -> list2.size() - list1.size()).limit(size).collect(Collectors.toList());
Collections.sort(arrayList, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
return o2.size() - o1.size();
}
});