Coding Problems and Solutions-6
[1] Find Median from Data Stream — Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Design a data structure that supports the following two operations:
- void addNum(int num) — Add a integer number from the data stream to the data structure.
- double findMedian() — Return the median of all elements so far.
(https://leetcode.com/problems/find-median-from-data-stream/)
Approach — Use a min-heap and a max-heap. For N numbers, min-heap stores the highest N/2 and max-heap the lowest N/2 numbers.
For a new number if sizes of min and max heap are equal then the number is added to min-heap if the number if greater than root of the max-heap.
If the new number is smaller than root of max-heap, then take the root of max-heap and add it to min-heap and add the new number to max-heap. The median is then root of min-heap.
When size of min-heap is greater, then if the new number is smaller than root of min-heap, it is added to max-heap else take the root of min-heap and add it to max-heap and add the new number to min-heap. Median is average of root of min and max heap.
[2] Robot Room Cleaner — Given a robot cleaner in a room modeled as a grid.
Each cell in the grid can be empty or blocked.
The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.
When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.
Design an algorithm to clean the entire room using only the 4 given APIs shown below.
class Robot {
#returns true if next cell is open and robot moves into the cell.
#returns false if next cell is obstacle and robot stays on the current cell. def move() {} #Robot will stay on the same cell after calling turnLeft/turnRight.
#Each turn will be 90 degrees. def turnLeft() {}
def turnRight() {} #Clean the current cell. def clean() {}
}
[3] Odd Even Linked List — Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL(https://leetcode.com/problems/odd-even-linked-list/)
Approach — Use recursion. For node i, use recursion to obtain 2 lists (odd and even numbered) from index i+2 onwards, then add the i-th node as head to the list with head i+2 and i+1-th node to list with head i+3-rd node.
[4] Search a 2D Matrix — Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]Given target = 5, return true.
Given target = 20, return false.
(https://leetcode.com/problems/search-a-2d-matrix-ii/)
Approach — Use binary search.
[5] Find the Kth Smallest Sum of a Matrix With Sorted Rows — You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order.
You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest array sum among all possible arrays.
Example:
Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.(https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/)
Approach — Use priority queue.
[6] Find K-th Smallest Pair Distance — Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.
Example:
Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.(https://leetcode.com/problems/find-k-th-smallest-pair-distance/)
Approach — Do binary search from minimum to maximum difference. For a value of diff, count the number of differences smaller than equal to diff. To count number of differences less than equal to diff use a queue.
If total number of differences is smaller than k then increase ‘diff’ else decrease diff.
[7] Range Sum Query 2D — Immutable — Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
(https://leetcode.com/problems/range-sum-query-2d-immutable/)
Approach — Use DP. Precompute mat_sum[i][j] which is the sum of all elements in the rectangle (0, 0) (top-left) to (i, j) (bottom-right).
[8] Possible Bipartition — Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.
Each person may dislike some other people, and they should not go into the same group.
Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.
Return true if and only if it is possible to split everyone into two groups in this way.
Example:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3](https://leetcode.com/problems/possible-bipartition/)
Approach — Use DFS. Bipartition is not possible if there is a cycle of odd length. Create adjacency list of the dislikes and do DFS from each node. If there is a cycle along a path with odd length then it is not possible to create a bipartition.
[9] Russian Doll Envelopes — You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Note:
Rotation is not allowed.
Example:
Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).(https://leetcode.com/problems/russian-doll-envelopes/)
Approach — Sort the envelopes on width first. Use an array ‘num_envelopes’ where num_envelopes[k] is the maximum height (height of outermost envelope) for k envelopes in total.
Note that num_envelopes[k+1] > num_envelopes[k].
For the i-th envelope do binary search on num_envelopes to find highest envelope j such that num_envelopes[j] < height[i]. Update num_envelopes[j+1] with the current height[i].
[10] Vertical Order Traversal of a Binary Tree — Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of Xcoordinate. Every report will have a list of values of nodes.
Example:
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).(https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)
Approach — Use BFS. For each node assign it to a (x, y) coordinate. For a node with coordinates (x, y) its children are assigned (x-1, y+1) and (x+1, y+1). Nodes with same x-coordinates lie in the same vertical order. For same x-coordinate sort on y-axis.
[11] Find K Pairs with Smallest Sums — You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.
Example:
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/)
Approach — Use heap.
