Monthly Archives: January 2015

Queue with min and max value

I’ve read the Queue with min and max value code from Junmin Liu link. The one he mentioned is really good idea. It uses 2 stacks to keep the min/max for queue.
This problem is orignated from the count bound sliced problem. For that problem, I used another way to implement. By that, I can evolve it to another way of implementation queue with min/max. As I mentioned before, this min/max value is similar to the sliding window problem. Just evolve it with another min value.
I would say, both are good idea for queue with min/max.
2 queues solution should always change the queues more than 1 time operaiton. There is no constant O(1) time enqueue and dequeue.
2 stacks solution can always take O(1) time for enqueue and dequeue. But disadvantage is that there would be sometime that it takes O(n) for dequeue.
Here is my code:

  1. package util;
  2. import java.util.LinkedList;
  3. public class MQueue2 {
  4.     private LinkedList<Integer> q = new LinkedList<Integer>();
  5.     private LinkedList<Integer> maxq = new LinkedList<Integer>();
  6.     private LinkedList<Integer> minq = new LinkedList<Integer>();
  7.     public boolean enQueue(int e){
  8.         enMaxq(e);
  9.         enMinq(e);
  10.         q.addLast(e);
  11.         return true;
  12.     }
  13.     public int deQueue(){
  14.         if(q.size()<1){
  15.             return Integer.MIN_VALUE;
  16.         }
  17.         int curr = q.removeFirst();
  18.         deMaxq(curr);
  19.         deMinq(curr);
  20.         return curr;
  21.     }
  22.     private void enMaxq(int e){
  23.         if(maxq.size()==0){
  24.             maxq.addLast(e);
  25.             return;
  26.         }
  27.         int curr = maxq.getLast();
  28.         while(e>curr&&maxq.size()>0){
  29.             maxq.removeLast();
  30.             if(maxq.size()<1){
  31.                 break;
  32.             }
  33.             curr = maxq.getLast();
  34.         }
  35.         maxq.addLast(e);
  36.     }
  37.     private void deMaxq(int e){
  38.         if(maxq.size()<1){
  39.             return;
  40.         }
  41.         int curr = maxq.getFirst();
  42.         if(e==curr){
  43.             maxq.removeFirst();
  44.         }
  45.     }
  46.     private void enMinq(int e){
  47.         if(minq.size()==0){
  48.             minq.addLast(e);
  49.             return;
  50.         }
  51.         int curr = minq.getLast();
  52.         while(e<curr&&minq.size()>0){
  53.             minq.removeLast();
  54.             if(minq.size()<1){
  55.                 break;
  56.             }
  57.             curr = minq.getLast();
  58.         }
  59.         minq.addLast(e);
  60.     }
  61.     private void deMinq(int e){
  62.         if(minq.size()<1){
  63.             return;
  64.         }
  65.         int curr = minq.getFirst();
  66.         if(e==curr){
  67.             minq.removeFirst();
  68.         }
  69.     }
  70.     public int min(){
  71.         if(minq.size()<1){
  72.             return Integer.MAX_VALUE;
  73.         }
  74.         return minq.getFirst();
  75.     }
  76.     public int max(){
  77.         if(maxq.size()<1){
  78.             return Integer.MIN_VALUE;
  79.         }
  80.         return maxq.getFirst();
  81.     }
  82. }

I also attach Junmin Liu’s code:

  1. package util;
  2. import java.util.Stack;
  3. //a queue(FIFO) can track min and max of all elements in amortized O(1) time
  4. public class MQueue {
  5.     MStack s_new = new MStack(), s_old = new MStack();
  6.     public void enqueue(int i) {
  7.         s_new.push(i);
  8.     }
  9.     public int dequeue() {
  10.         if (s_old.isEmpty()) {
  11.             while (!s_new.isEmpty()) {
  12.                 s_old.push(s_new.pop());
  13.             }
  14.         }
  15.         return s_old.pop();
  16.     }
  17.     public boolean isEmpty() {
  18.         return s_new.isEmpty() && s_old.isEmpty();
  19.     }
  20.     public int min() {
  21.         return Math.min(s_new.min(), s_old.min());
  22.     }
  23.     public int max() {
  24.         return Math.max(s_new.max(), s_old.max());
  25.     }
  26. }
  27. // a stack node which contains min and max of all underlying elements
  28. class MNode {
  29.     Integer i, min, max;
  30.     MNode(int i, int max, int min) {
  31.         this.i = i;
  32.         this.max = max;
  33.         this.min = min;
  34.     }
  35. }
  36. // a stack(LIFO) can track min and max of all elements in amortized O(1) time
  37. class MStack {
  38.     Stack<MNode> s = new Stack<MNode>();
  39.     public boolean isEmpty() {
  40.         return s.isEmpty();
  41.     }
  42.     public int min() {
  43.         if (s.isEmpty())
  44.             return Integer.MAX_VALUE;
  45.         return s.peek().min;
  46.     }
  47.     public int max() {
  48.         if (s.isEmpty())
  49.             return Integer.MIN_VALUE;
  50.         return s.peek().max;
  51.     }
  52.     public void push(int i) {
  53.         int max = Math.max(i, max());
  54.         int min = Math.min(i, min());
  55.         s.push(new MNode(i, max, min));
  56.     }
  57.     public int pop() {
  58.         System.out.println(s.peek().i);
  59.         return s.pop().i;
  60.     }
  61. }

Find order of characters in alien language

This is a very interesting question from geeksforgeek. link
Problem: Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.
Example
Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”}
Output: Order of characters is ‘b’, ‘d’, ‘a’, ‘c’ Note that words are sorted and in the given language “baa” comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly we can find other orders.

Solution:
For “baa”, “abcd”, “abca”, “cab”, “cad”, we can conclude: b->a, a->c
For “abcd”, “abca”, we can conclude: d->a
For “cab”, “cad”, we can conclude: b->d
Then do topological sorting on it.

Lowest cost to adjust integer array, adjacencies differ less than k

This problem frustrates me for a long time. Yesterday, I finally comprehended. Cheers!

Problem: Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number k. If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|.

Solution: Find the max and min in A. So we know each of element, it is obvious to know that their change should be within [min, max]. So let’s say see A[0]. We change it to every number between [min, max], and record the cost.
Go to A[1]. We change A[1] to every number between [min,max]. It has a cost by itself. Besides, we should consider the cost from A[0]. Let’s say A[1] want to change to a certain number B[1]=bi, and b1 is between [min,max]. So, before b1, the A[0] could range from [b1-k,b1+k]. We want to choose the minimum cost. So the minimum cost of bi equals min{cost of A[0] changing to bi-k, cost of A[0] changing to bi-k+1,…,cost of A[0] changing to bi,…,cost of A[0] changing to bi+k} + (cost of A[1] changing to bi).
Then, we iterate A[2], A[3] and so on.
It requires a matrix to store it. Let’s say it is DP[max-min][A.length].
DP[i][j] means the minimum cost of changing A[0,…,j] to the target series when we changee A[j] to i.

Take the following as example, it is from careercup link:
On each number from the first to last, calculate the total cost up to this number with the ending number. Thus we calculate a matrix with column as the order of the number, row as ending number, cell value as a pair of total cost so far and row number of previous column to reach this cell(for path). The cell with the lowest cost in the last column is the result. From that cell, we can get the cell on each column to reach this last cell. The row and column indices for cells on the path make the result sequences.
For example:
input : 1, 4, 2, 3
matrix:
1 2 3 4
1 (0, -1) (3, 1) (4, 1) (6, 1)
2 (1, -1) (2, 1) (2, 2) (3, 2)
3 (2, -1) (2, 2) (3, 2) (2, 2)
4 (3, -1) (2, 3) (4, 3) (4, 3)
So the last cell[3,4] has lowest cost of 2, the previous cell is [2,3] with cost 2, then previous is [2,2] with cost 2 and then [1,1]. The result sequence is ( 1, 2, 2, 3) . This result has the same cost as the sequence of (2,3,2,3).

Count bounded slices 2 – O(n) solution

This is the O(n) solution, without result permutation output. Thanks to the answer from careerup link. I wrote my understanding and analysis.
The basic idea is that we start with arr[0] and then see how many more elements you can include before you violate the max-min<=k constraint. When it reaches some index ‘end’ you can no longer include, you know the maximum subarray starting at index 0 is arr[0…end-1], and you can count ‘end’ different subarrays there. You then already know arr[1…end-1] is valid, and you try to advance the right boundary again (try arr[1…end], then arr[1…end+1]) and so on until again you reach a point ‘front’ past which you can’t advance. Then you’ll try subarrays starting with index 2, and so on.
In order to simplify the output, I just output the range of subarrays. The final result are the permutation of them. If we consider about result output, it may take more than O(n) time.
Let’s take following example:



My code:

  1. import java.util.ArrayList;
  2. public class CountBoundedSlices2 {
  3.     public static void main(String[] args) {
  4.         int[] arr = {1, 3, 2, 4, 5, 1, 6, 7, 9};
  5.         countBoundedSlices(arr, 4);
  6.     }
  8.     public static void countBoundedSlices(int[] arr, int k){
  9.         //initial maxQueue and minQueue.
  10.         int front=0, end=1;
  11.         BoundedSlicesSData frontElem = new BoundedSlicesSData(arr[front],front);
  12.         BoundedSlicesSData endElem = new BoundedSlicesSData(arr[end],end);
  13.         ArrayList < BoundedSlicesSData> maxQueue = new ArrayList< BoundedSlicesSData>();
  14.         ArrayList < BoundedSlicesSData> minQueue = new ArrayList< BoundedSlicesSData>();
  15.         addToMaxQueue(maxQueue, frontElem);
  16.         addToMaxQueue(maxQueue, endElem);
  17.         addToMinQueue(minQueue, frontElem);
  18.         addToMinQueue(minQueue, endElem);
  19.         //The following elements are recorded to check max-min < k
  20.         BoundedSlicesSData maxElem = maxQueue.get(0);    //indicate the max element.
  21.         BoundedSlicesSData minElem = minQueue.get(0);    //indicate the min element.
  22.         for(;front < arr.length&&end+1 < arr.length;front++){
  23.             //delete elements from front which has position less than front.
  24.             while(maxElem.position < front){
  25.                 maxQueue.remove(0);
  26.                 maxElem = maxQueue.get(0);
  27.             }
  28.             while(minElem.position < front){
  29.                 minQueue.remove(0);
  30.                 minElem = minQueue.get(0);
  31.             }
  32.             //move end forward until max-min < k
  33.             while(front < arr.length&&end+1 < arr.length&&((maxElem.value-minElem.value < k)||front==end)){
  34.                 end++;
  35.                 endElem = new BoundedSlicesSData(arr[end], end);
  36.                 addToMaxQueue(maxQueue, endElem);
  37.                 addToMinQueue(minQueue, endElem);
  38.                 maxElem = maxQueue.get(0);
  39.                 minElem = minQueue.get(0);
  40.             }
  41.             if(front!=end-1){
  42.                 System.out.println(“(“+front+”,”+(end-1)+”)”);
  43.             }
  44.             if(end==arr.length-1){    //to get the last result
  45.                 System.out.println(“(“+front+”,”+end+”)”);
  46.             }
  47.         }
  48.     }
  50.     /*
  51.      * Add a new element to min queue. Keep the min quene with ascend sequence.
  52.      */
  53.     public static void addToMinQueue(ArrayList < BoundedSlicesSData> queue, BoundedSlicesSData newElement){
  54.         if(queue.size()==0){
  55.             queue.add(newElement);
  56.             return;
  57.         }
  58.         BoundedSlicesSData front = queue.get(0);
  59.         if(newElement.value < front.value){    //new element is smaller than the front. Clear queue and add it.
  60.             queue.clear();
  61.             queue.add(newElement);
  62.             return;
  63.         }
  64.         BoundedSlicesSData end = queue.get(queue.size()-1);
  65.          /* Or delete those elements which are larger than new element from end of queue.
  66.          * And add new element to the queue. */
  67.         while(end.value>=newElement.value){
  68.             queue.remove(queue.size()-1);
  69.             end = queue.get(queue.size()-1);
  70.         }
  71.         queue.add(newElement);
  72.     }
  74.     /*
  75.      * Add a new element to max queue. Keep the min quene with descend sequence.
  76.      */
  77.     public static void addToMaxQueue(ArrayList < BoundedSlicesSData> queue, BoundedSlicesSData newElement){
  78.         if(queue.size()==0){
  79.             queue.add(newElement);
  80.             return;
  81.         }
  82.         BoundedSlicesSData front = queue.get(0);
  83.         if(newElement.value>front.value){    //new element is larger than the front. Clear queue and add it.
  84.             queue.clear();
  85.             queue.add(newElement);
  86.             return;
  87.         }
  88.         BoundedSlicesSData end = queue.get(queue.size()-1);
  89.          /* Or delete those elements which are less than new element from end of queue.
  90.          * And add new element to the queue. */
  91.         while(end.value < =newElement.value){
  92.             queue.remove(queue.size()-1);
  93.             end = queue.get(queue.size()-1);
  94.         }
  95.         queue.add(newElement);
  96.     }
  98. }
  99. /*
  100.  * The queue should store both value and position. So create this class for convinent.
  101.  */
  102. class BoundedSlicesSData{
  103.     int value;
  104.     int position;
  105.     public BoundedSlicesSData(){}
  106.     public BoundedSlicesSData(int value, int position){
  107.         this.value = value;
  108.         this.position = position;
  109.     }
  110. }

Find min sublist

This problem is given by Junmin Liu. I dicussed with him, and thought about this for 2 days, and finally came up with this the O(n) time, O(1) soluiton.

Problem:
Give a list of unsorted number, find the min window or min sublist of the list, such as if sublist is sorted, the whole list is sorted too. e.g. input 123 5433 789, output 5433, basically when 5433 is sorted, then whole list is sorted.

Idea 1: use max/min stack
use 2 stacks, which can indicate min/max value. Push all elements from right-to-left min stack. And then pop from the top. When it encounters an element, where the element is larger than current min value in stack. Stop. This is the left boundary. The right boundary is similar to it, which use a max stack. Both time and space take O(n).


Idea 2: Solve by finding a certain boundary.
For arr[0,…,n-1] try to find the first element which is unsorted from left side, and first element which is unsorted from right side. Besides, we need to make sure the right side element is always larger than the left side.
So we make it into: arr[0,…,i,i+1,…,j-1,j,…,n-1].
arr[0,…,i] is ascend, and arr[i]>arr[i+1].
arr[j,…,n-1] is ascend, arr[j-1]>a[j].
And arr[i] < arr[j].
In my code, I call the i left_bound, and j right_bound. The arr[i+1,…,j-1] is the unsorted array that we met. But it is not the final result. Because inside of arr[i+1,…j-1], there could be value falling in arr[0,…,i], and value falling in arr[j,…,n-1]. We find the min and max in arr[i+1,…,j-1].
Then we use binary search find the min position in arr[0,…,min,…,i] and max position in arr[j,…,max,…,n-1]. The arr[min,…,max] list is the result. Time is O(n),space is O(1).

Below is my code. Because the boundary condition for this binary search is kinda complex, so used normal comparison. But it still gives O(n) time.

  1. public class MinSublist {
  3.     public static void main(String[] args) {
  4.         int[] arr1 = {1,2,3,4,5,4,2,3,7,8,6,9};
  5.         int[] arr2 = {1,2,3,4,5,8,2,3,7,9,8};
  6.         int[] arr3 = {1,5,2,6,5,4,3,8,6,7,8};
  7.         int[] arr4 = {1,5,2,6,5,4,3,8,4,6,5,8};
  8.         int[] arr5 = {1,2,3,5,8,2,2,3,2,7,9};
  9.         int[] arr6 = {1,2,3,5,4,3,3,7,8,9};
  10.         int[] arr7 = {1,2,3,5,4,3,3,7,8,9,2};
  11.         int[] arr = arr7;
  12.         findMinSublist(arr);
  13.     }
  15.     public static void findMinSublist(int[] arr){
  16.         Bound bound = findBound(arr);
  17.         printArray(arr, 0, arr.length-1);
  18.         MaxMinPos maxMin = findMaxMinPos(arr, bound.left_bound+1, bound.right_bound-1);
  19.         int left = getLeftPos(arr, arr[maxMin.min], bound.left_bound);
  20.         int right = getRightPos(arr, arr[maxMin.max], bound.right_bound);
  21.         System.out.println(“(“+left+”,”+right+”)”);
  22.     }
  24.     /*
  25.      * This function return a left_bound, right_bound of the arr[], where arr[0,…,left_bound], arr[right_bound,…,len-1] are ascend.
  26.      * And arr[left_bound] is less than arr[right_bound].
  27.      * The idea is to find the right value in left and right side to compare. If left_compare is larger than right_compare, we found the boundes, and stop.
  28.      * If left_bound is found, then we should always use arr[left_bound] to compare.
  29.      * If right_bound is found, then we should always use arr[right_bound] to compare.
  30.      * This function should pass the below cases:
  31.      * int[] arr1 = {1,2,3,4,5,4,2,3,7,8,6,9};
  32.      * int[] arr2 = {1,2,3,4,5,8,2,3,7,8,6,9};
  33.      * int[] arr3 = {1,5,2,6,5,4,3,8,6,7,8,9};
  34.      * int[] arr4 = {1,5,2,6,5,4,3,8,4,6,7,8,9};
  35.      * int[] arr5 = {1,2,3,5,8,2,7,6,5,2,3,4,7,9};
  36.      */
  37.     public static Bound findBound(int[] arr){
  38.         if(arr==null||arr.length<2){
  39.             return null;
  40.         }
  41.         int left_bound = 0, right_bound = arr.length-1;
  42.         boolean found_left = false, found_right = false;
  43.         while(left_bound
  44.             int left_compare, right_compare;
  45.             if(!found_left){
  46.                 if(arr[left_bound+1]
  47.                     found_left = true;
  48.                     left_compare = arr[left_bound];
  49.                 }
  50.                 else{
  51.                     left_compare = arr[left_bound+1];    //if not, current comparison is arr[left_bound+1]
  52.                 }
  53.             }
  54.             else{
  55.                 left_compare = arr[left_bound];    //already found, left_compare is the left_bound value.
  56.             }
  57.             if(!found_right){
  58.                 if(arr[right_bound-1]>arr[right_bound]){    //if right_bound is found
  59.                     found_right = true;
  60.                     right_compare = arr[right_bound];
  61.                 }
  62.                 else{
  63.                     right_compare = arr[right_bound-1];    //if not, current comparison is arr[right_bound-1]
  64.                 }
  65.             }
  66.             else{
  67.                 right_compare = arr[right_bound];    //already found, right_compare is the right_bound value.
  68.             }
  69.             if(found_left&&found_right||left_compare>right_compare){    //check if left, right bound are both found.
  70.                 break;
  71.             }
  72.             if(!found_left){
  73.                 left_bound++;    //not found, move left_bound.
  74.             }
  75.             if(!found_right){
  76.                 right_bound–;    //not found, move right_bound.
  77.             }
  78.         }
  79.         return new Bound(left_bound, right_bound);
  80.     }
  82.     /*
  83.      * Find the max, min pos in arr[]
  84.      */
  85.     public static MaxMinPos findMaxMinPos(int[] arr, int start, int end){
  86.         int max_pos = arr[start], min_pos = arr[start];
  87.         for(int i=start;i<=end;i++){
  88.             if(arr[i]
  89.                 min_pos = i;
  90.             }
  91.             if(arr[i]>arr[max_pos]){
  92.                 max_pos = i;
  93.             }
  94.         }
  95.         return new MaxMinPos(max_pos, min_pos);
  96.     }
  98.     /*
  99.      * Get the left position for final result.
  100.      */
  101.     public static int getLeftPos(int[] arr, int value, int end){
  102.         int i;
  103.         for(i=0;i<=end;i++){
  104.             if(arr[i]>value){
  105.                 break;
  106.             }
  107.         }
  108.         return i;
  109.     }
  111.     /*
  112.      * Get the right position for final result.
  113.      */
  114.     public static int getRightPos(int[] arr, int value, int start){
  115.         int i;
  116.         for(i=arr.length-1;i>=start;i–){
  117.             if(arr[i]
  118.                 break;
  119.             }
  120.         }
  121.         return i;
  122.     }
  124.     public static void printArray(int[] arr, int start, int end){
  125.         for(int i=start;i<=end;i++){
  126.             System.out.print(arr[i]);
  127.         }
  128.         System.out.println();
  129.     }
  131.     public static void printArray2(int[] arr, int left, int right){
  132.         for(int i=0;i<=left;i++){
  133.             System.out.print(arr[i]);
  134.         }
  135.         System.out.print(” “);
  136.         for(int i=left+1;i<=right-1;i++){
  137.             System.out.print(arr[i]);
  138.         }
  139.         System.out.print(” “);
  140.         for(int i=right;i<=arr.length-1;i++){
  141.             System.out.print(arr[i]);
  142.         }
  143.         System.out.println();
  144.     }
  145. }
  146. class Bound{
  147.     int left_bound;
  148.     int right_bound;
  149.     public Bound(int left_bound, int right_bound){
  150.         this.left_bound = left_bound;
  151.         this.right_bound = right_bound;
  152.     }
  153. }
  154. class MaxMinPos{
  155.     int max;
  156.     int min;
  157.     public MaxMinPos(int max, int min){
  158.         this.max = max;
  159.         this.min = min;
  160.     }
  161.     public String toString(){
  162.         return “(“+max+”,”+min+”)”;
  163.     }
  164. }