Daily Archives: January 1, 2015

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