Questions on Arrays Part-3

Q12. Merge two sorted arrays without using any extra space. Assume one array to have two times space so that merging can be performed.

A12. We will use two pointer approach to this question. One pointer for the first array and a second for the second array. Iterating through the arrays we will compare the values of both and add the one which is suitable for the sorting manner to be retained.

public class MergeTwoSortedArr{
    static void merge(int[] arr1, int m, int[] arr2, int n){
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        while(j>=0){
            if(i<0 || arr1[i] < arr2[j]){
                arr1[k--] = arr2[j--]; }
            else{
                arr1[k--] = arr1[i--]; }
        }
    }
}

The time complexity is O(n) and the space complexity is O(1).

Q13. You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

A13. In this question, we will take two variables, the current value of stock assumed to be too high and the profit. We will iterate through the loop, and for each iteration, we will check if the current stock value is too high compared to that day, if yes we will change the current value to that day's stock value. If it's not we will check if the current day value minus the current stock price is larger than the profit we were getting before. If yes then we will choose those days and profit will be maximum.

public class BuySellStock{
    static int maxProfit(int[] stock){
        int current = Integer.MAX_VALUE;
        int profit = 0;
        for(int i =0; i<stock.length; i++){
            if(current> stock[i]){
                current = stock[i]; }
            else if(stock[i] - current > profit){
                profit = stock[i] - current; }
        }
    return profit;
    } 
}

The time complexity of this is O(n) and the space complexity is O(1).

Q14. Find the next permutation of an array.

A14. In this question, we will run the loop from the end of the array, until we find a break in the pattern. When we find the break, we mark that index with a temporary variable. From that index, we start a loop for the elements after it and find the one that is just larger than the one marked. We swap these two and then reverse the elements from that index till the end.

public class NextPermutation {
    static void permutation(int[] a){
        int index = -1;
        int n = a.length-1;
        for(int i=n; i>0; i--){
            if(a[i]>a[i-1]){
                index = i;
                break;
            }
        }
        if(index==-1){
            Collections.reverse(Arrays.asList(a));
        }
        else{
            int prev = index;
            for(int i= index+1; i<=n;i++){
                if(a[i]>a[index-1] && a[i]<=a[prev]){
                    prev = i;
                }
            }
            int temp;
            temp = a[index-1];
            a[index-1] = a[prev];
            a[prev] = temp;

            int start = index, end = n;
            while(start<=end){
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
                start++;
                end--;
            }
        }
        System.out.println(Arrays.toString(a));
    }

The time complexity of this algorithm is O(n) and the space complexity is O(1).

Q15. Given an array, find its inversion count.

A15. The inversion count of an array means, how far is the array from being sorted, i.e. how many inversions would it take the array to be sorted. So for this, we use an efficient sorting algorithm, and in each iteration, we increment a counter.

public class CountInversion {
    public static void main(String[] args) {
        int[] arr = {1,4,5,2,6};
        int temp, count=0;
        for(int i=arr.length-1; i>0; i--){
            if(arr[i]< arr[i-1]){
                temp = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = temp;
                count++;
            }
        }
        System.out.println(count);
    }
}

The time complexity is O(n) and the space complexity is O(1).

Q16. Given an array of integers & a target, return the indices of two numbers such that they add up to the target.

A16. There are two approaches to this question. One is direct but with higher time complexity by using two loops and summing up two elements at a time. The second is to use HashMap which gives us O(n) complexity.

public class TwoSum{
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                result[1] = i;
                result[0] = map.get(target - numbers[i]);
                return result;
                }
            map.put(numbers[i], i);
        }
    return result;
    }
}

The time complexity is O(n) and the space complexity is O(n) also.