πŸŒ“

Bubble Sort

2022-08-21
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
import java.util.*;

class Program {
    public static int[] bubbleSort(int[] array) {
        int count = 1;
        boolean isSorted = false;
        while (!isSorted) {
            isSorted = true;
            for (int i = 0; i < array.length - count; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    isSorted = false;
                }
            }
            count += 1;
        }

        return array;
    }

    public static void swap(int[] array, int idx1, int idx2) {
        int i = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = i;
    }
}

Read More

Heap Sort

2022-08-21
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
import java.util.*;

class Program {
    public static int[] heapSort(int[] array) {
        buildMaxHeap(array);
        int endIdx = array.length - 1;
        while (endIdx > 0) {
            siftDown(array, 0, endIdx);
            swap(array, 0, endIdx);
            endIdx -= 1;
        }
        return array;
    }

    public static int[] buildMaxHeap(int[] array) {
        if (array.length == 0)
            return array;
        int firstParentIdx = (array.length - 2) / 2;
        for (int i = firstParentIdx; i >= 0; i--) {
            siftDown(array, i, array.length - 1);
        }
        return array;
    }

    public static void siftDown(int[] array, int currentIdx, int endIdx) {
        int leftChildIdx = currentIdx * 2 + 1;
        while (leftChildIdx <= endIdx) {
            int rightChildIdx = leftChildIdx + 1;
            int idxToSwap = leftChildIdx;
            if (rightChildIdx <= endIdx && array[rightChildIdx] > array[leftChildIdx]) {
                idxToSwap = rightChildIdx;
            }
            if (array[idxToSwap] > array[currentIdx]) {
                swap(array, idxToSwap, currentIdx);
                currentIdx = idxToSwap;
                leftChildIdx = currentIdx * 2 + 1;
            } else {
                return;
            }
        }
    }

    public static void swap(int[] array, int idx1, int idx2) {
        int tmp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = tmp;
    }
}

Read More

Insertion Sort

2022-08-21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

class Program {
    public static int[] insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int j = i;
            while (j > 0 && array[j] < array[j - 1]) {
                swap(j, j - 1, array);
                j -= 1;
            }
        }
        return array;
    }

    public static void swap(int i, int j, int[] array) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Read More

Selection Sort

2022-08-21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

class Program {
    public static int[] selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minimumIdx = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minimumIdx]) {
                    minimumIdx = j;
                }
            }
            swap(i, minimumIdx, array);
        }
        return array;
    }

    public static void swap(int i, int j, int[] array) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Read More

KMP

2022-08-21
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.*;

class Program {
    public static boolean knuthMorrisPrattAlgorithm(String string, String substring) {
        int[] pattern = buildPattern(substring);
        return doesMatch(string, substring, pattern);
    }

    public static int[] buildPattern(String substring) {
        int[] pattern = new int[substring.length()];
        Arrays.fill(pattern, -1);
        int j = 0, i = 1;
        while (i < substring.length()) {
            if (substring.charAt(i) == substring.charAt(j)) {
                pattern[i] = j;
                i += 1;
                j += 1;
            } else if (j > 0) {
                j = pattern[j - 1] + 1;
            } else {
                i += 1;
            }
        }
        return pattern;
    }

    public static boolean doesMatch(String string, String substring, int[] pattern) {
        int i = 0, j = 0;
        while (i + substring.length() - j <= string.length()) {
            if (string.charAt(i) == substring.charAt(j)) {
                if (j == substring.length() - 1)
                    return true;
                i += 1;
                j += 1;
            } else if (j > 0) {
                j = pattern[j - 1] + 1;
            } else {
                i += 1;
            }
        }
        return false;
    }
}

Read More

Min Heap

2022-08-21
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
72
73
74
75
76
import java.util.*;

// Do not edit the class below except for the buildHeap,
// siftDown, siftUp, peek, remove, and insert methods.
// Feel free to add new properties and methods to the class.
class Program {
    static class MinHeap {
        List<Integer> heap = new ArrayList<Integer>();

        public MinHeap(List<Integer> array) {
            heap = buildHeap(array);
        }

        public List<Integer> buildHeap(List<Integer> array) {
            int firstParent = (array.size() - 2) / 2;
            for (int i = firstParent; i >= 0; i--) {
                siftDown(i, array.size() - 1, array);
            }
            return array;
        }

        public void siftDown(int currentIdx, int endIdx, List<Integer> heap) {
            int leftChild = currentIdx * 2 + 1;
            while (leftChild < heap.size()) {
                int rightChild = (currentIdx * 2 + 2) < heap.size() ? currentIdx * 2 + 2 : -1;
                int idxToSwap = leftChild;
                if (rightChild != -1 && heap.get(leftChild) > heap.get(rightChild)) {
                    idxToSwap = rightChild;
                }
                if (heap.get(currentIdx) > heap.get(idxToSwap)) {
                    swap(currentIdx, idxToSwap, heap);
                    currentIdx = idxToSwap;
                    leftChild = currentIdx * 2 + 1;
                } else {
                    return;
                }
            }
        }

        public void siftUp(int currentIdx, List<Integer> heap) {
            int parentIdx = (currentIdx - 1) / 2;
            while (parentIdx >= 0) {
                if (heap.get(currentIdx) < heap.get(parentIdx)) {
                    swap(currentIdx, parentIdx, heap);
                    currentIdx = parentIdx;
                    parentIdx = (currentIdx - 1) / 2;
                } else {
                    return;
                }
            }
        }

        public int peek() {
            return heap.get(0);
        }

        public int remove() {
            int valueToRemove = heap.get(0);
            swap(0, heap.size() - 1, heap);
            heap.remove(heap.size() - 1);
            siftDown(0, heap.size() - 1, heap);
            return valueToRemove;
        }

        public void insert(int value) {
            this.heap.add(value);
            siftUp(heap.size() - 1, heap);
        }

        public void swap(int i, int j, List<Integer> array) {
            int temp = array.get(i);
            array.set(i, array.get(j));
            array.set(j, temp);
        }
    }
}

Read More

Radix Sort

2022-08-21
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
import java.util.*;

class Program {

    public ArrayList<Integer> radixSort(ArrayList<Integer> array) {
        if (array.size() < 2)
            return array;
        int digit = 0;
        int max = Collections.max(array);
        while ((max / Math.pow(10, digit)) > 0) {
            countSort(array, digit);
            digit += 1;
        }
        return array;
    }

    public void countSort(List<Integer> array, int digit) {
        int digitColumn = (int) Math.pow(10, digit);
        int[] countArray = new int[10];
        int[] sortedArray = new int[array.size()];

        for (int i = 0; i < array.size(); i++) {
            int countIdx = (array.get(i) / digitColumn) % 10;
            countArray[countIdx] += 1;
        }

        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        for (int i = array.size() - 1; i >= 0; i--) {
            int countIdx = (array.get(i) / digitColumn) % 10;
            countArray[countIdx] -= 1;
            int sortIdx = countArray[countIdx];
            sortedArray[sortIdx] = array.get(i);
        }

        for (int i = 0; i < array.size(); i++) {
            array.set(i, sortedArray[i]);
        }
    }
}

Read More

12. Integer to Roman

2022-08-21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String intToRoman(int num) {
        int[] values = new int[] { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        String[] symbols = new String[] { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < values.length && num > 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                ans.append(symbols[i]);
            }
        }
        return ans.toString();
    }
}

Read More

342. Power of Four

2022-08-21
class Solution {
    public boolean isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0xaaaaaaaa) == 0);

Read More

314. Binary Tree Vertical Order Traversal

2022-08-21
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
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Map<Integer, List<Integer>> colNodesMap = new HashMap<>();
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
        q.offer(new Pair<>(root, 0));
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        while (!q.isEmpty()) {
            Pair<TreeNode, Integer> currPair = q.poll();
            colNodesMap.putIfAbsent(currPair.getValue(), new ArrayList<>());
            colNodesMap.get(currPair.getValue()).add(currPair.getKey().val);
            if (currPair.getKey().left != null) {
                q.offer(new Pair<>(currPair.getKey().left, currPair.getValue() - 1));
            }
            if (currPair.getKey().right != null) {
                q.offer(new Pair<>(currPair.getKey().right, currPair.getValue() + 1));
            }
            min = Math.min(min, currPair.getValue());
            max = Math.max(max, currPair.getValue());
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = min; i <= max; i++) {
            ans.add(new ArrayList<>(colNodesMap.get(i)));
        }
        return ans;
    }
}

Read More