Sorting Algorithms + Code

Q: Different types of Sorting:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Cyclic Sort

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 1, 4};
//        int[] arr = {1, 2, 3, 4, 5};
        bubbleSort(arr);
//        selectionSort(arr);
//        insertionSort(arr);
//        cyclicSort(arr);
        System.out.print(Arrays.toString(arr));
    }

    // Bubble sort ---
    static void bubbleSort(int[] arr) {
        boolean swapped;
        // Run the steps n-1 times
        for (int i = 0; i < arr.length; i++) {
            swapped = false;
            // For each step, max item will come at the last respective index
            for (int j = 1; j < arr.length - i; j++) {
                // Swap if the item is smaller than the previous item
                if (arr[j] < arr[j - 1]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    swapped = true;
                }
            }
            // If you didn't swap for a particular value of i, it means the array is sorted hence stop the program
            if (!swapped) break;
        }
    }
    // ---

    // Selection sort ---
    static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // Find the max item in the remaining array and swap with correct index
            int last = arr.length - i - 1;
            int maxIndex = getMaxIndex(arr, 0, last);
            // Swap
            swap(arr, maxIndex, last);
        }
    }

    // Return the index of maximum element
    static int getMaxIndex(int[] arr, int start, int end) {
        int max = start;

        for (int i = start; i <= end; i++) {
            if (arr[max] < arr[i]) {
                max = i;
            }
        }
        return max;
    }

    // Swap the items with the correct position
    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
    // ---

    // Insertion Sort ---
    static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j > 0; j--) {
                if (arr[j] < arr[j-1]) {
                    swap(arr, j-1, j);
                }
                else {
                    break;
                }
            }
        }
    }
    // ---

    // Cyclic Sort ---
    static void cyclicSort(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            int index = arr[i] - 1;
            if (arr[i] != arr[index]) {
                swap(arr, index, i);
            }
            else {
                i++;
            }
        }
    }
    // ---
}

Q: Find missing number? (LeetCode Question)

public class Main {
    public static void main(String[] args) {
        // Asked in Amazon
        int[] arr = {9, 6, 4, 2, 3, 5, 7, 0, 1};
//        int[] arr = {0, 1};
        System.out.println(missingNumber(arr));
    }

    static int missingNumber(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            int correctInd = arr[i];
            if (arr[i] < arr.length && arr[i] != arr[correctInd]) {
                // Swap
//                swap(arr, i, correctInd);
                swap2(arr, i, correctInd);
            }
            else {
                i++;
            }
        }

        // Search for the first missing number
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] != j) {
                return j;
            }
        }

        // If all numbers are present, return n (i.e., arr.length)
        return arr.length;
    }

    // Swap items
    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }

    // Optimized Version
    static void swap2(int[] arr, int first, int second) {
        if (first != second) {
            int temp = arr[first];
            arr[first] = arr[second];
            arr[second] = temp;
        }
    }
}

Q: Find all missing numbers? (LeetCode Question)

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // Asked in Google
        int[] arr = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println(allMissingNumbers(arr));
    }

    static List<Integer> allMissingNumbers(int[] arr) {
        // Sort the array using cycle sort
        int i = 0;
        while (i < arr.length) {
            int correctInd = arr[i] - 1;
            if (arr[i] > 0 && arr[i] <= arr.length && arr[i] != arr[correctInd]) {
                swap(arr, i, correctInd);
            } else {
                i++;
            }
        }

        // Find missing numbers
        List<Integer> ans = new ArrayList<>();
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] != j + 1) {
                ans.add(j + 1);
            }
        }
        return ans;
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Q: Find duplicate numbers? (LeetCode Question)

public class Main {
    public static void main(String[] args) {
        // Test cases
        int[] arr1 = {1, 3, 4, 2, 2};  // Expected Output: 2
        int[] arr2 = {3, 1, 3, 4, 2};  // Expected Output: 3
        int[] arr3 = {0};              // Expected Output: -1 (invalid input)
        int[] arr4 = {1, 1};           // Expected Output: 1

        System.out.println(findDuplicate(arr1));
        System.out.println(findDuplicate(arr2));
        System.out.println(findDuplicate(arr3));
        System.out.println(findDuplicate(arr4));
    }

    static int findDuplicate(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            if (arr[i] < 1 || arr[i] > arr.length - 1) {
                return -1;  // Handle invalid numbers
            }

            int correctInd = arr[i] - 1;
            if (arr[i] != arr[correctInd]) {
                swap(arr, i, correctInd);
            } else {
                i++;
            }
        }

        // Find the duplicate
        for (i = 0; i < arr.length; i++) {
            if (arr[i] != i + 1) {
                return arr[i];
            }
        }

        return -1; // No duplicate found
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Q: Find all duplicate numbers? (LeetCode Question)

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // Asked in Amazon or Microsoft
        int[] arr = {4, 3, 2, 7, 8, 2, 3, 1};
        System.out.println(allDuplicates(arr));
    }

    static List<Integer> allDuplicates(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            int correctInd = arr[i] - 1;
            if (arr[i] != arr[correctInd]) {
                swap(arr, i, correctInd);
            } else {
                i++;
            }
        }

        // Find duplicate
        List<Integer> ans = new ArrayList<>();
        for (i = 0; i < arr.length; i++) {
            if (arr[i] != i+1) {
                ans.add(arr[i]);
            }
        }

        return ans;
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Q: Set mismatch (LeetCode Question).

import java.util.Arrays;

public class SetMismatch {
    public static void main(String[] args) {
        // Asked in Amazon or Microsoft
        int[] arr = {1, 2, 2, 4};
        System.out.println(Arrays.toString(findErrorNum(arr)));
    }

    static int[] findErrorNum(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            int correctInd = arr[i] - 1;
            if (arr[i] != arr[correctInd]) {
                swap(arr, i, correctInd);
            } else {
                i++;
            }
        }

        // Find error numbers
        int[] ans = {-1, -1};
        for (i = 0; i < arr.length; i++) {
            if (arr[i] != i+1) {
                ans[0] = arr[i];
                ans[1] = i + 1;
            }
        }

        return ans;
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    
    }
}

Q:  (LeetCode Question)

import java.util.Arrays;

public class FindMissingpositive {
    public static void main(String[] args) {
        // Asked in Amazon
        int[] arr = {7, 8, 9, 11, 12};
//        int[] arr = {3, 4, -1, 1};
        System.out.println(missingPositive(arr));
    }

    static int missingPositive(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            int correctInd = arr[i] - 1;
            if (arr[i] > 0 && arr[i] <= arr.length && arr[i] != arr[correctInd]) {
                swap(arr, i, correctInd);
            } else {
                i++;
            }
        }

        // Find missing smallest positive number
        for (i = 0; i < arr.length; i++) {
            if (arr[i] != i+1) {
                return i+1;
            }
        }
        return arr.length + 1;
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}