Questions on Arrays Part-2

Moving on to some more interview questions from Arrays:

Q6. Find the Union and Intersection of two arrays.

A6. There are two approaches to this question. One is the two-pointer approach and the other is using a Set. Here we will go with the two-pointer approach as in some questions there can be a condition that one should also add duplicates in the answer. So, using a set would not produce that.

// Union
int left = 0;
int right = 0;
List<Integer> union = new ArrayList<>();
while(left<arr1.length || right<arr2.length){
    // Skip Duplicates
    while(left>0 && left<arr1.length && arr1[left] == arr1[left-1]){
        left++; }
    while(right>0 && right<arr2.length && arr2[right] == arr2[right-1){
        right++; }
    // If one array is exhausted
    if(left>=arr1.length){
        union.add(arr2[right]);
        right++;
        continue; }
    if(right>=arr2.length){
        union.add(arr1[left]);
        left++;
        continue; }
    // Comparison
    if(arr1[left] < arr2[right]){
        union.add(arr1[left]);
        left++; }
    else if(arr1[left] > arr2[right]){
        union.add(arr2[right]);
        right++; }
    else{
        union.add(arr1[left]);
        left++;
        right++; }
    }
}
System.out.println(union);

// Intersection
int left = 0;
int right = 0;
List<Integer> intersection = new ArrayList<>();
while(left<arr1.length && right<arr2.length){
    // Skip Duplicates
    while(left>0 && left<arr1.length && arr1[left] == arr1[left-1]){
        left++; }
    while(right>0 && right<arr2.length && arr2[right] == arr2[right-1]){
        right++; }
    // If one array is exhausted
    if(left>=arr1.length || right>=arr2.length){
        break; } 
    // Comparison
    if(arr1[left] < arr2[right]){
        left++; }
    else if(arr1[left] > arr2[right]){
        right++; }
    else{
        intersection.add(arr1[left]);
        left++;
        right++; }
    }
}
System.out.println(intersection);

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

Q7. Rotate the array cyclically k times.

A7. For this we directly use loops. We start the loop from the second last element of the array and swap the elements for k times. The last element of the array is stored in a temporary variable and added to the start of the array after the elements are shifted and the space at the start of the array is empty.

public class RotateArr{
    public static void main(String args[]){
        int[] arr = {1,2,3,4,5,6};
        int p = 1;
        int k = 2;
        int n = arr.length;
        while(p<=k){
            int temp = arr[n-1];
            for(int i = n-2; i>=0; i--){
                arr[i+1] = arr[i];
            }
            arr[0] = temp;
            p++;
        }
      }
    }
}

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

Q8. Find the maximum subarray sum of an array.

A8. There are two approaches to this problem, one is simple i.e. run two loops & for every subarray check if it is the max sum possible. The other is by using Kadane's Algorithm i.e. for every subarray we will have two variables, one will be the current sum variable and the other will be the max sum. After each iteration of the loop, we will check if the current sum is larger than the max sum so far. If it is negative we will reset the sum to 0.

public class LargestSumContiguousSubArr{
    public static void main(String[] args){
        // Direct Approach
        int[] arr = {1,2,-4,3,5,6};
        int sum = 0, max_sum = Integer.MIN_VALUE;
        for(int i=0; i < arr.length; i++){
            for(int j =i; j<arr.length; j++){
                sum = sum + arr[j];
                if(max_sum<sum)
                    max_sum = sum; 
            } sum = 0;
        }
        // Kadane's Algorithm
        sum = 0;
        max_sum = Integer.MIN_VALUE;
        for(int j: arr){
            sum = sum + j;
            if(max_sum<sum)
                max_sum = sum;
            if(sum<0)
                sum = 0;
        }
    }
}

The time complexity of the direct approach is O(n^2) whereas using Kadane's Algorithm its O(n) and the space complexity is O(1).

Q9. Minimise the maximum difference in the heights of towers. For each tower, you must perform exactly one of the following operations exactly once. Increase the height of the tower by K Decrease the height of the tower by K. Find out the minimum possible difference between the height of the shortest and tallest towers after you have modified each tower.

A9. In this question, we take three variables, diff, max and min. We initialize diff as the difference between the last and the first tower. Looping through the array, if subtracting k from any tower leads to -ve height, we move to the next tower. For each tower, we calculate the max and min heights and the difference. For max height, we maximise using Math.max function applied between the towers in which k is added and the other in which from the last tower k is subtracted. For min-height, we minimise using Math.min function applied between the towers in which k is subtracted and added to the first tower. In each iteration, we find the difference again and choose the minimum one.

public class MinimiseMaxDifferenceOfHeights {
    static int minimise(int[] a, int n, int k){
        if(n==1){
            return 0;
        }
        int diff = a[n-1] - a[0];
        int min, max;
        for(int i=1 ; i<n; i++){
            if(a[i]-k<0){
                continue;
            }
            max = Math.max(a[i-1]+k, a[n-1]-k);
            min = Math.min(a[0]+k, a[i]-k);
            diff= Math.min(max-min, diff);
        }
       return diff;
    }

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

Q10. You are given an integer array. You are initially at the first index & each element in the array represents your maximum jump length in that position. Return the minimum number of jumps required to reach the end of the array.

A10. In this question we can see, each element signifies the max steps it can take to some other element, for example, if the first element is 3, it can move a maximum of 3 steps or indices forward. And if we move, it means we took a jump. According to this, we need to find the minimum amount of jumps needed to reach the end of the given array.

public class MinNoOfJumpsToReachEndOfArr{
    static int MinNoOfJumps(int[] a, int n){
        if(n<=1){
            return 0; }
        int max = a[0];
        int steps = a[0];
        int jumps = 1;
        for(int i=1; i<n;i++){
            if(i+a[i]>max)
                max = i+a[i];
            steps--;
            if(steps==0){
                jumps++;
                steps = max - i; }
        }
    return jumps; }
}

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

Q11. Find a duplicate number in the array.

A11. There can be various approaches to this question. First is brute force, where we take an element one by one from the array and compare it with all the other elements of the array until we find the one which is equal to it. The second approach can be the count array, we take an array list and store the frequencies of each element if the element value is equal to the index. If the frequency is larger than one it concludes the duplicacy. The third and optimal approach is the negative indexing approach, in which we iterate through the array and convert each index value to its negative value. If we strike across the duplicate, the value of that index will be already negative hence revealing it.

public class DuplicateInArr{
    public static void main(String args[]){
        int[] arr = {1,2,3,4,2,5};
        int dup = 0;
        for(int i=0; i<arr.length; i++){
            int index = Math.abs(arr[i]);
            if(arr[index]<0){
                dup = arr[index];   }
            arr[index] = -arr[index];
        }
        System.out.println(dup);
    }
}

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