Arrays

MergeSort

One of the sorting algorithms with time complexity of O(nlogn) where n is the length of the given array.

///tc : O(nlogn)
//sc : O(n) for creating intermediate arrays a, b of size of part of subarray which is of size n
class Solution {
    public int[] sortArray(int[] nums) {
         merge(0,nums.length-1,nums);
         return nums;
    }
    public void merge(int start, int end, int arr[]){
        if(end>start){
            int mid = (start+end)/2;
            merge(start,mid,arr);
            merge(mid+1,end,arr);
            sort(start, mid,end, arr);
        }
    }
    public void sort(int start, int mid ,int end, int arr[]){
        int a[] = new int[mid-start+1];
        int b[] = new int[end-mid];
        for(int i = 0;i< a.length;i++){
            a[i] = arr[start+i];
        }
        for(int i= 0;i<b.length;i++){
            b[i] = arr[mid+1+i];
        }
        int i = 0;
        int j =0;
        int k = start;
        while(i<a.length && j < b.length){
            if(a[i] < b[j]){
                arr[k] = a[i++];
            }
            else{
                arr[k] = b[j++];
            }
            k++;
        }
        while(i<a.length){
            arr[k++] = a[i++];
        }
        while(j<b.length){
            arr[k++] = b[j++];
        }
    }
}

---

Inversion count

How many comparison are needed before the arrays becomes sorted ( given index i, j of array arr[] , arr[i]> arr[j] ( for j> i) will increment the inversion count by 1 every time this condition is met.

note: we can use the same merge sort approach to find the inversion count ( merge sort code have been changed a bit to make it more readable)

class Solution {
    // arr[]: Input Array
    // N : Size of the Array arr[]
    // Function to count inversions in the array.

    static long inversionCount(long arr[], int n) {
        // Your Code Here
       //we can use merge sort
       long temp[]= new long[n];
       return merge(0,n-1,arr,temp);


    }
    public static long merge(int start, int end, long arr[],long[] temp){
        long count = 0;
        if(end>start){
            int mid = (start+end)/2;
            count+=merge(start,mid,arr,temp);
            count+=merge(mid+1,end,arr,temp);
           count+=sort(start, mid,end, arr,temp);
        }
        return count;
    }
    public static long sort(int start, int mid ,int end, long arr[],long [] temp){
        long count = 0;
        int i = start;
        int j = mid+1;
        int k = start;

        while(i<=mid && j <=end){
            if(arr[i]<=arr[j]){
                temp[k] = arr[i++];
            }
            else{
                temp[k] = arr[j++];
                count+= mid-i+1; // if ( a[i] > arr[j] then all the values after ith index including will be
                // greater that jth index value hence count += mid-i+1
            }
            k++;
        }
        while(i<=mid){
            temp[k++] = arr[i++];
        }
        while(j<=end){
            temp[k++] = arr[j++];
        }
        for(int l = start;l<=end;l++){
            arr[l] = temp[l];
        }
        return count;
    }

}

---

Maximum Subarray

Note: This is based on Kadane's algorithm of finding the subarray maximum sum

//tc :O(n) where n is the length of the given array
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i =0;i<nums.length;i++){
            sum+=nums[i];
            if(sum > max){
                max = sum;
            }
            if(sum<0) sum = 0;
        }
        return max;
    }
}

---

3 Sum

• We have to make sure that duplicates are avoided, hence we to ignore nums[prev] == nums[current] then current index value needs to be avoided.

Note: We can use the same approach for 2 sum or 4 sum problems

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for(int i =0;i<n;i++){
            if(i>0 && nums[i] ==nums[i-1]) continue;
            int j = i+1;
            int k = n-1;
            while(j<k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum ==0){
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    list.add(l);
                    k--;
                    j++;
                    while(j<k && nums[k] ==nums[k+1]) k--;
                    while(j<k && nums[j] == nums[j-1]) j++;
                }
                else if(sum > 0) k--;
                else j++;
            }
        }
        return list;
    }
}