Author name: Mike

Integer to English Words – task solution (LeetCode)

The task “Integer to English Words” can be solved as follows:

  • introduce arrays for big numbers (100, 1000, 1 000 000 and so on) and for numbers less than 20
  • introduce arrays for names of big numbers and for names of numbers less than 20
  • use a recursive approach:
    – if the current value ot the num is greater than the smallest number from the big numbers array:
    — find the highest divider of the current num value from an array of big numbers
    — append a result string with the recursive result of the current function with num as a reminder from division a num by the highest divider
    — append a result string with the current English name of divider
    — subtract the divider from the num
    – otherwise find the highest divider of the current value of the num from array of small numbers
    — append a result string with the current English name of divider
    — subtract the divider from the num
    — append a result string with the recursive result of the current function with num as a reminder from division a num by the highest divider
    – recursively call the current function with a num as the reminder from division the num by the highest divider
  • time complexity: O(n), where n – count of digits in the num
  • space complexity: O(1)

public class IntegerToEnglishWords {

  private final String[] symbols = new String[]{"One", "Two", "Three", "Four", "Five", "Six", "Seven",
      "Eight",
      "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
      "Seventeen", "Eighteen", "Nineteen", "Twenty", "Thirty", "Forty", "Fifty", "Sixty",
      "Seventy",
      "Eighty", "Ninety"};
  private final short[] numbers = new short[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
      18, 19,
      20, 30, 40, 50, 60, 70, 80, 90};
  private final String[] bigSymbols = new String[]{"Hundred", "Thousand", "Million", "Billion"};
  private final int[] bigNumbers = new int[]{100, 1000, 1000000, 1000000000};

  public String numberToWords(int num) {
    if (num == 0) {
      return "Zero";
    }
    return numberToWordsRecursive(num);
  }

  private String numberToWordsRecursive(int num) {
    if (num == 0) {
      return "";
    }
    var resultLeft = new StringBuilder();
    if (num >= bigNumbers[0]) {
      var j = bigNumbers.length - 1;
      while (num / bigNumbers[j] == 0) {
        j--;
      }
      resultLeft.append(numberToWordsRecursive(num / bigNumbers[j]));
      resultLeft.append(" ");
      resultLeft.append(bigSymbols[j]);
      resultLeft.append(" ");

      num -= bigNumbers[j] * (num / bigNumbers[j]);
    } else {
      var j = numbers.length - 1;
      while (num / numbers[j] == 0) {
        j--;
      }
      resultLeft.append(symbols[j]);
      num -= numbers[j] * (num / numbers[j]);
      resultLeft.append(numberToWordsRecursive(num / numbers[j]));
      resultLeft.append(" ");
    }
    resultLeft.append(numberToWordsRecursive(num));
    return resultLeft.toString().trim();
  }

  public static void main(String[] args) {
    System.out.println(new IntegerToEnglishWords().numberToWords(1));
  }
}

Integer to English Words – task solution (LeetCode) Read More »

Integer to Roman – task solution (LeetCode)

I’m going to describe how to solve the task Integer to Roman from LeetCode using greedy algorithm.

  • introduce 2 arrays: Roman characters (reflections) and their values
  • in a loop, until the remaining convertible number exceeds 0:
    – find the largest predecessor of the remaining convertible number
    – append the result string with the found reflection of the predecessor
    – subtract the value from the remainder of the convertible number

Time complexity: O(1)

Space complexity: O(1)

public class IntegerToRoman {

  public static String intToRoman(int num) {
    var symbols = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    var values = new short[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    var result = new StringBuilder();
    byte j = 0;
    while (num > 0) {
      while (values[j] > num) {
        j++;
      }
      result.append(symbols[j]);
      num -= values[j];
    }
    return result.toString();
  }

  public static void main(String[] args) {
    System.out.println(intToRoman(2888));
  }
}

Integer to Roman – task solution (LeetCode) Read More »

Bellman-Ford algorithm

We can’t use Dijkstra algorithm to find the shortest path in a graph if there are any negative weights in the graph. The Bellman Ford algorithm is capable of:
– find the shortest path in graphs with negative edge weights
– answer the question: is there a negative cycle (edges are connected in such a way that the sum of their weights has a negative value) in the graph.

To find the shortest path, the Bellman-Ford algorithm uses a mathematical approach called the Principle of Relaxation:
– to find the shortest path it’s necessary to apply relaxation V-1 times, where V – count of vertices (nodes)
– if we apply the V‘th time of “relaxation” and any short path is shortened, then there is a negative cycle in graph.

The following should be implemented in code:

  • introduce a new distance array to store the current shortest distance from the starting point to the node with a number equal to the index of the distance array
  • fill this array with maximum integer values
  • execute the following steps V-1 times the relaxation procedure:
    – take each edge with a start node and an end node
    – if the distance to the start node plus the weight of the edge (new distance) does no exceed the distance to the end node, then put the new distance to the end node in the distance array
  • check for negative weighted cycles:
    – repeat relaxation 1 time more
    – if any distance has reduced, there is a negative cycle in the graph.

Time complexity: O(V * E)

Space complexity: O(V)

import java.util.Arrays;

public class ImplementBellmanFordAlgorithm {

  static void BellmanFord(int[][] graph, int nodes, int edges, int src) {
    
    var distance = new int[nodes];
    Arrays.fill(distance, Integer.MAX_VALUE);

    distance[src] = 0;

    for (var i = 0; i < nodes - 1; i++) {
      for (var j = 0; j < edges; j++) {
        var node1 = graph[j][0];
        var node2 = graph[j][1];
        var weight12 = graph[j][2];
        if (distance[node1] != Integer.MAX_VALUE
            && (distance[node1] + weight12 < distance[node2])) {

          distance[node2] = distance[node1] + weight12;
        }
      }
    }

    for (var i = 0; i < edges; i++) {
      var node1 = graph[i][0];
      var node2 = graph[i][1];
      var weight12 = graph[i][2];
      if (distance[node1] != Integer.MAX_VALUE && distance[node1] + weight12 < distance[node2]) {
        System.out.println("Graph contains negative weight cycle");
        break;
      }
    }

    System.out.println("Vertex Distance from Source");
    for (var i = 0; i < nodes; i++) {
      System.out.println(i + "\t\t" + distance[i]);
    }
  }

  
  public static void main(String[] args) {
    var vertices = 5;
    var edges = 8;


    var graph = new int[][]{
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };

    BellmanFord(graph, vertices, edges, 0);
  }
}

Bellman-Ford algorithm Read More »

Dijkstra algorithm

The Dijkstra algorithm serves to find the cheapest path in acyclic graphs with positive weights.

The algorithms can be described as following actions:

  1. Introduce 2 maps:
    – the costs to store the minimum cost of reaching a node from the starting node
    – the parents to store the shortest path.
  2. Introduce a list of processed nodes.
  3. Start with the cheapest and not processed node (according to the map costs and the list of processed nodes).
  4. Find all neighbors of the current node.
  5. Update costs and parents maps if the path through the current node is cheaper than it was.
  6. Put the current node to the list of processed node.
  7. Recursively start from point 3.
  8. After processing, we will have to maps: with the cheapest path from the starting node to all nodes, and the map describing the shortest path from start to finish.

Time complexity: O(n2+m), where n – the number of vertices (nodes), m – the count of the edges

Space complexity: O(n2)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ImplementDijkstraAlgorithm {

  private static final Map<String, Map<String, Integer>> graph = Map.of(
      "start", Map.of("a", 6, "b", 2),
      "a", Map.of("fin", 1),
      "b", Map.of("a", 3, "fin", 5),
      "fin", Map.of()
  );

  private static final Map<String, Integer> costs = new HashMap<>() {
    {
      put("a", 6);
      put("b", 2);
      put("fin", Integer.MAX_VALUE);
    }
  };

  private static final Map<String, String> parents = new HashMap<>() {
    {
      put("a", "start");
      put("b", "start");
      put("fin", null);
    }
  };

  private static final List<String> processed = new ArrayList<>();

  private static String findLowestNodeCost() {
    return costs.entrySet().stream()
        .filter(entry -> !processed.contains(entry.getKey()))
        .sorted(Comparator.comparingInt(Map.Entry::getValue))
        .map(Map.Entry::getKey)
        .findFirst().orElse(null);
  }

  public static void main(String[] args) {
    var node = findLowestNodeCost();
    while (node != null) {
      var neighbors = graph.get(node);
      var cost = costs.get(node);
      for (var entry : neighbors.entrySet()) {
        var newCost = cost + entry.getValue();
        if (newCost < costs.get(entry.getKey())) {
          costs.put(entry.getKey(), newCost);
          parents.put(entry.getKey(), node);
        }
      }
      processed.add(node);
      node = findLowestNodeCost();
    }
    System.out.println(costs.get("fin"));
  }
}

Dijkstra algorithm Read More »

Counting sort

This is a very fast algorithm, but can only be used with arrays with integer values.

This algorithm can be explained as follows:

  • find minimum (min) and maximum (max) value in the integer array
  • create a new array with length = max – min + 1 to store statistics
  • iterate through the initial array and count the array values. Put the value statistics into the previously created array at indexes equal to the values

For example, the initial array:

[1, 2, 3, 2, 1, 5, 0], min = 0, max = 5

Statistics array:

[1, 2, 1, 1, 0, 1]

  • iterate through a statistic array and restore the initial array:

[0, 1, 1, 2, 3, 5]

  • time complexity: O(n+m), where n – the length of the initial array, m – the length of the statistical array
  • space complexity: O(m)
import java.util.Arrays;

public class ImplementCountingSort {

  private static void sort(int[] input) {
    var min = Integer.MAX_VALUE;
    var max = Integer.MIN_VALUE;
    for (int j : input) {
      if (j < min) {
        min = j;
      }
      if (j > max) {
        max = j;
      }
    }
    var arrayLength = max - min + 1;
    var counts = new int[arrayLength];
    for (var i = 0; i < input.length; i++) {
      counts[input[i] - min]++;
    }
    var i = 0;
    for (var j = 0; j < counts.length; j++) {
      while (counts[j] > 0) {
        input[i] = min + j;
        i++;
        counts[j]--;
      }
    }
  }

  public static void main(String[] args) {
    int[] array = {-6, -6, -6, 3, 2, 1};
    System.out.println(Arrays.toString(array));
    sort(array);
    System.out.println(Arrays.toString(array));
  }
}

Counting sort Read More »

Quick sort

This algorithm is slightly faster than merge sort and heap sort on random data. Uses a divide-and-conquer approach.

The main idea of the algorithm is as follows:

  • select an element from the array, we will call this element as “pivot”. This element can be any element, let’s take the rightmost element
  • place elements that are smaller than the pivot value to the left side of the pivot
  • place elements that exceed the pivot value to the right side of the pivot
  • recursively call the sort function on the left subarray and the right subarray.

Time complexity (average): O(n log n)

Space complexity: O(n)

import java.util.Arrays;

public class ImplementQuickSort {

  public static void quickSort(int[] array, int left, int right) {
    if (right <= left) {
      return;
    }
    int pivot = array[right];
    int i = left;
    for (int j = left; j < right; j++) {
      if (array[j] < pivot) {
        int buffer = array[i];
        array[i] = array[j];
        array[j] = buffer;
        i++;
      }
    }
    int temp = array[right];
    array[right] = array[i];
    array[i] = temp;

    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
  }

  public static void main(String[] args) {
    int[] array = {6, 5, 4, 3, 2, 1};
    System.out.println(Arrays.toString(array));
    quickSort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
  }
}

Quick sort Read More »

Merge sort

Merge sort is an efficient, stable divide-and-conquer algorithm. The main idea of this algorithm is as follows:

  1. Divide the array into parts until the size of the part exceeds 1 element.
  2. Sort each part with another part of the same size using merging sort.
  3. Move forward to merge larger parts than in the previous step.

Time complexity: O(n log n).

Space complexity: O(n).

import java.util.Arrays;

public class ImplementMergeSort {

  private static void mergeSort(int[] array) {
    var length = array.length;
    if (length == 1) {
      return;
    }
    var leftArray = Arrays.copyOfRange(array, 0, length / 2);
    var rightArray = Arrays.copyOfRange(array, length / 2, length);
    mergeSort(leftArray);
    mergeSort(rightArray);
    merge(leftArray, rightArray, array);
  }

  private static void merge(int[] leftArray, int[] rightArray, int[] array) {
    var i = 0;
    var l = 0;
    var r = 0;
    while (l < leftArray.length && r < rightArray.length) {
      if (leftArray[l] < rightArray[r]) {
        array[i++] = leftArray[l++];
      } else {
        array[i++] = rightArray[r++];
      }
    }
    while (l < leftArray.length) {
      array[i++] = leftArray[l++];
    }
    while (r < rightArray.length) {
      array[i++] = rightArray[r++];
    }
  }

  public static void main(String[] args) {
    var array = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    System.out.println(Arrays.toString(array));
    mergeSort(array);
    System.out.println(Arrays.toString(array));
  }
}

Merge sort Read More »

Insertion sort

This algorithm is smarter than bubble sort and selection sort. The main idea of the algorithm is as follows:

  1. Take the i-element from the array.
  2. Swap the elements, starting with element i back to the beginning of the array, until they are in order.

The time complexity is also O(n2), but for small arrays this algorithm is faster than quick sort or merge sort.

import java.util.Arrays;

public class ImplementInsertionSort {

  public static void insertionSort(int[] nums) {
    int i = 1;
    while (i < nums.length) {
      int j = i;
      while (j >= 1 && (nums[j] < nums[j - 1])) {
        var buf = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = buf;
        j--;
      }
      i++;
    }
  }

  public static void main(String[] args) {
    var numbers = new int[]{10, 9, 1, 2, 3, 4, 5, 6, 1};
    System.out.println(Arrays.toString(numbers));
    insertionSort(numbers);
    System.out.println(Arrays.toString(numbers));
  }
}

Insertion sort Read More »

Selection sort

The idea of selection sort: iteratively find a smallest (or biggest) element in the remaining part of array and put it to the appropriate position.

The time complexity is pretty bad: O(n2).

This algorithm can only be used for fairly small arrays.

public class ImplementSelectionSort {

  private static void selectionSort(int[] array) {
    for (int i = 0; i < (array.length - 1); i++) {
      var smallestIndex = findSmallest(array, i);
      var buf = array[i];
      array[i] = array[smallestIndex];
      array[smallestIndex] = buf;
    }
  }

  public static int findSmallest(int[] array, int startingIndex) {
    var smallest = startingIndex;
    for (int i = startingIndex; i < array.length; i++) {
      if (array[i] < array[smallest]) {
        smallest = i;
      }
    }
    return smallest;
  }

  public static void main(String[] args) {
    var array = new int[]{22, 1, 3, 99, 8};
    selectionSort(array);
    for (var elem : array) {
      System.out.println(elem);
    }
  }
}

Selection sort Read More »

Bubble sort

Bubble sort algorithm is the most famous sorting algorithm as it is studied in schools, universities and various computer courses.

The idea of the algorithm is as follows:

  • we iterate through the array and swap adjacent elements pair by pair if they aren’t in the required order.
  • each iteration through the array pushes one item (“bubble”) to the outermost position.

The main weak point of this approach: the time complexity is O(n2).

This algorithm is created for educational purposes only: never use it in production code!

import java.util.Arrays;

public class ImplementBubbleSort {

  // An optimized version of Bubble Sort
  private static void bubbleSort(int[] arr, int n)
  {
    int buffer;
    boolean swapped;
    for (var i = 0; i < n - 1; i++) {
      swapped = false;
      for (var j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          buffer = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = buffer;
          swapped = true;
        }
      }
      if (!swapped)
        break;
    }
  }

  public static void main(String[] args)
  {
    var array = new int[] { 64, 34, 25, 12, 22, 11, 90 };
    var n = array.length;
    bubbleSort(array, n);
    System.out.println("Sorted array: ");
    System.out.println(Arrays.toString(array));
  }
}

Bubble sort Read More »

Scroll to Top