Merge k sorted arrays

Problem

Given k sorted arrays of size n each, merge them and print the sorted output.

Solutions

This problem can be solved in multiple ways.

- Take first two arrays and merge those. Now the rest all arrays with the merge result one by one.

- We can use the min heap of size 'k'. Add one element from each array and remove smaller element from heap. Once the smaller element is removed, from the same array insert next element in to heap. This way remove all the elements from heap and put in to merge array.

- Lastly instead of maintaining heap, we can just compare one element from each array, compare min from those and add to merge result. Now take next element from same array. Follow this till all elements are sorted. Solution below implements this approach.

import java.util.ArrayList;
import java.util.List;

public class MergeKSortedArrays {
    public static void MergeSortedArrays(int[][] sortedArrays) {
        int maxSize = sortedArrays.length * sortedArrays[0].length;

        int[] mergedArray = new int[maxSize];

        List arrayIndices =  new ArrayList<>();
        for (int[] sortedArray : sortedArrays) arrayIndices.add(0);

        for (int i = 0; i < maxSize; i++){
            int minSoFar = Integer.MAX_VALUE;
            int minIndex = 0;

            for(int index = 0; index < arrayIndices.size(); index++){
                if ( sortedArrays[index].length > arrayIndices.get(index) && sortedArrays[index][arrayIndices.get(index)] < minSoFar){
                    minSoFar = sortedArrays[index][arrayIndices.get(index)];
                    minIndex = index;
                }
            }
            mergedArray[i] = sortedArrays[minIndex][arrayIndices.get(minIndex)];
            arrayIndices.set(minIndex, arrayIndices.get(minIndex) + 1);
        }

        System.out.println("Merged : ");
        for (int i : mergedArray){
            System.out.print( i + ", ");
        }
    }

    public static void main(String[] args) {

        int[][] A = new int[5][];

        A[0] = new int[] { 1, 5, 8, 9 };
        A[1] = new int[] { 2, 3, 7, 10 };
        A[2] = new int[] { 4, 6, 11, 15 };
        A[3] = new int[] { 9, 14, 16, 19 };
        A[4] = new int[] { 2, 4, 6, 9 };

        MergeSortedArrays(A);
    }
}

Comments are welcome.

Buildings which can see the sun

Problem

An array of integers is given which represents the heights of n buildings.Sun start falling from the left side. If there is a building of certain Height, all the buildings right of it having lesser heights cannot see the sun. Find the no. of buildings which can see the sun.

Solutions

Starting from we have to find the building which has same or bigger height than building on left side. Which means we have to list out local maximum in the array, which will give us the building which can see the sun.
Solution below uses an temp list for storing the local maximum so far.

import java.util.ArrayList;
import java.util.List;

public class SunViewBuilding {

    public static int GetSunViewCount(int[] buildingHeights){
        if (buildingHeights.length <= 0)
            return 0;

        List localMax = new ArrayList<>();

        localMax.add(buildingHeights[0]);
        for (int i =1;  i < buildingHeights.length; i++){
            if (localMax.get(localMax.size()-1) <= buildingHeights[i]){
                localMax.add(buildingHeights[i]);
            }
        }

        return localMax.size();
    }

    public static void main(String[] args) {
        int[] input = {12, 11, 13, 5, 30, 6, 30};
        System.out.println("Buildings which can see the sun : " + GetSunViewCount(input));
    }
}

Comments are welcome. Question source geeksforgeeks

Swap two Strings without using third user defined variable

Problem

Given two string variables a and b, swap these variables without using temporary or third variable in Java. Use of library methods is allowed.

Solutions

We can use the String Split method and a separator to separating two string. We can also do this by using the substring method. Code below implement both the solutions.

 
public class SwapWithoutVar {
    public static void main(String[] args) {
        String a = "Hello";
        String b = "World";

        //Using String Split
        SwapWithSplit(a, b);

        //Using String Substring
        SwapWithSubString(a, b);

    }

    private static void SwapWithSubString(String a, String b) {
        System.out.println(String.format("Before Swap : a - %s, b - %s", a, b));
        b = a + b;
        a = b.substring( b.indexOf(a) + a.length());
        b = b.substring(0, b.indexOf(a));
        System.out.println(String.format("After Swap : a - %s, b - %s", a, b));
    }

    private static void SwapWithSplit(String a, String b) {
        System.out.println(String.format("Before Swap : a - %s, b - %s", a, b));
        b = b + "," + a;
        a = b;
        b = b.split(",")[1];
        a = a.split(",")[0];
        System.out.println(String.format("After Swap : a - %s, b - %s", a, b));
    }
}

Comments are welcome. Question source geeksforgeeks

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