✅ Day 4 Solution - DSA with Java

 

✅ 1. Implement All Three Sorting Algorithms

🔹 Bubble Sort

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // Optimization
        }
    }
}

---

🔹 Selection Sort

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // Swap
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

---

🔹 Insertion Sort

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

---

✅ 2. LeetCode Problems

---

🔸 Problem 1: Sort Colors

Sort an array containing only 0s, 1s, and 2s.
Use Dutch National Flag Algorithm (O(n) time, O(1) space)

public class SortColors {
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap with low
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                // nums[mid] == 2
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
            }
        }
    }
}

---

🔸 Problem 2: Check if Array Is Sorted and Rotated

Return true if array is sorted and rotated at most once.

🔍 Logic:

Count how many times arr[i] > arr[i+1]. If it happens more than once, it's not valid.

public class CheckSortedRotated {
    public static boolean check(int[] nums) {
        int count = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }

        return count <= 1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 1, 2};
        System.out.println("Is Sorted and Rotated? " + check(arr)); // true
    }
}

---

🧠 Summary of Day 4

• ✅ Bubble, Selection, Insertion Sort implemented

• ✅ LeetCode problems solved

  • Dutch National Flag (0s, 1s, 2s)

  • Check Sorted & Rotated