DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Edited on

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++];
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }

}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Great read:

Is it Time to go Back to the Monolith?

History repeats itself. Everything old is new again and I’ve been around long enough to see ideas discarded, rediscovered and return triumphantly to overtake the fad. In recent years SQL has made a tremendous comeback from the dead. We love relational databases all over again. I think the Monolith will have its space odyssey moment again. Microservices and serverless are trends pushed by the cloud vendors, designed to sell us more cloud computing resources.

Microservices make very little sense financially for most use cases. Yes, they can ramp down. But when they scale up, they pay the costs in dividends. The increased observability costs alone line the pockets of the “big cloud” vendors.