@RT42 your are right on. good explanation.
zahid2
@zahid2
Posts made by zahid2

RE: O(n) solution in Java with two simple pass in the array

RE: O(n) time O(n) space solution in Java
This is a simple premitive key type hashmap so not much collision and resizing. You are not correct when saying that hashmap lookup is skower than binary search. It's not and we shouldn't argue online about it. If you want we can discuss offline zahidbuet106@gmail.com

RE: O(n) time O(n) space solution in Java
The other solution uses o(lgn) binary search to find the matching hence it is o(nlgn) . My solution used o(1) time hashmap to find the match. Hence it is io(n). However my solution uses o(n) memory and the other solution doesn't use any extra memory. So there is always a tradeoff and I selected to go with extra memory as memory is cheap for the sake of runtime performance.

1 ms O(n) time solution in Java  dynamic sliding window
We will maintain a window that grows until sum reach the given sum. Once the window grows to sum at least s then we can start shirking the window from left with the hope to find a smaller window. We shrink until sum falls below s. Then we can grow the window on right again and so on. We keep this procedure of growingshrinking until the window start reaches the end of the array. Below is the implementation of the above idea which runs in O(n) time and O(1) space.
public class Solution { public int minSubArrayLen(int sum, int[] nums) { int minlen = Integer.MAX_VALUE; int curSum = 0; int start = 0; int end = 0; while(start < nums.length){ //if current window doesn't add up to the given sum then //strech the window to right if(curSum < sum && end < nums.length){ curSum += nums[end]; end++; } //if current window adds up to at least given sum then //we can shrink the window else if(curSum >= sum){ minlen = Math.min(minlen, endstart); curSum = nums[start]; start++; } //cur sum less than required sum but we reach the end else{ break; } } return (minlen == Integer.MAX_VALUE) ? 0 : minlen; } }

RE: 11line simple Java solution, O(n) with explanation
no need for O(n) space. Here is an O(n) time O(1) space solution using Kadane's algorithm
Idea is that, while we traverse form left to right if we see a character at position j is a duplicate of a character at a position i < j on the left then we know that we can't start the substring from i anymore. So, we need to start a new substring from i+1 position. While doing this we also need to update the length of current substring and start of current substring. Important part of this process is to make sure that we always keep the latest position of the characters we have seen so far. Below is a simple O(n) implementation of this logic.
public class Solution { public int lengthOfLongestSubstring(String s) { int lastIndices[] = new int[256]; for(int i = 0; i<256; i++){ lastIndices[i] = 1; } int maxLen = 0; int curLen = 0; int start = 0; int bestStart = 0; for(int i = 0; i<s.length(); i++){ char cur = s.charAt(i); if(lastIndices[cur] < start){ lastIndices[cur] = i; curLen++; } else{ int lastIndex = lastIndices[cur]; start = lastIndex+1; curLen = istart+1; lastIndices[cur] = i; } if(curLen > maxLen){ maxLen = curLen; bestStart = start; } } return maxLen; } }

15 ms accepted java soln using mergesort
Counting smaller on right is much easier as we just need to count how many time we are taking smaller element from right partition during merge of the merge sort process. Once we get an element from left partition that means that smaller on right for current element is the count so far.
So, With a simple modification of the merge sort code we can calculate smaller on right. The modification involves updating a rank array for the index of the array instead of modifying the array itself and counting smaller while taking element from right during merge. Overall complexity O(nlgn).
public class Solution { public List<Integer> countSmaller(int[] nums) { int n = nums.length; int[] rank = new int[n]; List<Integer> count = new ArrayList<Integer>(n); if(n == 0){ return count; } for(int i = 0; i < n; i++){ count.add(0); rank[i] = i; } countSmallerOnRightWithMerge(nums, rank, 0, n1, count); return count; } public void countSmallerOnRightWithMerge(int A[], int rank[], int p, int r, List<Integer> count){ if(A.length == 1){ return; } if(p < r){ int q = (p+r)/2; //sort left side and count ic countSmallerOnRightWithMerge(A, rank, p, q, count); //sort right side and count ic countSmallerOnRightWithMerge(A, rank, q+1, r, count); //merge left and right and count cross ic mergeToCountSmallerOnRight(A, rank, p, q, r, count); } } public void mergeToCountSmallerOnRight(int A[], int rank[], int p, int q, int r, List<Integer> count){ int n = rp+1; int i = p; int j = q+1; int mid = q; int k=0; int mergedRank[] = new int[n]; int smallerCount = 0; while(i <= mid && j <= r){ //satisfies i<j, A[i]<A[j]  so count smaller on right if(A[rank[i]] <= A[rank[j]]){ count.set(rank[i], count.get(rank[i])+smallerCount); mergedRank[k++] = rank[i++]; } //i<j, A[i]>=A[j] else{ smallerCount++; mergedRank[k++] = rank[j++]; } } //copy leftovers from the two partitions into merge while(i <= mid){ count.set(rank[i], count.get(rank[i])+(rq)); mergedRank[k++] = rank[i++]; } while(j <= r){ mergedRank[k++] = rank[j++]; } //update rank System.arraycopy(mergedRank, 0, rank, p, n); } }

RE: O(n) time O(1) space solution using Kadane's algo in Java
A constant is always O(1). Regardless of number of input n, the space is constant 256. For Thai reason space complexity is O(1). I hope this help in clarifying your confusion about algorithmic order.

50 ms accepted Java solution using MaxHeap (PQ) based on interval overlapping (explained)
The idea is to find overlapping intervals if we consider each building as an interval and the height of the building as the weight of the interval.
We can separate the left coordinates of the buildings in an array called start and sort it based on the left and the height (because if we have several buildings start from the same left then we want to take the tallest building). Similarly we separate right coordinates of the buildings in another array called end and sort it based on right.
Now, we will do a similar algorithm as we do to find overlapping intervals. We start scanning both start and end from left to right. If current start is less then prev end then it is part of the current overlap. Otherwise we find end of a set of overlapping intervals.
For each start and end points we will compute one strip as follows 
 If start point of current interval is part of current overlap then the height of the strip for this start point is the maximum height seen so far in the overlap. So, we use a max heap to maintain the max so far.
 Otherwise, we have an end of current overlap with the current end point. So, we need to remove the height of this end point from the heap as the overlap ends here. The height of the strip for this end point is the maximum of the remaining buildings in current overlap.
Finally we want to remove all the duplicate stripes (either strips with same height in subsequent positions or strips ending at same position for special case when we have many buildings ending at same right coordinate. The overall complexity is O(nlgn). This algorithm works for unsorted dataset also.
public class Solution { public List<int[]> getSkyline(int[][] buildings) { int n = buildings.length; if(n == 0){ return new ArrayList<int[]>(); } Building[] bld = new Building[n]; for(int i = 0; i<n; i++){ bld[i] = new Building(buildings[i][0],buildings[i][2],buildings[i][1]); } return skyLine(bld); } public static class Building{ int l; int h; int r; public Building(int left, int height, int right){ l = left; h = height; r = right; } } public static ArrayList<int[]> skyLine(Building[] buildings){ int n = buildings.length; Building[] start = Arrays.copyOf(buildings, n); Building[] end = Arrays.copyOf(buildings, n); PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(n, Collections.reverseOrder()); ArrayList<int[]> strips = new ArrayList<int[]>(); //sort based on left coordinate of a building i.e. start of a range Arrays.sort(start, new Comparator<Building>() { @Override public int compare(Building o1, Building o2) { int c = Integer.compare(o1.l, o2.l); if(c == 0){ c = Integer.compare(o2.h, o1.h); } return c; } }); //sort based on right coordinate of a building i.e. end of a range Arrays.sort(end, new Comparator<Building>() { @Override public int compare(Building o1, Building o2) { return Integer.compare(o1.r, o2.r); } }); int i = 0, j = 0; while(i < n  j < n){ //a new overlapping range i.e. a building if(i < n && start[i].l <= end[j].r){ //update max height seen so far in current overlap maxHeap.add(start[i].h); //max height in current overlap including the current building int maxHeightIncldingMe = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //add th current strip with the left of building and max height seen so far in currne overlap strips.add(new int[]{start[i].l, maxHeightIncldingMe}); //try next building i++; } else{ //it's an end of a range of current overlap. So, we need to remove the height //of this range i.e. building from the max heap maxHeap.remove(end[j].h); //max height of remaining buildings in current overlap int maxHeightExcldingMe = maxHeap.isEmpty() ? 0 : maxHeap.peek(); //add the current strip with the right of building and max height of remaining buildings strips.add(new int[]{end[j].r, maxHeightExcldingMe}); //update end index j++; } } //strips.add(new int[]{end[n1].r, 0}); //merge strips to remove successive strips with same height ArrayList<int[]> mergedStrips = new ArrayList<int[]>(); int prevHeight = 0; for(int[] st : strips){ if(st[0] == end[n1].r && st[1] != 0){ continue; } if(prevHeight == 0){ prevHeight = st[1]; mergedStrips.add(st); } else if(prevHeight != st[1]){ prevHeight = st[1]; mergedStrips.add(st); } } return mergedStrips; } }

Java BFS based accepted solution using Queue
Serialize:  comma separated values in BFS order.
Simply traverse the tree in BFS order and enqueue all children. In case of leaves we push special node with INF value. When we pop an item append the value of this node to string buffer unless this is a special node, in which case we append null to the buffer.Deserialize:
We start from root and start another BFS traverse to rebuild the tree. Each time we pop an item we scan 2 tokens from serialized string to get 2 child's. We create left and right child nodes for the popped node unless they are "null".public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null){ return "null"; } StringBuffer serTree = new StringBuffer(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); TreeNode node; while(!queue.isEmpty()){ node = queue.poll(); if(node.val == Integer.MIN_VALUE){ serTree.append("null,"); continue; } else{ serTree.append(node.val+","); } if(node.left != null){ queue.add(node.left); } else{ queue.add(new TreeNode(Integer.MIN_VALUE)); } if(node.right != null){ queue.add(node.right); } else{ queue.add(new TreeNode(Integer.MIN_VALUE)); } } return serTree.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data == null  data.isEmpty()  data.startsWith("null")){ return null; } String[] nodes = data.split(","); if(nodes.length == 0){ return null; } TreeNode root = new TreeNode(0); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); TreeNode node; int i = 0; while(!queue.isEmpty()){ node = queue.poll(); node.val = Integer.parseInt(nodes[node.val]); int left = i+1; int right = i+2; if(left < nodes.length1 && !nodes[left].equals("null")){ TreeNode leftNode = new TreeNode(left); node.left = leftNode; queue.add(leftNode); } if(right < nodes.length1 && !nodes[right].equals("null")){ TreeNode rightNode = new TreeNode(right); node.right = rightNode; queue.add(rightNode); } i+=2; } return root; } }

O(n) time O(1) space solution using Morris Inorder Traversal in Java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int kthSmallest(TreeNode root, int k) { TreeNode kth = MorrisInorderTraversal(root, k); return kth != null ? kth.val : 1; } public static TreeNode MorrisInorderTraversal(TreeNode root, int k){ if(root == null){ return null; } TreeNode cur = root; TreeNode pre = null; while(cur != null){ //if no left subtree the visit right subtree right away after printing current node if(cur.left == null){ k; if(k == 0){ return cur; } cur = cur.right; } else{ //otherwise we will traverse the left subtree and come back to current //node by using threaded pointer from predecessor of current node //first find the predecessor of cur pre = cur.left; while(pre.right != null && pre.right != cur){ pre = pre.right; } //threaded pointer not added  add it and go to left subtree to traverse if(pre.right == null){ pre.right = cur; cur = cur.left; } else{ //we traversed left subtree through threaded pointer and reached cur again //so revert the threaded pointer and print out current node before traversing right subtree pre.right = null; k; if(k == 0){ return cur; } //now traverse right subtree cur = cur.right; } } } return null; } }