Useful resources for Dijkstra's Algorithm

September 03, 2021

Dijkstra's algorithm

Dijkstra's algorithm shortest path algorithm is one of the most commonly used algorithms for finding short distances between two nodes. This article list down some of the important points for this algorithm and list down some of the useful contents available online.

Important Points

It does not work if the edges have negative weights. It is used to find shortest path between source and destination in a graph. Real life uses includes Map, Network communication.

Complexity

The complexity of this algorithm depends on the data structure used. For a graph G with V vertices and E edges, For Adjecency Matrix : Complexity is O(V**2) For Adjecency List and using Priority Queue with O(n) for sorting : O(E + VlogV)

References

Wikipedia
Algorithm with Visual Intro
Dijkstras Algo in Java
Dijkstras Algorithm with Java Code
Read More

Check if an array is Monotonic array in Java

August 25, 2021


An array is monotonic if it is either monotone increasing or monotone decreasing. More formally if all the elements are either in increasing order or decreasing order. That is for an given array nums[], it is monotone increasing if all i <= j, nums[i] <= nums[j]. it is monotone decreasing if for all i <= j, nums[i] >= nums[j]. In in article we will see how to efficiently decide if a given array is monotonic or not.

Examples

Examples of Monotonic arrays
Increasing monotonic array:
[1, 2, 20, 30]
[1, 2, 20, 20, 30]
decreasing monotonic array:
[66, 50, 40, 4]
[66, 50, 40, 40]

Algorithm

Iterate over the array and keep track of the first nonequal comparison to a variable signal. And once the signal is set check if holds true for the next set of array items.

Implementation

Implementation of the monotonic array is not very tough. Here we will see how to implement it in a single pass (single iteration of the input array) in Java.
MonotonicArray
Following Java, the class implement is a monotonic method that checks if an array is monotonic in a single pass.
public class MonotonicArray {
	public boolean isMonotonic(int[] nums) {
		int signal = -1; // -1 = not set, 0 = increasing, 1 = decreasing
		// iterate over the array till the arry.length-1 from 0
		for (int i = 0; i < nums.length - 1; i++) {
			// if signal is not initialized and we see either increasing or decreasing array
			// initialize it accordingly
			if (signal == -1) {
				if (nums[i] < nums[i + 1]) {
					signal = 0; // increasing
				} else if (nums[i] > nums[i + 1]) {
					signal = 1; // decreasing
				}
			} else {
				// once the signal is already initialized
				// then check if for other elements it holds true or not
				if (signal == 0 && nums[i] > nums[i + 1]) {
					return false;
				}
				if (signal == 1 && nums[i] < nums[i + 1]) {
					return false;
				}
			}
		}
		return true;
	}
}
Code Complexity
Runtime complexity: O(n) where n is the number of elements in the array. As we are iterating the array once. Space complexity: O(1) as we are not using extra storage

References

Leetcode Monotonic Array
Monotonic array In Python
Another implementation in Java
Read More

Java Convert Integer to Roman Numbers

October 26, 2020

Roman Number

Roman numerals have seven symbols. The table below shows these symbols and their decimal equivalents.

SymbolNumber
I1
V5
X10
L50
C100
D500
M1,000

Negative Numbers and Range

We cannot represent negative numbers using Roman Numbers. The largest number you can write in Roman numerals is 3,999 which is MMMCMXCIX Numbers larger than 3,999 in Roman numerals is represented using an overline. An overline on a Roman numeral means we are multiplying that Roman numeral by 1,000. For the number 50,000 in Roman numerals, you would use the Roman numeral L (50) with an overline to make it 50,000

Conversion Rules

I can be placed before V or X, represents subtract one, so IV (5-1) = 4 and 9 is IX (10-1)=9. 
X can be placed before L or C represents subtract ten, so XL (50-10) = 40 and XC (100-10)=90. 
C placed before D or M represents subtract hundred, so CD (500-100)=400 and CM (1000-100)=900. Roman numerals are usually written in highest to lowest from left to right except for some special cases where the left character is less than the right character.

Implementation

The algorithm is simple 
1) Place the roman literals in an array 
2) Place corresponding integer values (numbers) in another array maintaining the corresponding indices. 
3) Try subtracting the biggest number from the numbers array from the input value until the input is 0. 
4) Append the corresponding roman literal to output String.

ToRoman.java
The following class defines a method that accepts an integer and returns a Roman Number in the form of a String object.
 /**
   * I can be placed before V or X
   * 
   * X can be placed before L or C
   * 
   * C can be placed before D or M
   * 
   * 
   */
  public static String convertToRomanNumber(int num) {

    int number[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String roman[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    StringBuilder result = new StringBuilder();
    for (int i = 0; i < number.length; i++) {
      while (num >= number[i]) {
          num = num - number[i];
          result = result.append(roman[i]);
      }
    }

    return result.toString();
  }
Console
System.out.println("Integer 4 : Roman " + RomanNumbers.convertToRomanNumber(4)); System.out.println("Integer 100 : Roman " + RomanNumbers.convertToRomanNumber(100)); System.out.println("Integer 2000 : Roman " + RomanNumbers.convertToRomanNumber(2000)); System.out.println("Integer 3,999 : Roman " + RomanNumbers.convertToRomanNumber(3999)); Integer 4 : Roman IV Integer 100 : Roman C Integer 2000 : Roman MM Integer 3,999 : Roman MMMCMXCIX

References

Convert Online From Integer to Roman
Read More

Rotating matrix in java clockwise by 90 degree

October 09, 2020

Matrix Rotation in Java

In this article, we will explore a few different ways to rotate a matrix clock by 90 degrees.

Rotating Matrix to 90 Clockwise

Following is our Matrix. 

[    1        2        3    ]

[    4        5        6    ]

[    7        8        9    ]

We will explore multiple ways to rotate this matrix clockwise 90 

With Matrix Transpose

Matrix transpose is a flipped version of the matrix along its diagonal. In short, it is the same as interchanging the rows with columns. For the above matrix the transposed matrix will look like. 

[    1        4        7    ]

[    2        5        8    ]

[    3        6        9    ]

Also, the transposed matrix is equivalent to 90 Left rotation of the original array.
RoateMatrixWithTranspose
Here the Rotation of the matrix is done in two steps
1) We transpose the matrix 2) And we interchange the columns 
public void rotateMatrixRight90Transpose(int[][] mat) {

    int m = mat.length;
    int n = mat[0].length;

    for (int i = 0; i < m; i++) {
      for (int j = i; j < n; j++) {
        int x = mat[i][j];
        mat[i][j] = mat[j][i];
        mat[j][i] = x;
        System.out.println("IC" + i + ":" + j);
      }
    }

    // swap cols
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n / 2; j++) {
        // swap mat[i][j] with mat[N-i-1][j]
        int temp = mat[i][j];
        mat[i][j] = mat[i][n - j - 1];
        mat[i][n - j - 1] = temp;
      }
    }
  }
Output

Matrix Rotation with Transpose

<= Original Matrix  =>

[    1        2        3    ]

[    4        5        6    ]

[    7        8        9    ]



<= After Transpose =>

[    1        4        7    ]

[    2        5        8    ]

[    3        6        9    ]



<= After Rotation =>

[    7        4        1    ]

[    8        5        2    ]

[    9        6        3    ]

Matrix Rotation in Single pass

MatrixRotation.java
The following code will rotate the matrix in a single pass.
public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < (n + 1) / 2; i++) {
      for (int j = 0; j < n / 2; j++) {
        int temp = matrix[n - 1 - j][i];
        matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
        matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i];
        matrix[j][n - 1 - i] = matrix[i][j];
        matrix[i][j] = temp;
      }
    }
  }
Output

Matrix Rotation with single pass

<= Original Matrix  =>

[    1        2        3    ]

[    4        5        6    ]

[    7        8        9    ]



<= After Rotation =>

[    7        4        1    ]

[    8        5        2    ]

[    9        6        3    ]

Read More