✅ Topics for Day 6 DSA with Java

Focus: Two Pointer Technique

---

🔁 1. Learn & Implement Two Pointer Technique

• Understand how the two-pointer technique works on sorted arrays.

• Implement the following problems:

// Java Example: Two Sum (Sorted Array)
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[] { left + 1, right + 1 }; // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[] {}; // no solution
}

---

🧠 2. Solve 2 LeetCode Problems Using Two Pointers

1. LeetCode 167. Two Sum II – Input Array Is Sorted

2. LeetCode 283. Move Zeroes

   • Optimize with minimal swaps using the two-pointer pattern.

---

✨ Bonus Challenges (Optional but Recommended)

• LeetCode 26. Remove Duplicates from Sorted Array

• LeetCode 844. Backspace String Compare

---

📊 Explore Visualization

Try two-pointer visualizations at:
👉 https://visualgo.net/en/list

---

🧩 Concept Summary

• Two pointers are most useful for:

  • Sorted arrays

  • Reverse traversal

  • Sliding window (upcoming)

  • Partitioning logic

✅ 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 4: Sorting Algorithms (Basic to Intermediate)

🎯 Goals for Today

• Understand how sorting works and why it’s needed

• Learn and implement:

  • Bubble Sort

  • Selection Sort

  • Insertion Sort

• Analyze time & space complexities

• Practice beginner sorting problems

---

📘 1. Why Sorting Matters

Sorting helps:

• Optimize searching (e.g., binary search)

• Solve problems like duplicates, frequency, etc.

• Prepare data for algorithms like two pointers, greedy, divide & conquer, etc.

---

🔁 2. Sorting Algorithms

🔹 Bubble Sort

Repeatedly swap adjacent elements if they are in the wrong order.

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;
        }
    }
}

• Time Complexity: Worst → O(n²), Best → O(n) (already sorted)

• Space: O(1)

---

🔹 Selection Sort

Find the minimum element and put it at the beginning.

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

• Time Complexity: Always O(n²)

• Space: O(1)

---

🔹 Insertion Sort

Build the sorted array one element at a time by inserting elements at the correct position.

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

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

• Time Complexity: Best → O(n), Worst → O(n²)

• Space: O(1)

---

🧠 3. Sorting Algorithm Comparison Table

Algorithm	Time Complexity (Best / Avg / Worst)	Space	Stable?
Bubble Sort	O(n) / O(n²) / O(n²)	O(1)	✅
Selection Sort	O(n²) / O(n²) / O(n²)	O(1)	❌
Insertion Sort	O(n) / O(n²) / O(n²)	O(1)	✅

🔍 4. Practice Problems

Try these:

• Sort an array of 0s, 1s, and 2s (Dutch National Flag)

• Check if an array is sorted and rotated

• Count the number of swaps required to sort the array

• Sort a nearly sorted (k-sorted) array

You can also implement a custom comparator or reverse order sort (forward-thinking Java practice).

---

📚 Homework for Day 4

✅ Implement all three sorting algorithms
✅ Solve 2 sorting-based problems from LeetCode:

• Sort Colors

• Check if Array Is Sorted and Rotated

Would you like solutions for these 2 LeetCode problems?

---

⏭️ What’s Coming on Day 5:

• Advanced Sorting: Merge Sort, Quick Sort

• Time Complexity Analysis

• Recursion involved in sorting

✅ Solution Implement Both Linear and Binary Search Day 3 DSA with Java

🔹 Linear Search in Java

public class LinearSearch {
    public static int linearSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) return i;
        }
        return -1; // Not found
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2, 9};
        int key = 8;
        int index = linearSearch(arr, key);
        System.out.println("Element found at index: " + index);
    }
}

---

🔹 Binary Search in Java (Iterative)

public class BinarySearch {
    public static int binarySearch(int[] arr, int key) {
        int start = 0, end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] == key) return mid;
            else if (arr[mid] < key) start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int key = 5;
        int index = binarySearch(arr, key);
        System.out.println("Element found at index: " + index);
    }
}

---

✅ 2. LeetCode Problems

🔸 Search Insert Position

Problem: Return the index if the target is found. If not, return the index where it would be inserted.

public class SearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 2;
        System.out.println("Insert position: " + searchInsert(nums, target));
    }
}

---

🔸 First Bad Version

Assume isBadVersion(version) API exists.

public class FirstBadVersion {
    static int bad = 4; // Let's assume version 4 is the first bad version

    public static boolean isBadVersion(int version) {
        return version >= bad;
    }

    public static int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (isBadVersion(mid)) high = mid;
            else low = mid + 1;
        }
        return low;
    }

    public static void main(String[] args) {
        System.out.println("First bad version: " + firstBadVersion(10));
    }
}

---

🌱 3. Explore: Lower Bound & Upper Bound

These are binary search variants often used in competitive programming.

🔸 Lower Bound (First element ≥ target)

public static int lowerBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low; // returns the index
}

🔸 Upper Bound (First element > target)

public static int upperBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= target) low = mid + 1;
        else high = mid;
    }
    return low; // returns the index
}

You can test both with:

int[] arr = {1, 3, 3, 5, 7};
System.out.println("Lower Bound of 3: " + lowerBound(arr, 3)); // Output: 1
System.out.println("Upper Bound of 3: " + upperBound(arr, 3)); // Output: 3

🚀 Day 3: Searching Algorithms in Java

🎯 Goals:

• Understand Linear Search and Binary Search

• Learn when and how to use each

• Solve real interview problems using searching techniques

---

🔍 1. Linear Search

📘 Definition:

Linearly checks each element one by one. Used when the array is unsorted.

✅ Code Example:

public static int linearSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) return i;
    }
    return -1; // Not found
}

---

🧠 2. Binary Search

📘 Definition:

Used on sorted arrays. It divides the search space in half each time — O(log N) time complexity.

✅ Code (Iterative Approach):

public static int binarySearch(int[] arr, int key) {
    int start = 0, end = arr.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
}

✅ Code (Recursive Approach):

public static int binarySearchRec(int[] arr, int key, int start, int end) {
    if (start > end) return -1;

    int mid = start + (end - start) / 2;
    if (arr[mid] == key) return mid;
    else if (arr[mid] < key) return binarySearchRec(arr, key, mid + 1, end);
    else return binarySearchRec(arr, key, start, mid - 1);
}

---

💡 3. Binary Search Use Cases

• Search in sorted array

• Find first/last occurrence of an element

• Search in rotated sorted arrays

• Peak elements in mountain arrays

---

✍️ 4. Practice Problems

🔹 Write functions to:

• Find first and last occurrence of an element (e.g. in sorted duplicates)

• Count how many times a number appears in sorted array

• Search in a rotated sorted array

• Find square root using binary search (approximate to floor)

---

🔥 5. BONUS – Search in 2D Matrix

🔹 Use binary search logic on 2D:

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0, high = rows * cols - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int value = matrix[mid / cols][mid % cols];

        if (value == target) return true;
        else if (value < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

---

📚 Homework for Day 3:

• Implement both linear and binary search

• Solve 2 problems from LeetCode:

  • Search Insert Position

  • First Bad Version

• Explore: Lower Bound, Upper Bound (optional but forward-thinking)

---

⏭️ What’s Coming on Day 4?

• Sorting Algorithms: Bubble, Selection, Insertion (with time/space analysis)