DSA Questions on Arrays Part-1.

Now we will understand the different types of questions on Arrays.

Q1. Write a program to reverse an array.

A1. There are two ways to approach this problem. One is an iterative way and the other is the recursive way.

In an iterative way, we will use a while loop, with a start pointer at the start of the array and an end pointer at the end of the array. Iterating using a while loop, we swap the values of start and end pointers. After each iteration, we increment and decrement the start and end pointers respectively.

// Iterative way
public class ReverseArr{
    static void rev(int[] a, int start, int end){
            int temp;
            while(start<end){
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
                start++;
                end--;
             }
       }
}

Recursively, we use the base condition as start>=end and return, and recursively swap the values of the start and end pointer, calling the function recursively decrementing and incrementing the end and start values respectively in the function parameters.

// Recursive way
public class ReverseArr{
    static void rev(int[] a, int start, int end){
        if(start>=end){
            return;
        }
        int temp;
        temp = a[start];
        a[start] = a[end];
        a[end] = temp;
        rev(a,start+1,end-1);
    }
}

The time complexity of this algorithm is O(n) as we are iterating through the whole array. The space complexity is O(1) as no extra space is used.

Q2. Find the maximum and minimum elements in the array.

A2. There is a direct iterative approach to this question. Taking two variables as max and min, initialising them with the first two array values temporarily, we iterate through the loop and compare each value with min or the max value, using if else conditionals.

public class MaxMinArr{
    static void maxMin(int[] a){
            int max,min;
            if(a[0]>a[1]){
                max = a[0];
                min = a[1];
            }
            else{
                max = a[1];
                min = a[0];
            }
            for(int i=2; i<a.length; i++){
                if(a[i]>max){
                    max = a[i];
                }
                else if(a[i]<min){
                    min = a[i];
                }
            }
    }
}

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

Q3. Find the kth max and min elements in an array.

A3. In this question, if the array is not sorted we first sort the array using an efficient sorting method. After that, we directly access the array element using the given value of k in the question, i.e. Maximum element will be a[a.length - k] and the Minimum element will be a[k-1].

So the time complexity of this algorithm will depend on the type of sorting algorithm we use. Or we can directly use the sorting method in the Array package of Java.

import.java.util.*;
public class KthMaxMin{
    static void kthmaxmin(int[] a, int k){
        Arrays.sort(a);
        System.out.println("The kth max element in the array is" +           a[a.length - k] );
        System.out.println("The kth min element in the array is" + a[k - 1] );
    }
}

Q4. Move all negative numbers to one side of the array and all positive numbers to the other side.

A4. In this question, we directly apply an efficient sorting technique to get the answer.

public class SortNegPosArr{
    static void sortnegpos(int[] a){
        // Using QuickSort
        int j = 0, temp = 0;
        for(int i = 0; i<a.length; i++){
            if(a[i]<0){
                if(i!=j){
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            j++;
        }
    }
}

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

Q5. Sort the array of 0s, 1s and 2s in ascending order without using any sorting techniques.

A5. There are two ways to solve this problem, the first is to count the number of 0s, 1s and 2s in the array and add them to their respective indices using loops. But this approach is of very high time complexity. Hence the second way is more efficient i.e. the Dutch National Flag Algorithm also known as the low, middle & high technique.

Low depicts that before that index all are 0s, middle depicts 1s and high depicts that index after which all are 2s. If the middle element is 0, we swap it with a low index and increment both. Whereas if the middle element is 2, we swap it with a high index and decrement high.

public class SortArr0s1s2s{
    static void sort0s1s2s(int[] a){
        int low = 0, mid=0, high = a.length-1;
        int temp = 0;
        while(mid<=high){
            if(a[mid] == 0){
                temp = a[mid];
                a[mid] = a[low];
                a[low] = temp;
                mid++;
                low++;
            }
            else if(a[mid] == 1){
                mid++;
            }
            else{
                temp = a[mid];
                a[mid] = a[high];
                a[high] = temp;
                high--;
            }
        }
    }
}

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