✅ Day 5 Solution - DSA with Java

 

✅ 1. Implement Merge Sort and Quick Sort

🔹 Merge Sort

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1, n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

---

🔹 Quick Sort

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Final pivot swap
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

---

✅ 2. LeetCode Problems

---

🔸 Merge Sorted Array

Merge nums2 into nums1 sorted in-place.

public class MergeSortedArray {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;

        while (i >= 0 && j >= 0) {
            nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

---

🔸 Sort an Array

Use any sorting method. Here's Merge Sort used:

public class SortAnArray {
    public static int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1, n2 = r - m;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; ++i) L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j];

        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2)
            arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

---

✅ 3. Non-Recursive Quick Sort (Iterative)

import java.util.Stack;

public class QuickSortIterative {
    public static void quickSort(int[] arr) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{0, arr.length - 1});

        while (!stack.isEmpty()) {
            int[] range = stack.pop();
            int low = range[0], high = range[1];

            if (low < high) {
                int pi = partition(arr, low, high);
                stack.push(new int[]{low, pi - 1});
                stack.push(new int[]{pi + 1, high});
            }
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high], i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Final pivot placement
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
}

---

✅ 4. Visualize Merge vs Quick Sort

You can interactively visualize how Merge and Quick Sort work at:

🔗 Visualgo.net – Sorting Visualizations

Click:

• Merge Sort → observe divide → merge steps

• Quick Sort → watch pivot partitioning → recursive reduction

💡 Use small array sizes (e.g. 10 elements) to step-through for learning.

🚀 Day 5: Merge Sort & Quick Sort in Java 🎯 Goals for Today

• Understand the Divide and Conquer strategy

• Learn and implement:

  • Merge Sort

  • Quick Sort

• Analyze Time & Space Complexities

• Solve intermediate-level sorting problems

---

📘 1. Merge Sort

A stable, divide-and-conquer sorting algorithm.
Time Complexity: O(n log n) in all cases
Space Complexity: O(n) (extra array)

✅ Logic:

• Divide the array into two halves

• Sort each half recursively

• Merge the two sorted halves

🔹 Java Implementation

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Sort the left and right halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge them
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }

        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[j++];
    }
}

---

⚡ 2. Quick Sort

Quick and efficient, especially on average cases.
Time Complexity:

• Best/Average: O(n log n)

• Worst: O(n²) (when pivot is worst chosen)
  Space: O(log n) (due to recursive calls)

✅ Logic:

• Choose a pivot

• Partition the array: elements < pivot go left, > pivot go right

• Recursively sort left and right

🔹 Java Implementation

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1; // Index of smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap pivot to the right place
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

---

📊 3. Merge Sort vs Quick Sort

Feature	Merge Sort	Quick Sort
Time (Best)	O(n log n)	O(n log n)
Time (Worst)	O(n log n)	O(n²)
Space	O(n)	O(log n)
Stable	✅ Yes	❌ No
In-place	❌ No	✅ Yes
Use Case	Linked lists	Arrays

🧠 4. Practice Problems

Try these problems:

1. ✅ Merge Sorted Array

2. ✅ Sort an Array

3. 🔁 Kth Largest Element in Array – Use Quick Select

4. 🧠 Count Inversions in Array – Use Merge Sort logic

---

📚 Homework for Day 5

• Implement Merge Sort and Quick Sort

• Solve 2 LeetCode problems involving sorting or partitioning

• Try to write non-recursive quick sort (advanced)

• Visualize Merge vs Quick: Try https://visualgo.net/en/sorting

---

🔜 Coming Up on Day 6:

• Recursion Mastery

• Backtracking intro (Subset, Permutations)

• Understanding call stack and dry runs

✅ 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

✅ Day 5 Solution - DSA with C

 

✅ 1. Implement your own strlen()

#include <stdio.h>

int my_strlen(char str[]) {
    int i = 0;
    while (str[i] != '\0') {
        i++;
    }
    return i;
}

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);
    printf("Length of string = %d\n", my_strlen(str));
    return 0;
}

---

✅ 2. Implement your own strcpy()

#include <stdio.h>

void my_strcpy(char dest[], char src[]) {
    int i = 0;
    while (src[i] != '\0') {
        dest[i] = src[i];
        i++;
    }
    dest[i] = '\0'; // Null-terminate
}

int main() {
    char src[100], dest[100];
    printf("Enter a string to copy: ");
    scanf("%s", src);

    my_strcpy(dest, src);
    printf("Copied string: %s\n", dest);
    return 0;
}

---

✅ 3. Implement your own strcmp()

#include <stdio.h>

int my_strcmp(char str1[], char str2[]) {
    int i = 0;
    while (str1[i] != '\0' && str2[i] != '\0') {
        if (str1[i] != str2[i])
            return str1[i] - str2[i];
        i++;
    }
    return str1[i] - str2[i]; // Also handles different lengths
}

int main() {
    char str1[100], str2[100];
    printf("Enter two strings:\n");
    scanf("%s %s", str1, str2);

    int result = my_strcmp(str1, str2);
    if (result == 0)
        printf("Strings are equal.\n");
    else if (result < 0)
        printf("First string is smaller.\n");
    else
        printf("First string is greater.\n");

    return 0;
}

---

✅ 4. LeetCode Problem: Valid Anagram

Two strings are anagrams if they contain the same characters in any order.

✨ Custom C Solution:

#include <stdio.h>
#include <string.h>

int isAnagram(char s[], char t[]) {
    int count[26] = {0};

    if (strlen(s) != strlen(t))
        return 0;

    for (int i = 0; s[i] != '\0'; i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }

    for (int i = 0; i < 26; i++) {
        if (count[i] != 0)
            return 0;
    }

    return 1;
}

int main() {
    char s[100], t[100];
    printf("Enter first string: ");
    scanf("%s", s);
    printf("Enter second string: ");
    scanf("%s", t);

    if (isAnagram(s, t))
        printf("Valid Anagram\n");
    else
        printf("Not an Anagram\n");

    return 0;
}

✅ This C code solves the Valid Anagram LeetCode problem without using libraries like sort.

🚀 DSA with C – Day 5: Strings in C

🎯 Goal:

• Understand how strings work in C

• Perform common string operations:

  • Reverse a string

  • Check for palindrome

  • Count character frequency

  • Check if two strings are anagrams

---

🧠 What is a String in C?

A string is a character array ending with a null character (\0).

🔧 Declaration

char str[100]; // Character array

📥 Input

scanf("%s", str); // No spaces
fgets(str, sizeof(str), stdin); // With spaces

---

👨‍💻 1. Reverse a String

#include <stdio.h>
#include <string.h>

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str); // Use fgets if you want spaces

    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        char temp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = temp;
    }

    printf("Reversed string: %s\n", str);
    return 0;
}

---

👨‍💻 2. Check if a String is a Palindrome

#include <stdio.h>
#include <string.h>

int main() {
    char str[100];
    int flag = 1;

    printf("Enter a string: ");
    scanf("%s", str);

    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - i - 1]) {
            flag = 0;
            break;
        }
    }

    if (flag)
        printf("Palindrome\n");
    else
        printf("Not a palindrome\n");

    return 0;
}

---

👨‍💻 3. Character Frequency Count

#include <stdio.h>
#include <string.h>

int main() {
    char str[100];
    int freq[256] = {0}; // ASCII chars

    printf("Enter a string: ");
    scanf("%s", str);

    for (int i = 0; str[i] != '\0'; i++) {
        freq[(int)str[i]]++;
    }

    printf("Character frequencies:\n");
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0)
            printf("%c: %d\n", i, freq[i]);
    }

    return 0;
}

---

👨‍💻 4. Check if Two Strings Are Anagrams

Two strings are anagrams if they contain the same characters in any order.

#include <stdio.h>
#include <string.h>

int isAnagram(char str1[], char str2[]) {
    int count[256] = {0};

    if (strlen(str1) != strlen(str2))
        return 0;

    for (int i = 0; str1[i]; i++) {
        count[(int)str1[i]]++;
        count[(int)str2[i]]--;
    }

    for (int i = 0; i < 256; i++) {
        if (count[i] != 0)
            return 0;
    }

    return 1;
}

int main() {
    char str1[100], str2[100];
    printf("Enter two strings: ");
    scanf("%s %s", str1, str2);

    if (isAnagram(str1, str2))
        printf("Anagram\n");
    else
        printf("Not anagram\n");

    return 0;
}

---

🧪 Practice Problems:

1. Count vowels and consonants in a string.

2. Convert lowercase letters to uppercase.

3. Remove duplicate characters from a string.

4. Check if two strings are rotations of each other (e.g., abc and cab).

---

📘 Homework for Day 5:

• Implement your own versions of:

  • strlen()

  • strcpy()

  • strcmp()

• Try a string problem from LeetCode: Valid Anagram

✅ Day 4 solution - DSA with C

 Find the GCD of Two Numbers Using Recursion

GCD (Greatest Common Divisor) using Euclidean Algorithm:

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

---

✅ 2. Recursive Function to Calculate Power (xⁿ)

#include <stdio.h>

int power(int x, int n) {
    if (n == 0)
        return 1;
    return x * power(x, n - 1);
}

int main() {
    int base, exponent;
    printf("Enter base and exponent: ");
    scanf("%d %d", &base, &exponent);
    printf("%d^%d = %d\n", base, exponent, power(base, exponent));
    return 0;
}

---

✅ 3. Reverse an Array Using Recursion

#include <stdio.h>

void reverse(int arr[], int start, int end) {
    if (start >= end)
        return;
    
    // Swap
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;

    reverse(arr, start + 1, end - 1);
}

int main() {
    int arr[100], n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    reverse(arr, 0, n - 1);

    printf("Reversed array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

🚀 DSA with C – Day 4: Recursion + Factorial + Fibonacci + Array Sum

 

🎯 Goal:

• Understand the concept of Recursion

• Write recursive functions for:

  • Factorial

  • Fibonacci series

  • Sum of array elements

• Compare recursion with iteration

---

🧠 What is Recursion?

A function calling itself to solve a smaller version of the same problem.

🔄 Recursion Structure:

return_type function_name(parameters) {
    if (base_condition)
        return result;
    else
        return function_name(smaller_problem);
}

---

👨‍💻 1. Factorial Using Recursion

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

---

👨‍💻 2. Fibonacci Series Using Recursion

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int terms;
    printf("Enter number of terms: ");
    scanf("%d", &terms);
    printf("Fibonacci Series: ");
    for (int i = 0; i < terms; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

⚠️ Note: Recursive Fibonacci is inefficient for large n – we’ll optimize it later with memoization or iteration.

---

👨‍💻 3. Sum of Array Using Recursion

#include <stdio.h>

int sumArray(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumArray(arr, n - 1);
}

int main() {
    int arr[100], n;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Sum of array = %d\n", sumArray(arr, n));
    return 0;
}

---

🧪 Practice Problems:

1. Find the GCD of two numbers using recursion.

2. Write a recursive function to calculate the power (xⁿ).

3. Reverse an array using recursion.

---

📘 Homework for Day 4:

• Compare iteration vs recursion by writing factorial using loops.

• Try writing Fibonacci with memoization or using a loop.

• LeetCode problem suggestion: Climbing Stairs – this is basically Fibonacci!

---

📅 Day 4 Summary:

• ✅ Understood recursion

• ✅ Implemented factorial, Fibonacci, and sum via recursion

• ✅ Practiced recursive thinking