Thursday, November 3, 2016

Sorted subsequence of size n

Problem
Given an array, the task is to find n elements of this array such that they are in sorted form. Eg. For n =3 any three elements a[i], a[j] and a[k], they follow this relationship : a[i] < a[j] < a[k].

Solutions
If we have to find out the sorted sub-sequence means we need elements in incrementing order. Let's assume first element from array is less than second then we can add both elements in temp storage, if any element is less than element inserted in temp storage add this to another temp storage as new solution. We can follow this method will we get required number of elements in sorted order.
The solution below implement this approach using stack as temp storage. This solution finds out all the sorted subsequence in the array. The complexity of this solution is o(n) as we are going over all the elements not more than once. 
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class SortedSubSeq {

    public static List getSortedSubSequence(int[] input, int n){
        List> seqList = new ArrayList>();
        boolean added= false;
        for (int i : input){
            for (Stack s : seqList) {
                if (!s.empty() && s.peek() < i) {
                    s.push(i);
                    added = true;
                }
            }

            if (!added){
                Stack newSubSequence = new Stack<>();
                newSubSequence.push(i);
                seqList.add(newSubSequence);
            }
            added = false;
        }

        for (Stack s : seqList) {
            if (s.size() >= n) {
                List result = new ArrayList<>();
                result.addAll(s);
                return result;
            }
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        int[] input = {12, 11, 10, 5, 7, 6, 30};

        List result = getSortedSubSequence(input, 3);
        System.out.println("Sorted subsequence of length 3 : ");
        for (Integer i : result){
            System.out.print(i + " ");
        }
    }

}


Comments are welcome. Question source geeksforgeeks

No comments:

Post a Comment