**algorithm**. Show all posts

## Useful resources for Dijkstra's Algorithm

### Examples

Increasing monotonic array:

[1, 2, 20, 30]

[1, 2, 20, 20, 30]

decreasing monotonic array:

[66, 50, 40, 4]

[66, 50, 40, 40]

### Algorithm

### Implementation

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

### References

## Java Convert Integer to Roman Numbers

### Roman Number

Symbol | Number |
---|---|

I | 1 |

V | 5 |

X | 10 |

L | 50 |

C | 100 |

D | 500 |

M | 1,000 |

### Negative Numbers and Range

### Conversion Rules

### Implementation

```
/**
* 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();
}
```

### References

## Matrix Rotation in Java

## Rotating Matrix to 90 Clockwise

[ 1 2 3 ]

[ 4 5 6 ]

[ 7 8 9 ]

### With Matrix Transpose

[ 1 4 7 ]

[ 2 5 8 ]

[ 3 6 9 ]

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

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

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

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 ]