Kth Smallest Element in a Sorted Matrix

https://github.com/fishercoder1534/fishercoderLeetcode/blob/master/MEDIUM/src/medium/KthSmallestElementInASortedMatrix.java

Advertisements

Rearrange String K Distance Apart

This is a very good problem, very classic to test one’s understanding of appropriate data structures and one’s ability to sort out the logic from multiple requirements.

Basically, any problems that you spend >= 6 hours trying to make it AC yourself, you’ll never forget.

My own approach made it to 48/56, but then I realized that my approach wont’ make it AC: because I was forming a string that is contains by all its unique chars first, and then append all those that still have counts, but it’s good that I’ve tried so many different ways and really honed my coding skills.

Eventually, inspired by this post, and rewrote it myself: https://discuss.leetcode.com/topic/48109/java-7-version-of-priorityqueue-o-nlogn-with-comments-and-explanations

Still learned something new and better understood the logic when I wrote it myself.


public String rearrangeString(String str, int k) {
char[] chars = str.toCharArray();
Map<Character, Integer> map = new HashMap();
for(char c : chars){
if(map.containsKey(c)) map.put(c, map.get(c)+1);
else map.put(c, 1);
}

/**Have two queues, one is a heap to store all map.entry and write a customized comparator, make it sort on its frequency,
* so that we could always poll the one with the highest frequency.
* the other is a normal queue to hold all possible candidates to append, this queue should be capped at size K, when it reached size K,
* its head should be polled/un-freezed.*/
Queue<Map.Entry<Character, Integer>> heap = new PriorityQueue(new Comparator<Map.Entry<Character, Integer>>(){
@Override
public int compare(Entry<Character, Integer> o1, Entry<Character, Integer> o2) {
if(o1.getValue() > o2.getValue()) return -1;
else if(o1.getValue() < o2.getValue()) return 1;
return 0;
}
});

for(Map.Entry<Character, Integer> entry : map.entrySet()){
heap.offer(entry);
}

Queue<Character> q = new LinkedList<Character>();
StringBuilder sb = new StringBuilder();
while(!heap.isEmpty()){
/**I cannot use iterator, since iterator doesn't obey the priority order. Instead, I need to use a temp heap to hold all of them.*/
Queue<Map.Entry<Character, Integer>> temp = new PriorityQueue();
while(!heap.isEmpty() && q.contains(heap.peek().getKey())) temp.offer(heap.poll());
Map.Entry<Character, Integer> curr = heap.poll();
if(curr.getValue()-1 == 0) map.remove(curr.getKey());
else map.put(curr.getKey(), curr.getValue()-1);
q.offer(curr.getKey());
if(q.size() >= k ){
//the head of the q should be un-freezed and good to append now
char c = q.poll();
if(map.containsKey(c)){
heap.offer(new AbstractMap.SimpleEntry<Character, Integer>(c, map.get(c)));
}
}
while(!temp.isEmpty()) heap.offer(temp.poll());
sb.append(curr.getKey());
}
if(!map.isEmpty()) return "";
return sb.toString();
}

Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/

This is a typical heap problem, I’m really glad that I figured out it’s heap myself before clicking its Tag tab, cheers!

My idea:

  • Use heap (a priority queue) to keep removing the most left one from the heap: remove() method in PriorityQueue
  • Once you figured out the appropriate data structure, the HARD problem instantly becomes EASY. Cheers!

public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0 || k == 0) return new int[0];
Queue<Integer> heap = new PriorityQueue<Integer>(new Comparator<Integer>(){

@Override
public int compare(Integer o1, Integer o2) {
if(o1 > o2) return -1;
else if(o1 < o2) return 1;
else return 0;
}

}
);
int i = 0;
for(; i < k; i++){
heap.offer(nums[i]);
}
List<Integer> list = new ArrayList<Integer>();
list.add(heap.peek());
for(; i < nums.length; i++){
heap.remove(nums[i-k]);
heap.offer(nums[i]);
list.add(heap.peek());
}
int[] res = new int[list.size()];
for(int j = 0; j < list.size(); j++){
res[j] = list.get(j);
}
return res;
}

Merge K Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/

Inspired by this post: https://discuss.leetcode.com/topic/2780/a-java-solution-based-on-priority-queue

Pretty typical Heap problem/solution, although I still don’t understand what k sorted means.


public ListNode mergeKLists(ListNode[] lists) {

Queue<ListNode> heap = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
@Override
public int compare(ListNode o1, ListNode o2) {
if(o1.val > o2.val) return 1;
else if(o1.val < o2.val) return -1;
else return 0;
}
});

for(ListNode node : lists){
if(node != null) heap.offer(node);
}

ListNode head = new ListNode(Integer.MIN_VALUE);
ListNode temp = head;
while(!heap.isEmpty()){
temp.next = heap.poll();
temp = temp.next;
if(temp.next != null) heap.offer(temp.next);
}
return head.next;

}

 

Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

This video is super clear and helpful: https://www.youtube.com/watch?v=GSBLe8cKu0s

  •  Algorithm:
    • First observation: all the points in the final result come from the four angles that each building has
    • Scan through the horizontal lines
    • Use a PriorityQueue to hold each building, and make the PriorityQueue to sort on the height of the buildings
    • whenever we encounter the start of a building, we push it into the PriorityQueue, whenever we finished scanning that building, we remove it from the PriorityQueue
    • Also, in the scan process, we’ll keep updating the maxHeight in the PriorityQueue if we find a new maxHeight which means the building will be overshadowed by the new higher one

 

  • Three edge cases (see the graph illustration in the above video at 12’18”):
    1. when two buildings have the same start point, the one with higher height shows up in the final result
    2. when two buildings have the same end point, the one with higher height shows up in the final result
    3. when the start point of one building is is also the end point of another building, the one with higher height shows up in the final result

 

  •  We use TreeMap over a normal PriorityQueue:
    • For the sake of efficiency (better time complexity), we’ll use TreeMap which supports O(logn) for remove() operation, this is the reason we choose TreeMap over a normal PriorityQueue in Java (PriorityQueue supports add() and getMaxVal() in both O(logn) time, however, for remove(), it does NOT.)
    • But TreeMap in Java supports all the three operations in O(logn) time.

 

public List<int[]> getSkyline(int[][] buildings) {

//construct a new array and its length should be buildings.length*2, since each building will have two BuildingPoint
BuldingPoint[] bps = new BuldingPoint[buildings.length*2];
int index = 0;
for(int[] building : buildings){
BuldingPoint startPoint = new BuldingPoint(building[0], true, building[2]);
BuldingPoint endPoint = new BuldingPoint(building[1], false, building[2]);
bps[index] = startPoint;
bps[index+1] = endPoint;
index += 2;
}
Arrays.sort(bps);

List<int[]> res = new ArrayList<int[]>();
TreeMap<Integer, Integer> map = new TreeMap();//we use height as the key, number of times this height appears as the value
map.put(0, 1);//this line is very helpful in initializing the map, although it doesn't mean anything: or you could say it means height zero appears once
int prevMaxHeight = 0;
for(BuldingPoint bp : bps){
//if it's a start point, then we add the height into the map, if it's already there, we just increment its count
if(bp.isStart){
if(map.containsKey(bp.height)) map.put(bp.height, (map.get(bp.height)+1));
else map.put(bp.height, 1);
}

//if it's an end point, then we remove its heigh from the map or decrement it count by 1 if it's greater than 1
else if(!bp.isStart){
if(map.containsKey(bp.height) && map.get(bp.height) > 1) map.put(bp.height, (map.get(bp.height)-1));
else map.remove(bp.height);
}

int currentMaxHeight = map.lastKey();
//this comment is another key for this algorithm: if maxHeight changes, that means this buildingPoint is a critical one, so we need to add it to final result
if(currentMaxHeight != prevMaxHeight){
res.add(new int[]{bp.x, currentMaxHeight});
prevMaxHeight = currentMaxHeight;
}
}

return res;

}

class BuldingPoint implements Comparable<BuldingPoint>{
int x;
boolean isStart;
int height;

public BuldingPoint(int x, boolean isStart, int height){
this.x = x;
this.isStart = isStart;
this.height = height;
}

@Override
public int compareTo(BuldingPoint o) {
/**Comparision logic:
* if x are different, then use x
* if x are the same, then:
* if both are start points, then the one with higher height wins
* if both are end points, then the one with lower height wins
* if one is start point, the other is end point, then the start point wins
* */
if(this.x != o.x){
return this.x - o.x;
} else {
return (this.isStart ? -this.height : this.height) - (o.isStart ? -o.height : o.height);
}
}
}