4. Median of Two Sorted Arrays
84. Largest Rectangle in Histogram
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution:
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution:
You must know how to merge 2 sorted LinkedList, but how about k? There are two methods:
Recursion. Somehow if we can merge first k/2 lists, and last k/2 lists, respectively, then we can easily merge the two new merged lists. The base case is one list. The idea is similar to merge sort.
Use BFS, more specifically, dijkstra's algorithm.
Method 1:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
int left = 0;
int right = lists.length - 1;
return helper(lists, left, right);
}
private ListNode helper(ListNode[] lists, int left, int right) {
if (left == right) {
return lists[left];
}
int mid = left + (right - left) / 2;
ListNode leftHead = helper(lists, left, mid);
ListNode rightHead = helper(lists, mid + 1, right);
return mergeTwo(leftHead, rightHead);
}
private ListNode mergeTwo(ListNode left, ListNode right) {
if (left == null) {
return right;
}
if (right == null) {
return left;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
if (left != null) {
cur.next = left;
} else if (right != null) {
cur.next = right;
}
return dummy.next;
}
}
If there are m lists and the length of each list is n, then the time complexity is O(mnlogm) , because there are logm levels in the recursion tree and at each levle, the time complexity is mn. Space complexity is O(logm).
Method 2:
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, ListNodeComparator);
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
pq.offer(lists[i]);
}
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (!pq.isEmpty()) {
ListNode min = pq.poll();
cur.next = min;
cur = cur.next;
if (min != null && min.next != null) {
pq.offer(min.next);
}
}
return dummy.next;
}
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
public int compare(ListNode left, ListNode right) {
return left.val - right.val;
}
};
}
If there are m lists and the length of each list is n, then the time complexity is O(mnlogm) , because the heap offer/poll is O(logm) and all the mn nodes need to be offered to the heap then polled from the heap. Space complexity is O(m).
25. Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Solution:
Based on Problem 24. Swap Nodes in Pairs. Still use recursion.
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) {
return head;
}
ListNode cur = head;
//another base case: less than k nodes, return head
for (int i = 0; i < k; i++) {
if (cur == null) {
return head;
} else {
cur = cur.next;
}
}
// reverse first k nodes
ListNode prev = null;
cur = head;
for (int i = 0; i < k; i++) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
ListNode newHeadSub = reverseKGroup(cur, k);
ListNode newHead = prev;
head.next = newHeadSub;
return newHead;
}
}
30. Substring with Concatenation of All Words
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9]. (order does not matter).
Solution:
41. First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
Solution:
It is similar to **
public class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
for (int i = 0; i < nums.length; i++) {
while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
84. Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given heights = [2,1,5,6,2,3],
return 10.
Solution:
It is very difficult to explain this problem clearly.
public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int result = 0;
Deque<Integer> stack = new LinkedList<>();
// stack stores the "index", not height;
for (int i = 0; i <= heights.length; i++) {
// cur is current height;
// at last, explicitly add a bar of height 0 so we can pop out all elements in the stack
int cur = i == heights.length ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peekFirst()] >= cur) {
int height = heights[stack.pollFirst()];
int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
result = Math.max(result, height * (i - left));
}
stack.offerFirst(i);
}
return result;
}
}
149. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:
Two points are always on the same line. Three points are on the same line if any two of them has the same slope, i.e., slope of line AB is equal to slope of line BC.
The idea is simple as we can just use a Map to record # of points belonging to the same slope, while the implementation is not easy because we need to consider duplicate points and what if slope is positive infinity.
The code below works for all cases except [[0,0],[94911151,94911150],[94911152,94911151]]. The reason is that even double data type can not tell the difference of two extremely close numbers due to precision lost.
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) {
return 0;
}
Map<Double, Integer> map = new HashMap<>();
int max = 1;
for (int i = 0; i < points.length; i++) {
map.clear();
int dup = 1;
for (int j = i + 1; j < points.length; j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
dup++;
continue;
}
double slope = points[j].x - points[i].x == 0 ? Integer.MAX_VALUE : 0.0 + (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
map.put(slope, map.getOrDefault(slope, 0) + 1);
}
max = Math.max(max, dup);
for (int temp : map.values()) {
max = Math.max(max, dup + temp);
}
}
return max;
}
}
When dealing with float/double number, precision lost is always a issue. For a / b = c, we can use the integer pair (a, b) to represent the float number c. We need simplify (a, b) by dividing their greatest common dividend(gcd). For example, 10 / 4 = 2.5 and we use (5, 2) to represent it. A 2000+ years old algorithm can find gcd, please refer here and its Chinese name is 辗转相除法.
public class Solution {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0) {
return 0;
}
Map<Map<Integer, Integer>, Integer> map = new HashMap<>();
int max = 1;
for (int i = 0; i < points.length; i++) {
map.clear();
int dup = 1;
for (int j = i + 1; j < points.length; j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
dup++;
continue;
}
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int d = gcd(dx, dy);
Map<Integer, Integer> slope = new HashMap<>();
slope.put(dx / d, dy / d);
map.put(slope, map.getOrDefault(slope, 0) + 1);
}
max = Math.max(max, dup);
for (int temp : map.values()) {
max = Math.max(max, dup + temp);
}
}
return max;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
By storing a pair (a, b), we can avoid the hassle of vertical line.
Do you notice that I use a Map to store the pair? At first, I try to use a int array:
****
Map<int[], Integer> map = new HashMap<>();
****
int[] slope = new int[]{dx / d, dy / d};
map.put(slope, map.getOrDefault(slope, 0) + 1);
****
It does not work. Because int[] inherits equals from Object so it will compare the reference. But map in Java implements equals mehtod which compares the content.