GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Computer Science Algorithms

Here are a list of problems and their algorithmic solutions that I have written in Java to help me improve my computer science skills. To improve your skills, I suggest solving these problems using only a text editor, ie. no IDE. Make sure to not use code completion or the internet. After a few attempts, come back and check the solution. I like to use Sublime Text, the Linux terminal, and GNU Make for build automation.

References:

Shuffling
Generating a Random Permutation of a Finite Set

Date: June 5, 2016
To properly shuffle or permute an array, each permutation must have an equal chance of happening. The Fisher–Yates shuffle, aka the Knuth shuffle, algorithm successfully do so. Remember, when shuffling, there are n! ways to arrange the elements in a set.

Time Complexity: O(n)
public class Shuffling {

    public static void main(String[] args) {

        int[] numbers = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        print(numbers);
        shuffle(numbers);
        print(numbers);
    }

    public static void shuffle(int[] array) {

        for (int i = 0; i < array.length - 1; i++) {

            int random =
                  (int) (Math.random() * (array.length - i)) + i;
            swap(array, i, random);
        }
    }

    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

3- Way Partition Quicksort

Date: June 5, 2016
public class Quicksort3Way {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        quicksort3Way(numbers, 0, numbers.length - 1);
        print(numbers);
    }

    public static void quicksort3Way(int[] array,
                                     int start, int end) {

        if (start < end) {

            int left = start;
            int mid = start;
            int right = end;

            int random =
                 (int) (Math.random() * (end - start)) + start;
            swap(array, start, random);
            int pivot = array[start];

            while (mid <= right) {

                if (array[mid] < pivot) {

                    swap(array, mid, left);
                    mid++;
                    left++;

                } else if (array[mid] > pivot) {

                    swap(array, mid, right);
                    right--;

                } else {
                    mid++;
                }
            }

            quicksort3Way(array, start, left - 1);
            quicksort3Way(array, left + 1, end);
        }
    }

    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Dual-Pivot Quicksort

Date: June 3, 2016
Instead of employing only a single pivot as seen in the classical quicksort, this version makes use of two pivots. It was brought to light by Vladimir Yaroslavskiy in 2009 and has a better overall performance when compared to three-way quicksort, and the classical single pivot quicksort. For information on a three pivot variant, see this paper. The following image demonstrates the partitioning of the array where P1 and P2 are the pivots and P1 <= P2.

public class QuicksortDualPivot {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        sort(numbers, 0, numbers.length - 1);
        print(numbers);
    }

    public static void sort(int[] array, int start, int end) {

        if (start < end) {

            if (array[start] > array[end]) {
                swap(array, start, end);
            }

            int lessThan = start + 1;
            int mid = start + 1;
            int greaterThan = end - 1;

            while (mid <= greaterThan) {

                if (array[mid] < array[start]) {

                    swap(array, mid, lessThan);
                    lessThan++;
                    mid++;

                } else if (array[mid] > array[end]) {

                    swap(array, mid, greaterThan);
                    greaterThan--;


                } else {

                    mid++;
                }
            }

            swap(array, start, --lessThan);
            swap(array, end, ++greaterThan);

            sort(array, start, lessThan - 1);
            sort(array, lessThan + 1, greaterThan - 1);
            sort(array, greaterThan + 1, end);
        }
    }

    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Quicksort

Date: June 3, 2016
Quicksort is a divide-and-conquer algorithm that sorts in-place. It is one of the most popular sorting algorithms, but it is not stable. It centers on selecting a pivot and moving smaller elements to its left, and moving larger elements to its right. Quicksort is then called recursively on these two subarrays.

Best & Average Time Complexity: O(n log(n))
Worst Time Complexity: O(n2)
public class Quicksort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        quicksort(numbers, 0, numbers.length - 1);
        print(numbers);
    }

    public static void quicksort(int[] array, int start, int end) {

        if (start < end) {

            int pivot = partition(array, start, end);
            quicksort(array, start, pivot - 1);
            quicksort(array, pivot + 1, end);
        }
    }

    public static int partition(int[] array, int start, int end) {

        // Select random pivot
        int random = (int) (Math.random() * (end - start)) + start;
        swap(array, start, random);
        int pivot = array[start];

        int left = start + 1;
        int right = end;

        while (true) {

            while (left <= right && array[left] <= pivot) {
                left++;
            }

            while (right >= left && array[right] >= pivot) {
                right--;
            }

            if (left <= right) {
                swap(array, left, right);

            } else {
                break;
            }
        }

        swap(array, start, right);

        return right;
    }

    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Implement a Stack using Two Queues

Date: June 1, 2016
There are two ways to implement a stack using two queues. The code below demonstrates the first version. For the push function, first enqueue the element in queue #2, then enqueue (move) all items from queue #1 into queue #2. Finally, switch the names of the queues. For the pop function, dequeue and return the element from queue #1.

For the second version, enqueue the element in queue #1 when invoking the push function. For the pop function, enqueue (move) all items from queue #1 into queue #2 except for the very last element. Dequeue and return the only element from queue #1, and then switch the names of the queues.
import java.util.Queue;
import java.util.LinkedList;
import java.util.Iterator;

public class Stack2Queues {

    static Queue<Integer> queue1 = new LinkedList<Integer>();
    static Queue<Integer> queue2 = new LinkedList<Integer>();

    public static void main(String[] args) {

        int num = 5;

        for (int i = 0; i < num; i++) {
            push(i);
            System.out.println("Adding " + i);
        }

        for (int i = 0; i < num; i++) {
            System.out.println("Retrieving " + pop());
        }
    }

    public static void push(int num) {

        queue2.add(num);

        Iterator<Integer> iter = queue1.iterator();

        while (iter.hasNext()) {
            queue2.add(iter.next());
            iter.remove();
        }

        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public static int pop() {
        return queue1.remove();
    }
}
                

Heapsort

Date: June 1, 2016
Heapsort is similar to selection sort, but has a faster performance since it uses the properties of a binary heap to quickly find the required element. Heapsort is an in-place algorithm, but it is not stable.

Time Complexity: O(n log(n)) for best, average & worst case
Space Complexity: O(1)
public class Heapsort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        heapsort(numbers);
        print(numbers);
    }

    public static void heapsort(int[] array) {

        int lastIndex = array.length - 1;

        // Heapify
        for (int i = lastIndex / 2; i >= 0; i--) {

            sink(array, i, lastIndex);
        }

        // Sortdown
        for (int i = lastIndex; i > 0; i--) {

            swap(array, 0, i);
            sink(array, 0, i - 1);
        }
    }

    public static void sink(int[] array,
                            int parent, int lastIndex) {

        int leftChild = parent * 2;
        int rightChild = parent * 2 + 1;
        int max = parent;

        if (leftChild <= lastIndex
                      && array[leftChild] > array[max]) {

            max = leftChild;
        }

        if (rightChild <= lastIndex
                       && array[rightChild] > array[max]) {

            max = rightChild;
        }

        if (max != parent) {

            swap(array, parent, max);
            sink(array, max, lastIndex);
        }
    }

    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Merge Sort

Date: June 1, 2016
Merge Sort is a divide and conquer algorithm that was invented by the talented John von Neumann in 1945. It is a stable sort and does not require random access to data. Therefore, it is great for sorting linked lists.

Time Complexity: O(n log(n)) for best, average & worst case
Space Complexity: O(n)
public class MergeSort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        mergeSort(numbers);
        print(numbers);
    }

    public static void mergeSort(int[] array) {
        mergeSort(array, 0, array.length - 1);
    }

    public static void mergeSort(int[] array, int start, int end) {

        if (start < end) {

            int middle = (start + end) / 2;

            mergeSort(array, start, middle);
            mergeSort(array, middle + 1, end);

            merge(array, start, middle, end);
        }
    }

    public static void merge(int[] array,
                             int start, int middle, int end) {

        int length = middle + 1;
        int[] copyArray = new int[length];
        System.arraycopy(array, 0, copyArray, 0, length);

        int i = start;
        int j = middle + 1;
        int k = start;

        while (i <= middle && j <= end) {
            array[k++] = (array[j] < copyArray[i])
                                   ? array[j++] : copyArray[i++];
        }

        while (i <= middle) {
            array[k++] = copyArray[i++];
        }
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

The Tower of Hanoi

Date: May 31, 2016
The Tower of Hanoi is a classic problem that shows the power of recursion. The correct solution invovles 2n - 1 moves where n is the number of disks.

Time Complexity: O(2n)
public class TowerHanoi {

    static int numMoves = 0;

    public static void main(String[] args) {

        int numDisks = 10;
        solveTowerHanoi(numDisks, "A", "B", "C");
        System.out.println(
                    "Number of moves: " + numMoves);
    }

    public static void solveTowerHanoi(int numDisks,
        String start, String auxiliary, String end) {

        numMoves++;

        if (numDisks == 1) {
            System.out.println(start + " to " + end);

        } else if (numDisks > 1) {

             solveTowerHanoi(
                numDisks - 1, start, end, auxiliary);

             System.out.println(start + " to " + end);

             solveTowerHanoi(
                numDisks - 1, auxiliary, start, end);
        } else {

            throw new IllegalArgumentException(
                "Number of disks must be larger than 0!");
        }
    }
}
                

Shell Sort

Date: May 27, 2016
Shell sort works by sorting elements that are a certain distance (gap) apart by employing insertion sort, and then iteratively reducing the gap over time. This algorithm is adaptive, but not stable. The time complexity of the algorithm heavily depends on the size of the gap. Three popular gap sequences are Shell (floor(n/2k)), Pratt (2p3q), and Knuth ((3k - 1) / 2). For a gap sequence that may be optimal for your needs, check out Ciura's paper.

Shell Time Complexity: O(n2)
Pratt Time Complexity: O(n log2(n))
Knuth Time Complexity: O(n3/2) — Best
Space Complexity: O(1)
public class ShellSort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        shellSort(numbers);
        print(numbers);
    }

    public static void shellSort(int[] array) {

        int gap = 1;

        while (gap < array.length / 3) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {

            for (int i = gap; i < array.length; i++) {

                int element = array[i];
                int j;

                for (j = i - gap; j >= 0 && array[j] > element;
                                                    j -= gap) {
                    array[j + gap] = array[j];
                }

                array[j + gap] = element;
            }

            gap /= 3;
        }
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Selection Sort

Date: May 27, 2016
Selection sort works by finding the smallest unordered element and swapping it with the leftmost unordered element. It is an in-place algorithm, but it is not stable. It also generally performs worse than insertion sort.

Time Complexity: O(n2)
Space Complexity: O(1)
public class SelectionSort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        selectionSort(numbers);
        print(numbers);
    }

    public static void selectionSort(int[] array) {

        for (int i = 0; i < array.length; i++) {

            int k = i;

            for (int j = i + 1; j < array.length; j++) {

                if (array[j] < array[k]) {
                    k = j;
                }
            }

            swap(i, k, array);
        }
    }

    public static void swap(int i, int j, int[] array) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Insertion Sort

Date: May 24, 2016
Insertion sort works by inserting the current element into its position within the section of the array that has already been sorted (ie. 0 to i). This algorithm is stable, in-place, adaptive, and online. An online algorithm is one that can start processing its input without having the entire input available from the start (eg. streaming data). A sorting algorithm is adaptive if it can take advantage of the original ordering of the input (eg. the algorithm runs faster if the array is somewhat sorted already).

Time Complexity: O(n2)
Space Complexity: O(1)
public class InsertionSort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        insertionSort(numbers);
        print(numbers);
    }

    public static void insertionSort(int[] array) {

        for (int i = 1; i < array.length; i++) {

            int element = array[i];
            int j;

            for (j = i - 1; j >= 0 && array[j] > element; j--) {

                array[j + 1] = array[j];
            }

            array[j + 1] = element;
        }
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Bubble Sort

Date: May 24, 2016
Bubble sort is a stable sort, therefore input order is preserved for elements with equal keys. It is also an in-place sort meaning that sorting is done within the original array/list. It works by moving through the list and swapping adjacent elements if they are in the wrong order. Below are two versions of bubble sort with bubbleSortBetter having a lower computational complexity since one less element is needed to be compared after each iteration.

Time Complexity: O(n2)
Space Complexity: O(1)
public class BubbleSort {

    public static void main(String[] args) {

        int[] numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        bubbleSort(numbers);
        print(numbers);

        numbers = new int[]{5, 7, 3, 9, 2, 10, 4, 1, 6, 8};
        print(numbers);
        bubbleSortBetter(numbers);
        print(numbers);
    }

    public static void bubbleSort(int[] array) {

        boolean flag = true;

        while (flag) {

            flag = false;

            for (int i = 0; i < array.length - 1; i++) {

                int j = i + 1;

                if (array[i] > array[j]) {

                    swap(i, j, array);
                    flag = true;
                }
            }
        }
    }

    public static void bubbleSortBetter(int[] array) {

        for (int i = 0; i < array.length; i++) {

            boolean flag = false;

            for (int j = array.length - 1; j > i; j--) {

                if (array[j] < array[j-1]) {
                    swap(j, j - 1, array);
                    flag = true;
                }
            }

            if (!flag) {
                break;
            }
        }
    }
    public static void swap(int i, int j, int[] array) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {

        for (int num : array) {
            System.out.print(num + " ");
        }

        System.out.println("");
    }
}
                

Finding the Maximum Submatrix Within Another Matrix

Date: May 23, 2016
This algorithm works by employing Kadane's algorithm on an array whose values represent the sum of the rows of a submatrix.

Click here to see the algorithm.

Finding the Maximum Contiguous Subarray

Date: May 22, 2016
To find the contiguous subarray with the largest sum (maximum subarray problem), one can employ Kadane's algorithm. It works by scanning through the values in the array and computing the maximum subarray that ends at each index position. The current subarray will either consist of the previous subarray plus the current element, or solely the current element if its value is larger. The current subarray is then compared to the global maximum subarray.

Time Complexity: O(n)
Space Complexity: O(1)
public class MaximumSubarray {

    public static void main(String[] args) {

        int[] array = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        findMaximumSubarray(array);
    }

    public static void findMaximumSubarray(int[] array) {

        if (array == null || array.length == 0) {

            throw new IllegalArgumentException(
                "Must provide an array with at least " +
                "one element in it");
        }

        int curStart = 0;
        int curEnd = 0;
        int curMax = array[0];

        int maxStart = 0;
        int maxEnd = 0;
        int max = array[0];

        for (int i = 1; i < array.length; i++) {

            if (array[i] > curMax + array[i]) {

                curStart = i;
                curEnd = i;
                curMax = array[i];

            } else {

                curEnd = i;
                curMax += array[i];
            }

            if (curMax > max) {

                maxStart = curStart;
                maxEnd = curEnd;
                max = curMax;
            }
        }

        System.out.print("Maximum subarray with sum " + max);
        System.out.print(" starts at " + maxStart);
        System.out.println(" and ends at " + maxEnd);
    }
}
                

Determining if a Tree is Symmetric

Date: May 21, 2016
This algorithm works for binary trees as well as for trees with more than two children.

Click here to see the algorithm.

Determining if Two Trees are Identical

Date: May 21, 2016
The algorithm presented here is suited for trees in general (ie. it works for non-binary trees as well).

Click here to see the algorithm.

Highest Profit from Stock using Greedy Algorithm

Date: May 20, 2016
The naive approach to finding the highest potential profit from buying and selling stock is to use a double for loop where each stock price is compared against all other stock prices to find the highest difference. The better method is to employ a greedy algorithm that makes a locally optimal choice. This reduces the time complexity from quadratic to linear: O(n).
public class Greedy {

    public static void main(String[] args) {

        int[] stock = new int[]{30, 25, 27, 32, 31, 29};

        highestProfit(stock);
    }

    public static void highestProfit(int[] stock) {

        if (stock == null || stock.length == 0
            || stock.length == 1) {

            return;
        }

        int profit = stock[1] - stock[0];
        int min = stock[0];

        for (int i = 1; i < stock.length; i++) {

            int tempProfit = stock[i] - min;

            profit = Math.max(profit, tempProfit);

            min = Math.min(min, stock[i]);
        }

        System.out.println("Highest profit would be $" + profit);
    }
}
                

Generating Prime Numbers

Date: May 19, 2016
There are many ways to generate prime numbers. The naive way is to employ trial division. Instead of checking if the prime number candidate is divisible by numbers up to the candidate itself, one can reduce the time complexity of this algorithm by only checking up to and including the square root of the candidate. This is because all composite numbers (non-primes) that are less than the candidate must have a factor that is less than or equal to the square root of the candidate.

The sieve of Eratosthenes and the sieve of Sundaram are two better algorithms for generating prime numbers, and their implementations are shown on another page.

Click here to see the algorithms.

Calculate a Fibonacci Number

Date: May 18, 2016
To reduce the time complexity of this algorithm, I have employed a technique called memoization that is based on caching and retrieving the results of expensive function calls.

Time Complexity Without Memoization: O(2n)
Space Complexity: O(n)
import java.util.Scanner;

public class Fibonacci {

    static long[] memoization;

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        memoization = new long[num + 1];

        long result = findFibonacci(num);

        System.out.print("Fibonacci for number: ");
        System.out.println(num + " = "  + result);
    }

    public static long findFibonacci(int num) {

        if (num <= 0) {
            return 0;

        } else {

            long fib = memoization[num];

            if (fib == 0) {

                if (num == 1) {
                    memoization[num] = 1;

                } else {
                    memoization[num] = findFibonacci(num - 1)
                                    + findFibonacci(num - 2);
                }

                fib = memoization[num];
            }

            return fib;
        }
    }
}
                

Determine if a String is a Palindrome

Date: May 17, 2016
This algorithm works by checking the equality of the ends of the string and if they match, then it removes both of those characters and calls the function again (recursion) with the rest of the string.
import java.util.Scanner;

public class Palindrome {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in).useDelimiter("\\n");
        String test = in.next();

        System.out.print("Is \"" + test + "\" a palindrome? ");
        System.out.println(isPalindrome(test));
    }

     public static boolean isPalindrome(String str) {

        if (str == null || str.length() == 0) {
            return false;

        } else if (str.length() == 1) {
            return true;

        } else if (str.charAt(0) == str.charAt(str.length() - 1)) {

            str = str.substring(1, str.length() - 1);

            if (str.length() > 0) {
                return isPalindrome(str);
            }

            return true;
        }

        return false;
    }
}
                

Find the Factorial of a Number

Date: May 17, 2016
Time Complexity: O(n) when multiplication is an O(1) operation. This is incorrect since as the index tends towards infinity, the time complexity of multiplying two numbers of arbitrary length is not O(1). Three famous multiplication algorithms include the Karatsuba algorithm, Toom–Cook multiplication, and the Schönhage–Strassen algorithm.
public class Factorial {

    public static void main(String[] args) {

        int num = 6;
        long iter = factorialIter(num);
        long recurse = factorialRecurse(num);

        System.out.println(iter + " " + recurse);
    }

    public static long factorialIter(long num) {

        if (num == 0 || num == 1) {
            return 1;
        }

        long factorial = 1;

        for (int i = 2; i <= num; i++) {
            factorial *= i;
        }

        return factorial;
    }

    public static long factorialRecurse(long num) {

        if (num == 0 || num == 1) {
            return 1;
        }

        return num * factorialRecurse(num - 1);
    }
}
                

Tree Traversal

Date: May 17, 2016

Swapping Two Numbers Without Temporary Variable

Date: May 15, 2016
Here are three different ways to swap two numbers without using a temporary variable. One makes use of addition and subtraction, another make use of multiplication and division, and the third employs the bitwise XOR operator. Caveats: the multiplication/division method does not work when one of the numbers equals 0, and both arithmetic methods might cause arithmetic overflow if the numbers are too large.
public class Swap {

    public static void main(String[] args) {

        int a = 5, b = 10;
        System.out.println("a = " + a + " : b = " + b);

        swapFirst(a, b);
        swapSecond(a, b);
        swapThird(a, b);

    }

    public static void swapFirst(int a, int b) {

        a = a + b; // 5 + 10 = 15
        b = a - b; // 15 - 10 = 5
        a = a - b; // 15 - 5 = 10

        System.out.println("a = " + a + " : b = " + b);
    }

    public static void swapSecond(int a, int b) {

        a = a * b; // 5 * 10 = 50
        b = a / b; // 50 / 10 = 5
        a = a / b; // 50 / 5 = 10

        System.out.println("a = " + a + " : b = " + b);
    }

    public static void swapThird(int a, int b) {

        a = a ^ b; // 00000101 ^ 00001010 = 00001111 = 15
        b = a ^ b; // 00001111 ^ 00001010 = 00000101 = 5
        a = a ^ b; // 00001111 ^ 00000101 = 00001010 = 10

        System.out.println("a = " + a + " : b = " + b);
    }
}
                

Generating All Permutations of a Given String

Date: May 15, 2016
In this algorithm, each permutation of the original string is created by employing a for loop as well as recursion. For each permutation, the algorithm appends the current character from str onto the prefix string. This character is then removed from str and the permute function is called with the new string values. When the length of str equals 0, then the prefix string represents a valid permutation. One caveat: this algorithm does not take repeated characters into account.

Time complexity: O(n!)
public class Permutation {

    public static void main(String[] args) {
        permute("apple");
    }

    public static void permute(String str) {
        permute("", str);
    }

    public static void permute(String prefix, String str) {
        int length = str.length();

        if (length == 0) {
            System.out.println(prefix);
        } else {

            for (int i = 0; i < length; i++) {

                String newPrefix = prefix + str.charAt(i);
                String newStr = str.substring(0, i)
                                + str.substring(i + 1);
                permute(newPrefix, newStr);
            }
        }
    }
}
                

Binary Search Algorithm

Date: May 14, 2016
For the binary search algorithm to work, the array being searched must already be sorted in ascending order. To find the target element, the algorithm compares the element located in the middle of the array to the target. If the element is greater than the target, the upper half of the array is eliminated from the search, and the process repeats. If the element if less than the target, then the lower half of the array is eliminated. This process repeats until the target has been found or the search subarray no longer has any elements in it.

Time Complexity: O(log(n))
import java.util.Arrays;

public class BinarySearch {

    public static void main(String[] args) {

        int[] nums = new int[]{5, 9, 2, 4, 15, 22, 3, 1};
        int searchFor = 9;
        Arrays.sort(nums);

        int index1 = Arrays.binarySearch(nums, searchFor);

        if (index1 > -1) {
            System.out.println("Found " + searchFor
                    + " at index " + index1);
        }

        int index2 = binarySearch(nums, searchFor);

        if (index2 > -1) {
            System.out.println("Found " + searchFor
                    + " at index " + index2);
        }
    }

    public static int binarySearch(int[] array, int target) {
        return binarySearch(array, target, 0, array.length);
    }

    // Start index is inclusive
    // End index is exclusive
    public static int binarySearch(
                int[] array, int target, int start, int end) {

        if (start < 0 || end > array.length || start >= end
            || array[start] > target
            || array[end - 1] < target) {

            return -1;
        }

        while (true) {

            int middle = (int) Math.floor((start + end) / 2.0F);

            if (array[middle] == target) {
                return middle;

            } else if (array[middle] > target) {
                end = middle;

            } else if (array[middle] < target) {
                start = middle + 1;
            }

            if (start >= end) {
                return -1;
            }
        }
    }
}
                

Reversing the Words in a String

Date: May 11, 2016
import java.util.List;
import java.util.ArrayList;

public class ReverseWords {

    public static void main(String[] args) {

        String sentence = "This is a sentence";
        reverseWithSplit(sentence);
        reverseWithoutSplit(sentence);
    }

    public static void reverseWithSplit(String sentence) {

        String[] words = sentence.split("\\s");
        StringBuilder sBuilder = new StringBuilder(sentence.length());

        for (int i = words.length - 1; i >= 0; i--) {
            sBuilder.append(words[i]);

            if (i > 0) {
                sBuilder.append(" ");
            }
        }

        System.out.println(sBuilder.toString());
    }

    public static void reverseWithoutSplit(String sentence) {

        StringBuilder sBuilder = new StringBuilder(sentence.length());
        List<String> wordsArray = new ArrayList<String>();
        int prevSpace = 0;

        for (int i = 0; i < sentence.length(); i++) {

            String charString = sentence.substring(i, i + 1);

            if (charString.matches("\\s")) {
                wordsArray.add(sentence.substring(prevSpace, i));
                prevSpace = i + 1;

            } else if (i == sentence.length() - 1) {
                wordsArray.add(sentence.substring(prevSpace, i + 1));
            }
        }

        for (int i = wordsArray.size() - 1; i >= 0; i--) {

            sBuilder.append(wordsArray.get(i));

            if (i > 0) {
                sBuilder.append(" ");
            }
        }

        System.out.println(sBuilder.toString());
    }
}
                

Checking if a Point Lies Within a Polygon

Date: May 10, 2016
To determine if a point lies within a polygon (point-in-polygon problem), one can employ the crossing number algorithm, also known as the even-odd rule algorithm. Starting at the point, cast an infinite ray in any fixed direction and count the number of times that the ray intersects with the polygon. If the number of intersections is odd, then the point is inside the polygon. If the number of intersections is even, then the point is outside of the polygon. A few caveats: the algorithm does not work if the point resides on an edge of the polygon, nor does it always work for self-intersecting polygons (complex polygons).

Click here to see the algorithms.

Checking Array for Duplicate Elements

Date: May 9, 2016
The naive algorithm O(n2) is to use a double for loop to check for duplicates. A better approach is to sort the array using Quicksort or Merge Sort, which have an average time complexity of O(nlog(n)), and then compare consecutive locations in the array (lines 13-20).

Another way in Java is to make use of the Set interface, which models the mathematical set abstraction. Since a set cannot contain duplicate elements, one can add all of the array's elements to the Set and check its size. If its size differs from the array's length, then the array has duplicate elements (lines 22-27). Also, if you add an element to the Set one at a time, the Set will return false if the Set already contains the element (lines 29-36).
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Iterator;

public class Duplicates {

    public static void main(String[] args) {

        Integer[] array = new Integer[]{1, 6, 3, 4, 2, 4, 5};
        int length = array.length;

        Arrays.sort(array);

        for (int i = 0; i < length - 1; i++) {

            if (array[i] == array[i + 1]) {
                System.out.println("Duplicate found");
            }
        }

        List<Integer> list = Arrays.asList(array);
        HashSet<Integer> set = new HashSet<Integer>(list);

        if (set.size() != length) {
            System.out.println("Duplicate found");
        }

        HashSet<Integer> set2 = new HashSet<Integer>(length);

        for (Integer num : array) {

            if (!set2.add(num)) {
                System.out.println("Duplicate found");
            }
        }
    }
}
                

Detecting a Loop in Singly Linked List

Date: May 8, 2016
Floyd's Cycle Detection Algorithm (The Tortoise and The Hare) and Brent's Cycle Detection Algorithm (The Teleporting Turtle) are two famous algorithms that solve this problem. Both make use of two pointers that travel through the list at different speeds. If there is a loop/cycle, then the faster moving pointer (the hare) will eventually lap the slower moving pointer (the tortoise). Therefore, when both the hare and the tortoise point to the same node, then a loop/cycle has been detected. Otherwise, if the hare reaches the end of the list, then there is no loop/cycle.

Click here to see the algorithms.

Remove Node From Position p in a Singly Linked List

Date: May 8, 2016

Reversing a Singly Linked List

Date: May 7, 2016
public void reverseList(LinkedList list) {

    if (list.head == null) {
        return;
    } else {

        Node cur = list.head;
        Node newHead = null;

        while (true) {

            if (cur == null) {
                break;
            }

            Node temp = newHead;
            newHead = cur;
            cur = cur.next;
            newHead.next = temp;
        }

        list.tail = list.head;
        list.head = newHead;
    }
}
                
Time Complexity: O(n)
Space Complexity: O(1)

Extract n Bits Between Bits i and j

Date: May 7, 2016
public class ExtractBits {

    public static void main(String[] args) {

        int num = 0b11101000;

        int i = 2;
        int j = 6;
        int n = j - i; // = 6 - 2 = 4

        int mask = (1 << n) - 1; // = 10000 - 1 = 01111

        System.out.println(Integer.toBinaryString(num));

        num = num >>> i; // = 11101000 >>> 2 = 111010
        num = num & mask; // = 111010 & 01111 = 1010

        System.out.println(Integer.toBinaryString(num));
    }
}
                
  1. This algorithm will extract n bits from a binary number starting at i (exclusive) and ending at j (inclusive).
  2. To drop the least significant bits before and including i, use the unsigned right shift operator (line 15).
  3. To isolate the remaining n bits, you need to create a bitmask of n 1s (line 11). To do this, use the left shift operator to left shift a 1 n times. This will result in a 1 followed by n 0s. Subtracting 1 from it will give you what you need.
  4. Finally, perform a bitwise AND operation with the bitmask and the number (line 16).

Isolate Last Bit

Date: May 7, 2016
import java.util.Scanner;

public class IsolateBit {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();

        System.out.println(Integer.toBinaryString(num));

        num = num & ~(num - 1);

        System.out.println(Integer.toBinaryString(num));
    }
}
                
Example using binary number 11001100:
  1. 11001100 minus 1 = 11001011
  2. The bitwise complement of 11001011 = 00110100
  3. Performing the bitwise AND operator on 00110100 and the original number (11001100) = 00000100

Unset Last Bit

Date: May 7, 2016
import java.util.Scanner;

public class UnsetBit {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();

        System.out.println(Integer.toBinaryString(num));

        num = num & (num - 1);

        System.out.println(Integer.toBinaryString(num));
    }
}
                
Example using binary number 11001100:
  1. 11001100 minus 1 = 11001011
  2. Performing the bitwise AND operator on 11001011 and the original number (11001100) = 11001000