Saturday, 27 March 2021

Java Program To Sort A Linked List

Here is the fully working Java code solution for sorting a Linked List. You can find the same problem as an exercise in LeetCode. I have used Merge Sort here. The expectation here is that the code should run in O(n log n) time complexity and space complexity should be O(1).

The below java program manages to do it within the same complexity limit.

If you see the code, we are dividing the LinkedList in halves with each recursive call. So recursion tree height would be log n. For each of these recursive step, we are finding the middle element of the current linked list which requires a full traversal. So it would be O(n). And we are merging sub lists in each recursive step which will again take O(n) (our merge() method is linear complexity). So worst case time complexity is (n + n) * log n = O(n logn).

Regarding space complexity, I am not creating any additional Linked List for merging and doing the merge in place by changing the pointers. Only four additional variables are used in merge step and that is fixed. So if we omit the space taken by recursion stack, we are using constant space. So space complexity is O(1).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.*;
import java.lang.*;
import java.io.*;


// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next)
    { this.val = val; this.next = next; }
}
 
class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    
    public ListNode mergeSort(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode middle = findMiddle(head);
        ListNode nextToMiddle = middle.next;
        middle.next = null;
        //sort left hand side array
        ListNode leftHead = mergeSort(head);
        //sort right hand side array
        ListNode rightHead = mergeSort(nextToMiddle);
        return merge(leftHead, rightHead);
    }
    
    public ListNode merge(ListNode left, ListNode right){
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        
        ListNode leftTemp = left;
        ListNode rightTemp = right;
        
        int count = 0;
        while(leftTemp != null && rightTemp != null){
            if(leftTemp.val <= rightTemp.val){
                tail.next = leftTemp;
                leftTemp = leftTemp.next;
            } else {
                tail.next = rightTemp;
                rightTemp = rightTemp.next;
            }
            tail = tail.next;
        }
        
        if(leftTemp == null){
            tail.next = rightTemp;
        } else {
            tail.next = leftTemp;
        }
        return dummyHead.next;
    }
    
    public ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Monday, 22 March 2021

QuickSort Implementation In Java

This is a working solution of Quick Sort algorithm in Java. I haven't written the main method. You can add it & call quickSort(arr, 0, arr.length - 1) with your custom input array. Hope this Java program is self-explanatory.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
import java.lang.*;
import java.io.*;


class Solution
{
    //Function to sort an array using quick sort algorithm.
    static void quickSort(int arr[], int low, int high)
    {
        if(low >= high){
            return;
        }
        int sortedIndex = partition(arr, low, high);
        quickSort(arr, low, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, high);
    }
    
    static int partition(int arr[], int low, int high)
    {
        int pivot = high;
       
        /* keeps track of the current index where left-hand side
        elements are less than pivot element*/
        int index = low;
       
        for(int i=low; i < high; i++){
            if(arr[i] < arr[pivot]){
                swap(arr, i, index);
                index++;
            }
        }
       
        swap(arr, pivot, index);
        return index;
    }
    
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Sunday, 21 March 2021

Working Merge Sort Implementation In Java

 Here is the fully working solution of Merge Sort written in Java.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
import java.lang.*;
import java.io.*;


class Solution
{
    void merge(int arr[], int l, int m, int r)
    {
        int[] leftArr = new int[m - l + 1];
        int[] rightArr = new int[r - m];
        for(int i=l; i<= m; i++){
            leftArr[i-l] = arr[i];
        }
        for(int i=m+1; i<=r; i++){
            rightArr[i-(m+1)] = arr[i];
        }
        int x = 0;
        int y = 0;
        int i = l;
        while(x < leftArr.length && y < rightArr.length){
            if(leftArr[x] > rightArr[y]){
                arr[i] = rightArr[y];
                y++;
            } else {
                arr[i] = leftArr[x];
                x++;
            }
            i++;
        }
        while(x < leftArr.length){
            arr[i] = leftArr[x];
            x++;
            i++;
        }
        while(y < rightArr.length){
            arr[i] = rightArr[y];
            y++;
            i++;
        }
    }
    void mergeSort(int arr[], int l, int r)
    {
        if(l >= r){
            return;
        }
        int m = l + (r-l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}
I didn't write the main() method intentionally. If you want, you can write a main() method & call mergeSort(arr, 0, arr.length-1) with any custom input.

Monday, 15 March 2021

How to Check Git Commit History Of A Particular Line In Eclipse

Suppose you want to check Git commit history of a specific line from a Java class file or for that matter any other source code. You need to check who did that & figure out if any JIRA ticket is associated in the commit message. You don't want to scan through all the commit history of that file as you don't know when the line was changed, There is a simple solution in Eclipse. Just right click on the source file & select Team -> Show Revision Information .  And that should be it. Now you can click on the line number on the left side and it will show revision history of that.



Friday, 12 March 2021

What Is The Best Online JSON Formatter And Viewer

I have tried out several JSON viewer websites and most of them do a decent job in formatting & parsing JSON string. JSONLint is pretty popular. But I have had issues with them when file size goes beyond 3-4 mb. It becomes unresponsive & browser hangs. Most likely they have issue with the JavaScript code that does the JSON text processing. http://jsonviewer.stack.hu is my favourite one.  I mostly use this website to validate & format JSON. It works well with big text payload. So if you have a large JSON string to validate, it can be useful. Their JSON viewer UI is pretty good. It can display JSON in collapsible tree structure.



A Better Online Tool To Draw Sequence Diagram Using Text

I already wrote a post regarding a free tool for drawing sequence diagram by typing just text. But it lacked few features. Basically few days back, I was looking for some frame or boundary element that I can use to logically group some participants. I won't say this requirement is part of standard UML sequence diagram elements. But it's needed when you are working with too many objects. And sequence diagram will have more visual clarity if you can define few logical division between different subsystems.



sequencediagram.org came to the rescue. I even have Lucidchart account. But their sequence diagram markup language is pretty limited in option. Even my earlier post was better to draw a sequence diagram if you are planning to write some text & just get it done with (Obviously Lucidchart can do a lot more things than drawing a sequence diagram from input text).
So feel free to try this new one out & check the syntax for different options & features.

Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...