PYnative

Python Programming

Home » Java Exercises » Java Sorting and Searching Exercises: 35 Coding Problems with Solutions

Java Sorting and Searching Exercises: 35 Coding Problems with Solutions

Updated on:  | Leave a Comment

This set of 35 Java exercises covers every classic sorting and searching algorithm, along with the interview-style variations built on top of them.

  • The sorting exercises walk through Bubble, Selection, Insertion, Merge, Quick (including Hoare partitioning and median-of-three pivot selection), Radix, and Shell Sort, along with custom Comparator and Comparable sorting for objects.
  • The searching exercises cover standard, recursive, ceiling, and floor binary search, then move into higher-difficulty variations: search in a rotated array, Quickselect, the Dutch National Flag algorithm, finding a peak element, and interpolation search.

Each exercise includes a Practice Problem, Hint, Solution code, and detailed Explanation, so you understand not just what the code does, but why it works.

+ Table of Contents (35 Exercises)

Table of contents

Exercise 1: Bubble Sort with Swap Counting

Problem Statement: Implement Bubble Sort in Java to sort an array of integers in ascending order, and track the number of swaps performed.

Purpose: This exercise helps you practice the repeated comparison and swap pattern at the core of Bubble Sort, and introduces the idea of instrumenting an algorithm to measure its own work.

Given Input: int[] numbers = {5, 2, 9, 1, 5, 6};

Expected Output:

Sorted array = [1, 2, 5, 5, 6, 9]
Number of swaps = 6
▼ Hint
  • Use two nested loops, the outer loop for passes and the inner loop for adjacent comparisons.
  • Each pass pushes the largest remaining unsorted element to its correct position at the end.
  • Increment a counter every time you actually swap two elements, not every time you compare them.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static int bubbleSort(int[] numbers) {
        int swaps = 0;
        int n = numbers.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                    swaps++;
                }
            }
        }
        return swaps;
    }
    public static void main(String[] args) {
        int[] numbers = {5, 2, 9, 1, 5, 6};
        int swaps = bubbleSort(numbers);
        System.out.println("Sorted array = " + Arrays.toString(numbers));
        System.out.println("Number of swaps = " + swaps);
        // Usage:
        // bubbleSort(new int[]{5, 2, 9, 1, 5, 6}) sorts the array and returns 6, the number of swaps performed
    }
}Code language: Java (java)

Explanation:

  • for (int j = 0; j < n - 1 - i; j++): Shrinks the inner loop’s range on each pass, since the last i elements are already guaranteed to be sorted.
  • if (numbers[j] > numbers[j + 1]): Compares each pair of adjacent elements and swaps them if they are out of order.
  • swaps++;: Increments the counter only when an actual swap occurs, giving an accurate measure of how much work the algorithm performed on this input.
  • Alternative: You could add a flag that breaks out of the outer loop early if a full pass produces no swaps, which improves best-case performance to O(n) on an already sorted array.

Exercise 2: Selection Sort for Strings

Problem Statement: Implement Selection Sort in Java, modified to sort an array of strings alphabetically.

Purpose: This exercise helps you practice adapting a numeric sorting algorithm to work with a different data type by swapping out the comparison logic, a common requirement when sorting real-world objects.

Given Input: String[] words = {"banana", "apple", "cherry", "date"};

Expected Output: [apple, banana, cherry, date]

▼ Hint
  • On each pass, find the index of the alphabetically smallest remaining word using compareTo() instead of a numeric comparison.
  • Swap that word into the current position once the inner loop finishes.
  • Repeat for each position until the entire array is sorted.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void selectionSort(String[] words) {
        int n = words.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (words[j].compareTo(words[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            String temp = words[i];
            words[i] = words[minIndex];
            words[minIndex] = temp;
        }
    }
    public static void main(String[] args) {
        String[] words = {"banana", "apple", "cherry", "date"};
        selectionSort(words);
        System.out.println(Arrays.toString(words));
        // Usage:
        // selectionSort(new String[]{"banana", "apple", "cherry", "date"})
        // modifies the array to [apple, banana, cherry, date]
    }
}Code language: Java (java)

Explanation:

  • words[j].compareTo(words[minIndex]) < 0: Uses String’s natural ordering to determine which word comes first alphabetically, replacing the numeric less-than check used for integers.
  • int minIndex = i;: Tracks the position of the smallest word found so far in the unsorted portion of the array.
  • Swap logic: Places the smallest remaining word into its correct sorted position only once per outer loop iteration, unlike Bubble Sort which may swap multiple times per pass.
  • Alternative: You could pass a custom Comparator instead of relying on compareTo(), which would let you sort case-insensitively or by string length without changing the sorting logic itself.

Exercise 3: Insertion Sort with Early Exit

Problem Statement: Implement Insertion Sort in Java, optimized to break early if the array becomes fully sorted partway through.

Purpose: This exercise helps you practice adding a short-circuit check to an existing algorithm, a useful technique for avoiding unnecessary work when the input is already close to sorted.

Given Input: int[] numbers = {1, 2, 3, 5, 4, 6};

Expected Output: [1, 2, 3, 4, 5, 6]

▼ Hint
  • Standard Insertion Sort already shifts each key only as far as needed, which is a partial optimization on its own.
  • Add a helper method that checks whether the entire array is already in non-decreasing order.
  • At the start of each outer loop iteration, call this helper, and break out of the loop entirely if the array is already sorted.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void insertionSort(int[] numbers) {
        int n = numbers.length;
        for (int i = 1; i < n; i++) {
            if (isSorted(numbers)) {
                break;
            }
            int key = numbers[i];
            int j = i - 1;
            while (j >= 0 && numbers[j] > key) {
                numbers[j + 1] = numbers[j];
                j--;
            }
            numbers[j + 1] = key;
        }
    }
    private static boolean isSorted(int[] numbers) {
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 5, 4, 6};
        insertionSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // insertionSort(new int[]{1, 2, 3, 5, 4, 6}) modifies the array to [1, 2, 3, 4, 5, 6]
        // and exits one iteration early since the array becomes sorted before the final pass
    }
}Code language: Java (java)

Explanation:

  • if (isSorted(numbers)) break;: Checks at the start of every outer loop iteration whether the array is already fully sorted, and exits immediately if so.
  • isSorted(int[] numbers): Scans the array once, returning false as soon as it finds any pair of adjacent elements that are out of order.
  • while (j >= 0 && numbers[j] > key): Shifts elements greater than the key one position to the right until the correct insertion point is found.
  • Alternative: You could track whether any shifting occurred during the previous iteration instead of rescanning the whole array, which avoids the O(n) cost of isSorted() on every outer loop pass.

Exercise 4: Merge Sort for an Array of Doubles

Problem Statement: Implement the standard divide-and-conquer Merge Sort in Java for an array of doubles.

Purpose: This exercise helps you practice the divide-and-conquer pattern of splitting a problem into halves, solving each half recursively, and combining the results, a strategy used throughout algorithm design.

Given Input: double[] numbers = {3.6, 1.2, 5.4, 2.2, 4.8};

Expected Output: [1.2, 2.2, 3.6, 4.8, 5.4]

▼ Hint
  • Split the array into two halves around the midpoint, then recursively sort each half.
  • A subarray of length 1 is already sorted by definition, which forms the recursion’s base case.
  • After both halves are sorted, merge them back together by repeatedly picking the smaller of the two current front elements.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void mergeSort(double[] numbers, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(numbers, left, mid);
            mergeSort(numbers, mid + 1, right);
            merge(numbers, left, mid, right);
        }
    }
    private static void merge(double[] numbers, int left, int mid, int right) {
        double[] leftArray = Arrays.copyOfRange(numbers, left, mid + 1);
        double[] rightArray = Arrays.copyOfRange(numbers, mid + 1, right + 1);
        int i = 0;
        int j = 0;
        int k = left;
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                numbers[k++] = leftArray[i++];
            } else {
                numbers[k++] = rightArray[j++];
            }
        }
        while (i < leftArray.length) {
            numbers[k++] = leftArray[i++];
        }
        while (j < rightArray.length) {
            numbers[k++] = rightArray[j++];
        }
    }
    public static void main(String[] args) {
        double[] numbers = {3.6, 1.2, 5.4, 2.2, 4.8};
        mergeSort(numbers, 0, numbers.length - 1);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // mergeSort(new double[]{3.6, 1.2, 5.4, 2.2, 4.8}, 0, 4)
        // modifies the array to [1.2, 2.2, 3.6, 4.8, 5.4]
    }
}Code language: Java (java)

Explanation:

  • int mid = left + (right - left) / 2;: Calculates the midpoint in a way that avoids integer overflow on very large ranges, unlike (left + right) / 2.
  • mergeSort(numbers, left, mid); mergeSort(numbers, mid + 1, right);: Recursively sorts each half independently before any merging takes place.
  • if (leftArray[i] <= rightArray[j]): Compares the current front elements of both temporary arrays and copies the smaller one back into the original array first.
  • Alternative: You could sort using Arrays.sort() directly for production code, but implementing Merge Sort manually demonstrates how the divide-and-conquer recursion and merging steps fit together.

Exercise 5: Quick Sort Using the Hoare Partition Scheme

Problem Statement: Implement Quick Sort in Java using the Hoare partition scheme, where two pointers move toward each other from opposite ends of the array.

Purpose: This exercise helps you practice an in-place partitioning strategy that typically performs fewer swaps than the more commonly taught Lomuto partition scheme.

Given Input: int[] numbers = {8, 3, 7, 4, 9, 2, 6};

Expected Output: [2, 3, 4, 6, 7, 8, 9]

▼ Hint
  • Pick a pivot, commonly the first element of the current range.
  • Move a left pointer rightward until it finds an element greater than or equal to the pivot, and a right pointer leftward until it finds an element less than or equal to the pivot.
  • Swap the two elements the pointers land on and continue, until the pointers cross, at which point the crossing index becomes the partition boundary for the two recursive calls.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            int partitionIndex = hoarePartition(numbers, low, high);
            quickSort(numbers, low, partitionIndex);
            quickSort(numbers, partitionIndex + 1, high);
        }
    }
    private static int hoarePartition(int[] numbers, int low, int high) {
        int pivot = numbers[low];
        int i = low - 1;
        int j = high + 1;
        while (true) {
            do {
                i++;
            } while (numbers[i] < pivot);
            do {
                j--;
            } while (numbers[j] > pivot);
            if (i >= j) {
                return j;
            }
            int temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }
    }
    public static void main(String[] args) {
        int[] numbers = {8, 3, 7, 4, 9, 2, 6};
        quickSort(numbers, 0, numbers.length - 1);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // quickSort(new int[]{8, 3, 7, 4, 9, 2, 6}, 0, 6)
        // modifies the array to [2, 3, 4, 6, 7, 8, 9]
    }
}Code language: Java (java)

Explanation:

  • int pivot = numbers[low];: Chooses the first element of the current range as the pivot for this partition step.
  • do { i++; } while (numbers[i] < pivot);: Advances the left pointer past every element that already belongs on the left side of the pivot.
  • if (i >= j) return j;: Stops the partitioning once the two pointers meet or cross, and returns the right pointer’s position as the split point.
  • Alternative: You could use the Lomuto partition scheme, which places the pivot itself into its final sorted position, but it typically performs more swaps than the Hoare scheme used here.

Exercise 6: Radix Sort for 3-Digit Integers

Problem Statement: Implement Radix Sort in Java to efficiently sort an array of 3-digit integers.

Purpose: This exercise helps you practice a non-comparison-based sorting approach that processes numbers digit by digit, useful when sorting large collections of fixed-width numbers such as IDs or postal codes.

Given Input: int[] numbers = {329, 457, 657, 839, 436, 720, 355};

Expected Output: [329, 355, 436, 457, 657, 720, 839]

▼ Hint
  • Sort the numbers digit by digit, starting from the least significant digit (ones place) and moving toward the most significant digit (hundreds place).
  • Use a stable counting sort as the subroutine for sorting by a single digit, since stability preserves the ordering established by previous digit passes.
  • After sorting by every digit position, the entire array ends up fully sorted.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void radixSort(int[] numbers) {
        int max = Arrays.stream(numbers).max().getAsInt();
        for (int place = 1; max / place > 0; place *= 10) {
            countingSortByDigit(numbers, place);
        }
    }
    private static void countingSortByDigit(int[] numbers, int place) {
        int n = numbers.length;
        int[] output = new int[n];
        int[] count = new int[10];
        for (int num : numbers) {
            int digit = (num / place) % 10;
            count[digit]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            int digit = (numbers[i] / place) % 10;
            output[count[digit] - 1] = numbers[i];
            count[digit]--;
        }
        System.arraycopy(output, 0, numbers, 0, n);
    }
    public static void main(String[] args) {
        int[] numbers = {329, 457, 657, 839, 436, 720, 355};
        radixSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // radixSort(new int[]{329, 457, 657, 839, 436, 720, 355})
        // modifies the array to [329, 355, 436, 457, 657, 720, 839]
    }
}Code language: Java (java)

Explanation:

  • for (int place = 1; max / place > 0; place *= 10): Loops once for every digit position, moving from the ones place to the hundreds place by multiplying place by 10 each time.
  • int digit = (num / place) % 10;: Extracts a single digit at the current place value from each number.
  • count[digit] += count[digit - 1];: Converts the raw digit counts into cumulative counts, which tells each digit exactly where its last occurrence should land in the output array.
  • Alternative: You could use comparison-based sorts like Merge Sort or Quick Sort instead, but Radix Sort can outperform them on large sets of fixed-width numbers since it avoids direct element-to-element comparisons entirely.

Exercise 7: Linear Search for First and Last Occurrence

Problem Statement: Write a Java method to find the first and last occurrence of a target element in an unsorted array.

Purpose: This exercise helps you practice a single linear scan that tracks two separate pieces of state at once, useful whenever you need to locate a value’s full range within unsorted data.

Given Input: int[] numbers = {2, 4, 6, 4, 8, 4, 10}; int target = 4;

Expected Output: First occurrence = 1 and Last occurrence = 5

▼ Hint
  • Since the array is unsorted, you cannot use binary search, so a single pass through the array is required.
  • Record the index the first time you find the target, and keep updating a separate variable every time you find it again.
  • By the end of the loop, the first recorded index and the most recently updated index give you the first and last occurrences.
▼ Solution & Explanation
public class Main {
    public static int[] findFirstAndLast(int[] numbers, int target) {
        int first = -1;
        int last = -1;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == target) {
                if (first == -1) {
                    first = i;
                }
                last = i;
            }
        }
        return new int[]{first, last};
    }
    public static void main(String[] args) {
        int[] numbers = {2, 4, 6, 4, 8, 4, 10};
        int target = 4;
        int[] result = findFirstAndLast(numbers, target);
        System.out.println("First occurrence = " + result[0]);
        System.out.println("Last occurrence = " + result[1]);
        // Usage:
        // findFirstAndLast(new int[]{2, 4, 6, 4, 8, 4, 10}, 4) returns [1, 5]
    }
}Code language: Java (java)

Explanation:

  • if (first == -1) first = i;: Records the index only the first time the target is found, leaving it unchanged on every later match.
  • last = i;: Runs on every match, so by the end of the loop it holds the index of the most recent occurrence.
  • return new int[]{first, last};: Returns both results together as a small array, avoiding the need for two separate method calls over the same data.
  • Alternative: You could scan once from the front for the first occurrence and once from the back for the last, but that requires two passes compared to the single pass shown here.

Exercise 8: Binary Search (Iterative)

Problem Statement: Implement standard iterative Binary Search in Java on a sorted array, returning -1 if the element is not found.

Purpose: This exercise helps you practice narrowing a search range by half on every step, the core idea behind Binary Search and many other divide-and-conquer search techniques.

Given Input: int[] numbers = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72}; int target = 23;

Expected Output: Index = 5

▼ Hint
  • Maintain a low and high boundary representing the current search range.
  • Check the middle element of the range, if it matches the target, return its index immediately.
  • If the middle element is smaller than the target, search the right half by moving low, otherwise search the left half by moving high. Repeat until low passes high.
▼ Solution & Explanation
public class Main {
    public static int binarySearch(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] == target) {
                return mid;
            } else if (numbers[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] numbers = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
        int target = 23;
        System.out.println("Index = " + binarySearch(numbers, target));
        // Usage:
        // binarySearch(new int[]{2, 5, 8, 12, 16, 23, 38, 45, 56, 72}, 23) returns 5
        // binarySearch(new int[]{2, 5, 8, 12, 16, 23, 38, 45, 56, 72}, 100) returns -1
    }
}Code language: Java (java)

Explanation:

  • int mid = low + (high - low) / 2;: Computes the midpoint of the current range safely, avoiding overflow that (low + high) / 2 could cause on very large arrays.
  • else if (numbers[mid] < target) low = mid + 1;: Discards the entire left half of the range once it’s known the target must be larger.
  • while (low <= high): Continues narrowing the range until it becomes empty, at which point the target is confirmed absent.
  • Alternative: You could use Arrays.binarySearch() from the standard library for production code, but implementing it manually shows exactly how the range narrows on each step.

Exercise 9: Binary Search (Recursive)

Problem Statement: Implement the recursive version of Binary Search in Java.

Purpose: This exercise helps you practice expressing the same divide-and-conquer logic from the iterative version as a recursive function, reinforcing how a shrinking range maps naturally onto recursive calls.

Given Input: int[] numbers = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72}; int target = 72;

Expected Output: Index = 9

▼ Hint
  • Pass low and high as parameters to the recursive method so each call operates on a smaller range.
  • The base case is when low exceeds high, meaning the target is not present, at which point return -1.
  • Otherwise, compare the middle element to the target and recurse into whichever half could still contain it.
▼ Solution & Explanation
public class Main {
    public static int binarySearchRecursive(int[] numbers, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;
        if (numbers[mid] == target) {
            return mid;
        } else if (numbers[mid] < target) {
            return binarySearchRecursive(numbers, target, mid + 1, high);
        } else {
            return binarySearchRecursive(numbers, target, low, mid - 1);
        }
    }
    public static void main(String[] args) {
        int[] numbers = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
        int target = 72;
        int result = binarySearchRecursive(numbers, target, 0, numbers.length - 1);
        System.out.println("Index = " + result);
        // Usage:
        // binarySearchRecursive(new int[]{2, 5, 8, 12, 16, 23, 38, 45, 56, 72}, 72, 0, 9) returns 9
    }
}Code language: Java (java)

Explanation:

  • if (low > high) return -1;: Serves as the base case, triggered once the search range becomes empty without finding the target.
  • return binarySearchRecursive(numbers, target, mid + 1, high);: Recurses into the right half of the range when the target is known to be larger than the middle element.
  • return binarySearchRecursive(numbers, target, low, mid - 1);: Recurses into the left half when the target is smaller, narrowing the range on every call just like the iterative version.
  • Alternative: You could keep the iterative version from the previous exercise for production use, since it avoids the small overhead of extra recursive method calls while behaving identically.

Exercise 10: Binary Search Ceiling

Problem Statement: Given a sorted array and a target value, write a Java program to find the index of the smallest element that is greater than or equal to the target.

Purpose: This exercise helps you practice adapting Binary Search to return the closest valid position instead of only an exact match, a pattern used in range queries and insertion-point lookups.

Given Input: int[] numbers = {1, 3, 5, 7, 9, 11}; int target = 6;

Expected Output: Ceiling index = 3

▼ Hint
  • Unlike standard Binary Search, do not stop as soon as you fail to find an exact match, instead keep narrowing the range while remembering the best candidate seen so far.
  • Whenever the middle element is greater than or equal to the target, record its index as a potential answer and continue searching the left half for an even smaller valid candidate.
  • If the middle element is smaller than the target, it can never be the ceiling, so search the right half instead.
▼ Solution & Explanation
public class Main {
    public static int findCeilingIndex(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        int ceilingIndex = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] >= target) {
                ceilingIndex = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ceilingIndex;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11};
        int target = 6;
        System.out.println("Ceiling index = " + findCeilingIndex(numbers, target));
        // Usage:
        // findCeilingIndex(new int[]{1, 3, 5, 7, 9, 11}, 6) returns 3, the index of value 7
    }
}Code language: Java (java)

Explanation:

  • if (numbers[mid] >= target): Treats the middle element as a valid candidate for the ceiling whenever it is not smaller than the target.
  • ceilingIndex = mid; high = mid - 1;: Records the current candidate, then keeps searching the left half in case an even smaller valid value exists.
  • else low = mid + 1;: Moves past any element too small to ever be the ceiling, narrowing the search toward the right half.
  • Alternative: You could scan the array linearly for the first element greater than or equal to the target, but that runs in O(n) time compared to O(log n) with Binary Search.

Exercise 11: Binary Search Floor

Problem Statement: Given a sorted array and a target value, write a Java program to find the index of the largest element less than or equal to the target.

Purpose: This exercise helps you practice adapting Binary Search to return the closest valid position from below, the mirror image of the ceiling variation, useful in range queries and insertion-point lookups.

Given Input: int[] numbers = {1, 3, 5, 7, 9, 11}; int target = 6;

Expected Output: Floor index = 2

▼ Hint
  • Whenever the middle element is less than or equal to the target, record its index as a potential answer and continue searching the right half for an even larger valid candidate.
  • If the middle element is greater than the target, it can never be the floor, so search the left half instead.
  • The last recorded candidate once the range is exhausted is the floor index.
▼ Solution & Explanation
public class Main {
    public static int findFloorIndex(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        int floorIndex = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] <= target) {
                floorIndex = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return floorIndex;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11};
        int target = 6;
        System.out.println("Floor index = " + findFloorIndex(numbers, target));
        // Usage:
        // findFloorIndex(new int[]{1, 3, 5, 7, 9, 11}, 6) returns 2, the index of value 5
    }
}Code language: Java (java)

Explanation:

  • if (numbers[mid] <= target): Treats the middle element as a valid candidate for the floor whenever it does not exceed the target.
  • floorIndex = mid; low = mid + 1;: Records the current candidate, then keeps searching the right half in case an even closer valid value exists.
  • else high = mid - 1;: Skips any element too large to ever be the floor, narrowing the search toward the left half.
  • Alternative: You could scan the array linearly from the end for the first element less than or equal to the target, but that runs in O(n) time compared to O(log n) with Binary Search.

Exercise 12: Sort Products by Price Using a Custom Comparator

Problem Statement: Create a Product class with id, name, and price fields, then sort a list of products by price using a custom Comparator.

Purpose: This exercise helps you practice defining external sorting logic through the Comparator interface, useful when a class has no single natural ordering or when you need multiple different sort orders for the same objects.

Given Input: Products (1, "Laptop", 999.99), (2, "Mouse", 25.50), (3, "Keyboard", 45.00), (4, "Monitor", 199.99)

Expected Output: [Mouse ($25.5), Keyboard ($45.0), Monitor ($199.99), Laptop ($999.99)]

▼ Hint
  • Define a Comparator that compares two products based on their price field using Double.compare().
  • Pass this comparator to List.sort() instead of relying on the class implementing Comparable.
  • This approach keeps the sorting logic separate from the Product class itself, so you can define other comparators for name or id without modifying the class.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Main {
    static class Product {
        int id;
        String name;
        double price;
        Product(int id, String name, double price) {
            this.id = id;
            this.name = name;
            this.price = price;
        }
        @Override
        public String toString() {
            return name + " ($" + price + ")";
        }
    }
    public static void main(String[] args) {
        List<product> products = new ArrayList<>();
        products.add(new Product(1, "Laptop", 999.99));
        products.add(new Product(2, "Mouse", 25.50));
        products.add(new Product(3, "Keyboard", 45.00));
        products.add(new Product(4, "Monitor", 199.99));
        Comparator<product> byPrice = new Comparator<product>() {
            @Override
            public int compare(Product a, Product b) {
                return Double.compare(a.price, b.price);
            }
        };
        products.sort(byPrice);
        System.out.println(products);
        // Usage:
        // products.sort(byPrice) sorts the list to
        // [Mouse ($25.5), Keyboard ($45.0), Monitor ($199.99), Laptop ($999.99)]
    }
}</product></product></product>Code language: Java (java)

Explanation:

  • Comparator byPrice: Defines the comparison logic externally from the Product class, so the same class can be sorted differently depending on which comparator is used.
  • Double.compare(a.price, b.price): Safely compares two double values and returns a negative, zero, or positive result, avoiding the pitfalls of subtracting floating-point numbers directly.
  • products.sort(byPrice);: Sorts the list in place using the supplied comparator instead of any natural ordering the class might define.
  • Alternative: You could write the comparator more concisely as a lambda expression, Comparator.comparingDouble(p -> p.price), which achieves the same result with less boilerplate.

Exercise 13: Sort Students by GPA Using Comparable

Problem Statement: Implement the Comparable interface in a Student class so students sort naturally by their GPA in descending order.

Purpose: This exercise helps you practice defining a class’s natural ordering through Comparable, so that calling Collections.sort() directly produces the expected order without needing a separate comparator.

Given Input: Students ("Alice", 3.8), ("Bob", 3.5), ("Carol", 3.9)

Expected Output: [Carol (3.9), Alice (3.8), Bob (3.5)]

▼ Hint
  • Implement Comparable and override compareTo().
  • To sort in descending order, compare the other student’s GPA to the current student’s GPA, rather than the other way around.
  • Once compareTo() is implemented, Collections.sort() uses it automatically without any additional comparator.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
    static class Student implements Comparable<student> {
        String name;
        double gpa;
        Student(String name, double gpa) {
            this.name = name;
            this.gpa = gpa;
        }
        @Override
        public int compareTo(Student other) {
            return Double.compare(other.gpa, this.gpa);
        }
        @Override
        public String toString() {
            return name + " (" + gpa + ")";
        }
    }
    public static void main(String[] args) {
        List<student> students = new ArrayList<>();
        students.add(new Student("Alice", 3.8));
        students.add(new Student("Bob", 3.5));
        students.add(new Student("Carol", 3.9));
        Collections.sort(students);
        System.out.println(students);
        // Usage:
        // Collections.sort(students) sorts the list to
        // [Carol (3.9), Alice (3.8), Bob (3.5)]
    }
}</student></student>Code language: Java (java)

Explanation:

  • class Student implements Comparable: Declares that students have a defined natural ordering that sorting methods can rely on directly.
  • Double.compare(other.gpa, this.gpa): Reverses the usual comparison order by comparing the other student’s GPA first, which produces descending order instead of ascending.
  • Collections.sort(students);: Sorts the list using the natural ordering defined by compareTo(), with no comparator needed.
  • Alternative: You could keep the natural ascending order in compareTo() and instead sort with Collections.sort(students, Collections.reverseOrder()), which keeps ascending as the natural order while still allowing descending sorts when needed.

Exercise 14: Multi-level Sorting of Employees by Department and Salary

Problem Statement: Sort a list of Employee objects first by department name, and then by salary from highest to lowest within each department.

Purpose: This exercise helps you practice chaining multiple comparators together to express a primary sort key followed by a tiebreaker, a very common requirement in reporting and data grouping tasks.

Given Input: Employees ("Alice", "Engineering", 90000), ("Bob", "Sales", 70000), ("Carol", "Engineering", 95000), ("Dave", "Sales", 75000)

Expected Output: [Carol (Engineering, 95000.0), Alice (Engineering, 90000.0), Dave (Sales, 75000.0), Bob (Sales, 70000.0)]

▼ Hint
  • Build the primary comparator using Comparator.comparing() on the department field, which sorts departments alphabetically by default.
  • Chain thenComparing() onto the primary comparator to define the tiebreaker for employees within the same department.
  • Use Comparator.reverseOrder() on the salary comparison so that higher salaries come first within each department.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Main {
    static class Employee {
        String name;
        String department;
        double salary;
        Employee(String name, String department, double salary) {
            this.name = name;
            this.department = department;
            this.salary = salary;
        }
        @Override
        public String toString() {
            return name + " (" + department + ", " + salary + ")";
        }
    }
    public static void main(String[] args) {
        List<employee> employees = new ArrayList<>();
        employees.add(new Employee("Alice", "Engineering", 90000));
        employees.add(new Employee("Bob", "Sales", 70000));
        employees.add(new Employee("Carol", "Engineering", 95000));
        employees.add(new Employee("Dave", "Sales", 75000));
        Comparator<employee> byDepartmentThenSalary = Comparator
            .comparing((Employee e) -> e.department)
            .thenComparing((Employee e) -> e.salary, Comparator.reverseOrder());
        employees.sort(byDepartmentThenSalary);
        System.out.println(employees);
        // Usage:
        // employees.sort(byDepartmentThenSalary) sorts the list to
        // [Carol (Engineering, 95000.0), Alice (Engineering, 90000.0), Dave (Sales, 75000.0), Bob (Sales, 70000.0)]
    }
}</employee></employee>Code language: Java (java)

Explanation:

  • Comparator.comparing((Employee e) -> e.department): Establishes department name as the primary sort key, grouping employees from the same department together.
  • .thenComparing((Employee e) -> e.salary, Comparator.reverseOrder()): Applies a secondary sort by salary only among employees whose department is equal, using reverse order so higher salaries appear first.
  • employees.sort(byDepartmentThenSalary);: Applies both levels of the comparator chain in a single sort call.
  • Alternative: You could implement this with a single custom Comparator and manual if-else logic comparing departments first and then salaries, but chaining comparing() and thenComparing() is more readable and less error-prone.

Exercise 15: Case-Insensitive String Sort

Problem Statement: Sort a list of mixed-case strings alphabetically while ignoring case sensitivity.

Purpose: This exercise helps you practice using a built-in comparator designed for a common real-world need, avoiding the mistake of sorting mixed-case text with the default comparator, which would group all uppercase letters before all lowercase letters.

Given Input: List words = Arrays.asList("banana", "Apple", "cherry", "apple", "Banana");

Expected Output: [Apple, apple, banana, Banana, cherry]

▼ Hint
  • Java provides a ready-made comparator for this exact purpose, String.CASE_INSENSITIVE_ORDER.
  • Pass it directly to List.sort() instead of writing custom comparison logic.
  • Since Java’s sort is stable, words that are equal ignoring case keep their original relative order in the output.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
    public static void main(String[] args) {
        List<string> words = new ArrayList<>(Arrays.asList("banana", "Apple", "cherry", "apple", "Banana"));
        words.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println(words);
        // Usage:
        // words.sort(String.CASE_INSENSITIVE_ORDER) sorts the list to
        // [Apple, apple, banana, Banana, cherry]
    }
}</string>Code language: Java (java)

Explanation:

  • String.CASE_INSENSITIVE_ORDER: A built-in comparator that compares strings by converting both sides to a common case internally before comparing.
  • words.sort(...): Sorts the list in place using the supplied comparator instead of String’s default case-sensitive natural ordering.
  • Stable sort behavior: Because Java’s List.sort() is stable, "Apple" and "apple" keep their original relative order in the result since the comparator treats them as equal.
  • Alternative: You could write your own comparator using a.compareToIgnoreCase(b), which behaves the same way but requires writing the comparison logic yourself instead of using the built-in constant.

Exercise 16: K-th Smallest Element Using Quickselect

Problem Statement: Find the k-th smallest element in an unsorted array using a modified Quick Sort approach known as Quickselect.

Purpose: This exercise helps you practice adapting Quick Sort’s partitioning step to answer a selection question without fully sorting the array, achieving better average performance than sorting first.

Given Input: int[] numbers = {7, 10, 4, 3, 20, 15}; int k = 3;

Expected Output: 3rd smallest element = 7

▼ Hint
  • Partition the array around a pivot just like in Quick Sort, which places the pivot at its correct sorted index.
  • If the pivot’s index matches the target rank, you have found the answer immediately, there is no need to sort the rest of the array.
  • Otherwise, recurse into only the half of the array that could contain the target rank, discarding the other half entirely.
▼ Solution & Explanation
public class Main {
    public static int findKthSmallest(int[] numbers, int k) {
        return quickSelect(numbers, 0, numbers.length - 1, k - 1);
    }
    private static int quickSelect(int[] numbers, int low, int high, int targetIndex) {
        int pivotIndex = partition(numbers, low, high);
        if (pivotIndex == targetIndex) {
            return numbers[pivotIndex];
        } else if (targetIndex < pivotIndex) {
            return quickSelect(numbers, low, pivotIndex - 1, targetIndex);
        } else {
            return quickSelect(numbers, pivotIndex + 1, high, targetIndex);
        }
    }
    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (numbers[j] < pivot) {
                i++;
                int temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }
        int temp = numbers[i + 1];
        numbers[i + 1] = numbers[high];
        numbers[high] = temp;
        return i + 1;
    }
    public static void main(String[] args) {
        int[] numbers = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println("3rd smallest element = " + findKthSmallest(numbers, k));
        // Usage:
        // findKthSmallest(new int[]{7, 10, 4, 3, 20, 15}, 3) returns 7
    }
}Code language: Java (java)

Explanation:

  • quickSelect(numbers, 0, numbers.length - 1, k - 1);: Converts the 1-based rank k into a 0-based target index before starting the search.
  • if (pivotIndex == targetIndex) return numbers[pivotIndex];: Returns immediately once partitioning places an element exactly at the desired rank.
  • quickSelect(numbers, low, pivotIndex - 1, targetIndex);: Recurses only into the side of the partition that could contain the target rank, unlike full Quick Sort which recurses into both sides.
  • Alternative: You could sort the entire array first and read the element at index k – 1, but that costs O(n log n) time compared to the average O(n) time of Quickselect.

Exercise 17: Two Sum on a Sorted Array in O(n) Time

Problem Statement: Given a sorted array, find two numbers that add up to a specific target in O(n) time.

Purpose: This exercise helps you practice the two-pointer technique on already sorted data, avoiding the need for a nested loop or an auxiliary hash structure.

Given Input: int[] numbers = {2, 7, 11, 15}; int target = 9;

Expected Output: Indices = [0, 1]

▼ Hint
  • Place one pointer at the start of the array and one at the end.
  • If the sum of the two pointed elements equals the target, you have found the answer.
  • If the sum is too small, move the left pointer forward to increase it. If the sum is too large, move the right pointer backward to decrease it.
▼ Solution & Explanation
public class Main {
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left, right};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(numbers, target);
        System.out.println("Indices = [" + result[0] + ", " + result[1] + "]");
        // Usage:
        // twoSum(new int[]{2, 7, 11, 15}, 9) returns [0, 1]
    }
}Code language: Java (java)

Explanation:

  • int left = 0; int right = numbers.length - 1;: Starts with the widest possible pair, one at each end of the sorted array.
  • else if (sum < target) left++;: Moves the left pointer forward to a larger value when the current sum falls short of the target.
  • else right--;: Moves the right pointer backward to a smaller value when the current sum exceeds the target.
  • Alternative: You could use a HashMap to solve Two Sum in O(n) time on an unsorted array as well, but the two-pointer approach here takes advantage of the array already being sorted to avoid the extra memory a hash map requires.

Exercise 18: Search in a Rotated Sorted Array

Problem Statement: An array sorted in ascending order has been rotated at some pivot unknown to you beforehand. Search for a target value in O(log n) time.

Purpose: This exercise helps you practice adapting Binary Search to handle a broken sort order, a pattern useful whenever data has a mostly ordered but shifted structure, such as circular buffers.

Given Input: int[] numbers = {4, 5, 6, 7, 0, 1, 2}; int target = 0;

Expected Output: Index = 4

▼ Hint
  • At every step, at least one half of the current range, split by the middle index, is guaranteed to be normally sorted, even though the array as a whole is rotated.
  • Determine which half is sorted by comparing the element at low with the element at mid.
  • Check whether the target falls within the sorted half’s range, if it does, search that half, otherwise search the other half.
▼ Solution & Explanation
public class Main {
    public static int search(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] == target) {
                return mid;
            }
            if (numbers[low] <= numbers[mid]) {
                if (numbers[low] <= target && target < numbers[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (numbers[mid] < target && target <= numbers[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] numbers = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        System.out.println("Index = " + search(numbers, target));
        // Usage:
        // search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0) returns 4
    }
}Code language: Java (java)

Explanation:

  • if (numbers[low] <= numbers[mid]): Checks whether the left half of the current range is the normally sorted portion.
  • if (numbers[low] <= target && target < numbers[mid]): Confirms the target falls within the sorted left half’s range before deciding to search there.
  • Else branch: Handles the case where the right half is the sorted portion instead, applying the same range check against that half.
  • Alternative: You could first find the rotation pivot with a separate binary search, then run a standard binary search on the correct segment, but that requires two passes compared to the single-pass approach shown here.

Exercise 19: Sort Colors (Dutch National Flag Algorithm)

Problem Statement: Given an array containing only 0s, 1s, and 2s, sort it in-place in a single pass, using O(n) time and O(1) space.

Purpose: This exercise helps you practice the three-pointer partitioning technique known as the Dutch National Flag algorithm, useful whenever data only has a small, fixed number of distinct categories to sort into.

Given Input: int[] colors = {2, 0, 2, 1, 1, 0};

Expected Output: [0, 0, 1, 1, 2, 2]

▼ Hint
  • Use three pointers, low, mid, and high, dividing the array into four conceptual regions: 0s, 1s, unprocessed elements, and 2s.
  • If colors[mid] is 0, swap it to the low region and advance both low and mid. If it is 1, it is already in the right place, so just advance mid.
  • If colors[mid] is 2, swap it to the high region and shrink high, but do not advance mid yet, since the swapped-in element still needs to be examined.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void sortColors(int[] colors) {
        int low = 0;
        int mid = 0;
        int high = colors.length - 1;
        while (mid <= high) {
            if (colors[mid] == 0) {
                swap(colors, low, mid);
                low++;
                mid++;
            } else if (colors[mid] == 1) {
                mid++;
            } else {
                swap(colors, mid, high);
                high--;
            }
        }
    }
    private static void swap(int[] colors, int i, int j) {
        int temp = colors[i];
        colors[i] = colors[j];
        colors[j] = temp;
    }
    public static void main(String[] args) {
        int[] colors = {2, 0, 2, 1, 1, 0};
        sortColors(colors);
        System.out.println(Arrays.toString(colors));
        // Usage:
        // sortColors(new int[]{2, 0, 2, 1, 1, 0}) modifies the array to [0, 0, 1, 1, 2, 2]
    }
}Code language: Java (java)

Explanation:

  • if (colors[mid] == 0) { swap(colors, low, mid); low++; mid++; }: Moves a 0 into the growing zero region at the front, advancing both boundaries since the swapped-in element from low is already known to be a 1 or has already been processed.
  • else if (colors[mid] == 1) mid++;: Leaves a 1 in place, since the middle region is exactly where 1s belong once sorting finishes.
  • else { swap(colors, mid, high); high--; }: Moves a 2 into the shrinking region at the end without advancing mid, since the newly swapped-in element at mid still needs to be classified.
  • Alternative: You could count the number of 0s, 1s, and 2s in one pass and then overwrite the array in a second pass based on those counts, but that requires two passes compared to the single pass shown here.

Exercise 20: Find a Peak Element

Problem Statement: An element is considered a peak if it is greater than its neighbors. Find a peak element in an array using a Binary Search variation.

Purpose: This exercise helps you practice applying Binary Search to a problem that is not about finding an exact value, but about locating a position that satisfies a local structural condition.

Given Input: int[] numbers = {1, 2, 3, 1};

Expected Output: Peak index = 2

▼ Hint
  • If the middle element is greater than its right neighbor, a peak must exist somewhere at or before the middle index, so search the left half including mid.
  • Otherwise, a peak must exist somewhere after the middle index, so search the right half.
  • This works because the array is treated as bounded by negative infinity on both ends, guaranteeing at least one peak always exists.
▼ Solution & Explanation
public class Main {
    public static int findPeakElement(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] > numbers[mid + 1]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 1};
        System.out.println("Peak index = " + findPeakElement(numbers));
        // Usage:
        // findPeakElement(new int[]{1, 2, 3, 1}) returns 2, the index of value 3
    }
}Code language: Java (java)

Explanation:

  • if (numbers[mid] > numbers[mid + 1]): Signals that the sequence is descending at this point, meaning a peak lies at mid or somewhere to its left.
  • high = mid;: Keeps mid itself in the search range rather than excluding it, since mid could be the peak.
  • else low = mid + 1;: Moves past mid when the sequence is still ascending, since a peak must exist further to the right.
  • Alternative: You could scan the array linearly checking each element against both neighbors, but that runs in O(n) time compared to O(log n) with the Binary Search variation shown here.

Exercise 21: Intersection of Two Arrays Using Sorting

Problem Statement: Given two unsorted arrays, find their common elements. Use sorting to achieve an efficient solution.

Purpose: This exercise helps you practice combining sorting with a two-pointer scan, an approach that avoids the extra memory a hash-based solution would require.

Given Input: int[] arr1 = {1, 3, 4, 5, 7}; int[] arr2 = {3, 5, 7, 9};

Expected Output: [3, 5, 7]

▼ Hint
  • Sort both arrays first, this allows a linear scan instead of comparing every pair of elements.
  • Use two pointers, one for each array, advancing whichever pointer is at the smaller value.
  • When both pointers reference equal values, record that value and advance both pointers.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
    public static List<integer> findIntersection(int[] arr1, int[] arr2) {
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        List<integer> result = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] == arr2[j]) {
                result.add(arr1[i]);
                i++;
                j++;
            } else if (arr1[i] < arr2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 4, 5, 7};
        int[] arr2 = {3, 5, 7, 9};
        System.out.println(findIntersection(arr1, arr2));
        // Usage:
        // findIntersection(new int[]{1, 3, 4, 5, 7}, new int[]{3, 5, 7, 9}) returns [3, 5, 7]
    }
}</integer></integer>Code language: Java (java)

Explanation:

  • Arrays.sort(arr1); Arrays.sort(arr2);: Sorts both arrays so their elements can be compared in a single coordinated pass.
  • if (arr1[i] == arr2[j]): Records a common value and advances both pointers once a match is found.
  • else if (arr1[i] < arr2[j]) i++;: Advances the pointer sitting on the smaller value, since that value cannot match anything further ahead in the other array.
  • Alternative: You could use a HashSet to find the intersection in a single pass without sorting, but that trades the O(n log n) sorting cost for O(n) extra space.

Exercise 22: Optimized Bubble Sort Using the Flag Method

Problem Statement: Implement a traditional Bubble Sort that uses a boolean flag to track whether any swaps occurred during a pass. If no swaps happen, terminate the loop early to achieve O(n) best-case time complexity.

Purpose: This exercise helps you practice adding a simple early-exit optimization to a classic algorithm, showing how a small change can turn a worst-case O(n^2) sort into an O(n) pass on already sorted input.

Given Input: int[] numbers = {1, 2, 3, 4, 5};

Expected Output:

Sorted array = [1, 2, 3, 4, 5]
Passes performed = 1
▼ Hint
  • Declare a boolean flag before each pass and set it to false.
  • Set the flag to true only when an actual swap occurs during the inner loop.
  • After the inner loop finishes, check the flag, if it is still false, the array is already sorted, so break out of the outer loop.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static int bubbleSortOptimized(int[] numbers) {
        int n = numbers.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            passes++;
            for (int j = 0; j < n - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
        return passes;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        int passes = bubbleSortOptimized(numbers);
        System.out.println("Sorted array = " + Arrays.toString(numbers));
        System.out.println("Passes performed = " + passes);
        // Usage:
        // bubbleSortOptimized(new int[]{1, 2, 3, 4, 5}) returns 1
        // since the first pass finds no swaps and the loop terminates immediately
    }
}Code language: Java (java)

Explanation:

  • boolean swapped = false;: Resets the flag at the start of every pass so each pass is evaluated independently.
  • swapped = true;: Marks that at least one swap happened during this pass, meaning the array might still not be fully sorted.
  • if (!swapped) break;: Exits the outer loop immediately once a full pass completes without any swaps, since that means the array is already sorted.
  • Alternative: You could track the index of the last swap during each pass and shrink the inner loop’s range to that index next time, which skips over the already-sorted tail even faster than the flag alone.

Exercise 23: In-Place Selection Sort

Problem Statement: Write a Java program that sorts an array of integers using Selection Sort, performing the sorting entirely in-place by swapping the minimum found element with the first element of the unsorted sub-array.

Purpose: This exercise helps you practice the core Selection Sort pattern of repeatedly finding the minimum of the remaining unsorted portion and placing it at the front, using no auxiliary array.

Given Input: int[] numbers = {29, 10, 14, 37, 13};

Expected Output: [10, 13, 14, 29, 37]

▼ Hint
  • For each position i, scan the remaining unsorted portion of the array to find the index of the smallest element.
  • Swap that smallest element with the element currently at position i.
  • Only perform the swap if the minimum index is different from i, avoiding an unnecessary self-swap.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void selectionSort(int[] numbers) {
        int n = numbers.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (numbers[j] < numbers[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = numbers[i];
                numbers[i] = numbers[minIndex];
                numbers[minIndex] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] numbers = {29, 10, 14, 37, 13};
        selectionSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // selectionSort(new int[]{29, 10, 14, 37, 13}) modifies the array to [10, 13, 14, 29, 37]
    }
}Code language: Java (java)

Explanation:

  • int minIndex = i;: Assumes the current position holds the minimum until a smaller value is found further along.
  • if (numbers[j] < numbers[minIndex]) minIndex = j;: Updates the tracked minimum index whenever a smaller value is discovered in the unsorted portion.
  • if (minIndex != i): Skips the swap entirely when the current position already holds the minimum, avoiding a pointless self-assignment.
  • Alternative: You could track and swap the maximum element to the end of the array instead of the minimum to the front, which sorts in the same number of comparisons but builds the sorted portion from the opposite side.

Exercise 24: Insertion Sort Using Shifting

Problem Statement: Implement Insertion Sort by shifting elements to the right rather than performing multiple consecutive swaps, optimizing the inner loop’s operations.

Purpose: This exercise helps you practice the distinction between shifting and swapping, shifting moves each element once per position instead of performing a full three-step swap, cutting the work roughly in half.

Given Input: int[] numbers = {12, 11, 13, 5, 6};

Expected Output: [5, 6, 11, 12, 13]

▼ Hint
  • Store the current element to be inserted in a separate key variable first, since its original slot will be overwritten.
  • Shift every element in the sorted portion that is greater than key one position to the right, rather than swapping the key past each of them individually.
  • Once the shifting stops, place key into the now-empty slot it was shifted toward.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void insertionSort(int[] numbers) {
        int n = numbers.length;
        for (int i = 1; i < n; i++) {
            int key = numbers[i];
            int j = i - 1;
            while (j >= 0 && numbers[j] > key) {
                numbers[j + 1] = numbers[j];
                j--;
            }
            numbers[j + 1] = key;
        }
    }
    public static void main(String[] args) {
        int[] numbers = {12, 11, 13, 5, 6};
        insertionSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // insertionSort(new int[]{12, 11, 13, 5, 6}) modifies the array to [5, 6, 11, 12, 13]
    }
}Code language: Java (java)

Explanation:

  • int key = numbers[i];: Saves the value to be inserted before its slot gets overwritten by the shifting that follows.
  • numbers[j + 1] = numbers[j];: Shifts a single element one position to the right, which is cheaper than a full three-step swap since only one assignment happens per element moved.
  • numbers[j + 1] = key;: Places the saved key into its correct position once shifting has made room for it.
  • Alternative: You could perform a swap at every step of the inner loop instead of shifting, which produces the same final result but does roughly three times more assignments per comparison.

Exercise 25: Quick Sort with Median-of-Three Pivot Selection

Problem Statement: Implement Quick Sort using the Median-of-Three rule, taking the median of the first, middle, and last elements as the pivot, to prevent O(n^2) worst-case performance on already sorted data.

Purpose: This exercise helps you practice a pivot selection strategy that avoids the classic weakness of always picking the first or last element, which degrades to O(n^2) on sorted or reverse-sorted input.

Given Input: int[] numbers = {8, 3, 7, 4, 9, 2, 6, 1};

Expected Output: [1, 2, 3, 4, 6, 7, 8, 9]

▼ Hint
  • Look at the elements at the low, middle, and high indices of the current range.
  • Sort these three positions relative to each other using at most three comparisons and swaps, which leaves the median value sitting at the middle index.
  • Move that median value to the end of the range (or wherever your partition scheme expects the pivot) before running the normal partition step.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            int medianIndex = medianOfThree(numbers, low, high);
            swap(numbers, medianIndex, high);
            int partitionIndex = partition(numbers, low, high);
            quickSort(numbers, low, partitionIndex - 1);
            quickSort(numbers, partitionIndex + 1, high);
        }
    }
    private static int medianOfThree(int[] numbers, int low, int high) {
        int mid = low + (high - low) / 2;
        if (numbers[low] > numbers[mid]) {
            swap(numbers, low, mid);
        }
        if (numbers[low] > numbers[high]) {
            swap(numbers, low, high);
        }
        if (numbers[mid] > numbers[high]) {
            swap(numbers, mid, high);
        }
        return mid;
    }
    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (numbers[j] < pivot) {
                i++;
                swap(numbers, i, j);
            }
        }
        swap(numbers, i + 1, high);
        return i + 1;
    }
    private static void swap(int[] numbers, int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
    public static void main(String[] args) {
        int[] numbers = {8, 3, 7, 4, 9, 2, 6, 1};
        quickSort(numbers, 0, numbers.length - 1);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // quickSort(new int[]{8, 3, 7, 4, 9, 2, 6, 1}, 0, 7)
        // modifies the array to [1, 2, 3, 4, 6, 7, 8, 9]
    }
}Code language: Java (java)

Explanation:

  • medianOfThree(numbers, low, high): Sorts the low, middle, and high elements relative to each other, which leaves the median value at the middle index.
  • swap(numbers, medianIndex, high);: Moves the chosen median pivot to the end of the range, so the existing Lomuto-style partition logic can use it directly.
  • partition(numbers, low, high): Partitions the range around the pivot exactly as in standard Quick Sort, since only the pivot selection strategy has changed.
  • Alternative: You could pick a pivot completely at random instead of using the median of three fixed positions, which also avoids worst-case behavior on sorted input but relies on randomness rather than a deterministic rule.

Exercise 26: Two-Way Merge Sort with a Dedicated Merge Helper

Problem Statement: Implement the classic top-down Merge Sort in Java. Write a dedicated merge() helper function that takes two sorted halves of an array and combines them into a single sorted array using a temporary workspace.

Purpose: This exercise helps you practice reusing a single temporary array across the entire sort instead of allocating a new one at every recursive call, which reduces memory churn on large inputs.

Given Input: int[] numbers = {38, 27, 43, 3, 9, 82, 10};

Expected Output: [3, 9, 10, 27, 38, 43, 82]

▼ Hint
  • Allocate a single temporary array once, before any recursive sorting begins, rather than creating new arrays inside every call to merge().
  • Inside merge(), copy the current range into the temporary array first, then merge back into the original array by comparing values from the two halves.
  • Recurse on the left half, then the right half, then merge the two sorted halves together, in that order.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void mergeSort(int[] numbers) {
        int[] temp = new int[numbers.length];
        mergeSort(numbers, temp, 0, numbers.length - 1);
    }
    private static void mergeSort(int[] numbers, int[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(numbers, temp, left, mid);
            mergeSort(numbers, temp, mid + 1, right);
            merge(numbers, temp, left, mid, right);
        }
    }
    private static void merge(int[] numbers, int[] temp, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = numbers[i];
        }
        int i = left;
        int j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                numbers[k++] = temp[i++];
            } else {
                numbers[k++] = temp[j++];
            }
        }
        while (i <= mid) {
            numbers[k++] = temp[i++];
        }
        while (j <= right) {
            numbers[k++] = temp[j++];
        }
    }
    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // mergeSort(new int[]{38, 27, 43, 3, 9, 82, 10})
        // modifies the array to [3, 9, 10, 27, 38, 43, 82]
    }
}Code language: Java (java)

Explanation:

  • int[] temp = new int[numbers.length];: Allocates the workspace array exactly once, before recursion begins, instead of on every call to merge().
  • for (int i = left; i <= right; i++) temp[i] = numbers[i];: Copies the current range into the shared temporary array so both halves can be read safely while writing the merged result back into numbers.
  • if (temp[i] <= temp[j]): Compares the current front elements of both halves within the temporary array and writes the smaller one back into the original array.
  • Alternative: You could create a new temporary array inside every call to merge() using Arrays.copyOfRange(), which is simpler to write but allocates far more memory over the course of the full sort.

Exercise 27: Shell Sort (Diminishing Increment Sort)

Problem Statement: Implement Shell Sort, an extension of Insertion Sort that allows the exchange of far-apart elements, using a halving gap sequence (N/2, N/4, and so on down to 1).

Purpose: This exercise helps you practice generalizing Insertion Sort to compare elements separated by a gap rather than only adjacent elements, which moves misplaced values toward their correct position faster on larger arrays.

Given Input: int[] numbers = {12, 34, 54, 2, 3};

Expected Output: [2, 3, 12, 34, 54]

▼ Hint
  • Start with a large gap, typically half the array length, and perform a gapped Insertion Sort using that gap.
  • Reduce the gap on each outer iteration, commonly by halving it, and repeat the gapped Insertion Sort.
  • Once the gap reaches 1, the final pass behaves exactly like standard Insertion Sort, but on an array that is already mostly sorted from the earlier passes.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static void shellSort(int[] numbers) {
        int n = numbers.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int key = numbers[i];
                int j = i;
                while (j >= gap && numbers[j - gap] > key) {
                    numbers[j] = numbers[j - gap];
                    j -= gap;
                }
                numbers[j] = key;
            }
        }
    }
    public static void main(String[] args) {
        int[] numbers = {12, 34, 54, 2, 3};
        shellSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Usage:
        // shellSort(new int[]{12, 34, 54, 2, 3}) modifies the array to [2, 3, 12, 34, 54]
    }
}Code language: Java (java)

Explanation:

  • for (int gap = n / 2; gap > 0; gap /= 2): Repeats the sorting process with a shrinking gap, starting wide and ending at a gap of 1.
  • while (j >= gap && numbers[j - gap] > key): Compares and shifts elements that are gap positions apart instead of only adjacent elements, allowing far-apart out-of-place values to move quickly.
  • numbers[j] = key;: Places the current key into its correct position for the current gap size once shifting stops.
  • Alternative: You could use Knuth’s increment sequence (1, 4, 13, 40, …) instead of simple halving, which is known to perform better on average than the halving sequence used here.

Exercise 28: Merge Overlapping Intervals

Problem Statement: Given a collection of intervals, such as [1, 3] and [2, 6], merge all overlapping intervals using sorting.

Purpose: This exercise helps you practice sorting by a custom key before scanning linearly to combine related items, a pattern used in scheduling, calendar merging, and range-based data cleanup.

Given Input: int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};

Expected Output: [1, 6] [8, 10] [15, 18]

▼ Hint
  • Sort the intervals by their starting value first, this guarantees that any interval which could overlap with the current one will be encountered right after it.
  • Walk through the sorted intervals, comparing each one to the last interval already added to the result.
  • If the current interval’s start is less than or equal to the last added interval’s end, they overlap, so extend the end of the last interval instead of adding a new one.
▼ Solution & Explanation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
    public static List<int[]> mergeIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        return merged;
    }
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        List<int[]> merged = mergeIntervals(intervals);
        for (int[] interval : merged) {
            System.out.print(Arrays.toString(interval) + " ");
        }
        System.out.println();
        // Usage:
        // mergeIntervals(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})
        // returns intervals [1, 6], [8, 10], [15, 18]
    }
}</int[]></int[]></int[]>Code language: Java (java)

Explanation:

  • Arrays.sort(intervals, (a, b) -> a[0] - b[0]);: Sorts the intervals by their starting value, which guarantees overlapping intervals are always adjacent in the sorted order.
  • merged.get(merged.size() - 1)[1] < interval[0]: Checks whether the current interval starts after the last merged interval ends, meaning the two do not overlap at all.
  • Math.max(merged.get(merged.size() - 1)[1], interval[1]);: Extends the end of the last merged interval to cover the current interval when they do overlap.
  • Alternative: You could sort by start value and also track the maximum end seen so far without modifying the intervals in place, storing new merged ranges in a separate structure instead.

Exercise 29: Find the Minimum in a Rotated Sorted Array with Duplicates

Problem Statement: Find the minimum element in a rotated sorted array that may contain duplicate values.

Purpose: This exercise helps you practice handling the extra ambiguity that duplicates introduce into a rotated Binary Search problem, where the standard rotation-detection logic can no longer rely purely on comparing endpoints.

Given Input: int[] numbers = {2, 2, 2, 0, 1, 2};

Expected Output: Minimum = 0

▼ Hint
  • If the middle element is greater than the element at the high pointer, the minimum must be somewhere to the right of the middle.
  • If the middle element is smaller, the minimum must be at the middle or somewhere to its left.
  • If the middle element equals the element at the high pointer, you cannot tell which side the minimum is on, so simply shrink the range by moving the high pointer inward by one.
▼ Solution & Explanation
public class Main {
    public static int findMin(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] > numbers[high]) {
                low = mid + 1;
            } else if (numbers[mid] < numbers[high]) {
                high = mid;
            } else {
                high--;
            }
        }
        return numbers[low];
    }
    public static void main(String[] args) {
        int[] numbers = {2, 2, 2, 0, 1, 2};
        System.out.println("Minimum = " + findMin(numbers));
        // Usage:
        // findMin(new int[]{2, 2, 2, 0, 1, 2}) returns 0
    }
}Code language: Java (java)

Explanation:

  • if (numbers[mid] > numbers[high]) low = mid + 1;: Confirms the rotation point, and therefore the minimum, lies strictly to the right of the middle index.
  • else if (numbers[mid] < numbers[high]) high = mid;: Confirms the minimum lies at the middle index or somewhere to its left, keeping mid in the range.
  • else high--;: Handles the ambiguous case caused by duplicate values by simply narrowing the range by one, since numbers[high] has an equal duplicate elsewhere and is safe to discard.
  • Alternative: You could fall back to a full linear scan whenever duplicates are detected, which guarantees correctness but loses the O(log n) average-case benefit that this approach still provides on most inputs.

Problem Statement: Implement a variation of Linear Search that places the target element at the very end of the array as a sentinel value, eliminating the need to check whether the array boundary has been reached during every iteration of the loop.

Purpose: This exercise helps you practice a classic micro-optimization technique where removing a redundant bounds check from a hot loop can measurably reduce the number of comparisons performed on large arrays.

Given Input: int[] numbers = {4, 2, 7, 1, 9}; int target = 7;

Expected Output: Index = 2

▼ Hint
  • Before searching, save the last element of the array and temporarily overwrite it with the target value, this guarantees the loop will always find a match.
  • Loop through the array comparing only against the target, without any separate check on the loop index, since the sentinel guarantees termination.
  • After the loop, restore the original last element, then determine whether the match found was a genuine one or just the sentinel itself.
▼ Solution & Explanation
public class Main  {
    public static int sentinelSearch(int[] numbers, int target) {
        int n = numbers.length;
        int last = numbers[n - 1];
        numbers[n - 1] = target;
        int i = 0;
        while (numbers[i] != target) {
            i++;
        }
        numbers[n - 1] = last;
        if (i < n - 1 || numbers[n - 1] == target) {
            return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] numbers = {4, 2, 7, 1, 9};
        int target = 7;
        System.out.println("Index = " + sentinelSearch(numbers, target));
        // Usage:
        // sentinelSearch(new int[]{4, 2, 7, 1, 9}, 7) returns 2
        // sentinelSearch(new int[]{4, 2, 7, 1, 9}, 100) returns -1
    }
}Code language: Java (java)

Explanation:

  • numbers[n - 1] = target;: Temporarily plants the target as a sentinel at the very end of the array, guaranteeing the search loop will always find a match and never run past the array bounds.
  • while (numbers[i] != target) i++;: Advances through the array checking only for the target, with no separate i < n bounds check needed since the sentinel guarantees a match exists.
  • if (i < n - 1 || numbers[n - 1] == target): Distinguishes a genuine match found before the last index from a match that only occurred because of the sentinel, in which case the original last element is checked to see if it was actually equal to the target as well.
  • Alternative: You could use standard Linear Search with an explicit i < n bounds check on every iteration, which is simpler to read but performs one extra comparison per iteration compared to the sentinel approach.

Problem Statement: Instead of dividing the search space into two halves like Binary Search, implement Ternary Search, which divides a sorted array into three equal segments using two midpoints.

Purpose: This exercise helps you practice generalizing the divide-and-conquer search pattern to more than two partitions, and encourages you to reason about whether more partitions actually means better performance.

Given Input: int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15}; int target = 11;

Expected Output: Index = 5

▼ Hint
  • Calculate two midpoints, mid1 and mid2, that split the current range into three roughly equal segments.
  • Check whether the target equals either midpoint directly.
  • If the target is smaller than numbers[mid1], recurse into the first segment. If it is larger than numbers[mid2], recurse into the third segment. Otherwise, recurse into the middle segment.
▼ Solution & Explanation
public class Main {
    public static int ternarySearch(int[] numbers, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid1 = low + (high - low) / 3;
        int mid2 = high - (high - low) / 3;
        if (numbers[mid1] == target) {
            return mid1;
        }
        if (numbers[mid2] == target) {
            return mid2;
        }
        if (target < numbers[mid1]) {
            return ternarySearch(numbers, target, low, mid1 - 1);
        } else if (target > numbers[mid2]) {
            return ternarySearch(numbers, target, mid2 + 1, high);
        } else {
            return ternarySearch(numbers, target, mid1 + 1, mid2 - 1);
        }
    }
    public static void main(String[] args) {
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 11;
        int result = ternarySearch(numbers, target, 0, numbers.length - 1);
        System.out.println("Index = " + result);
        // Usage:
        // ternarySearch(new int[]{1, 3, 5, 7, 9, 11, 13, 15}, 11, 0, 7) returns 5
    }
}Code language: Java (java)

Explanation:

  • int mid1 = low + (high - low) / 3; int mid2 = high - (high - low) / 3;: Splits the current range into three roughly equal segments using two calculated midpoints instead of one.
  • if (target < numbers[mid1]): Narrows the search to the first third of the range once it’s known the target must be smaller than both midpoints.
  • return ternarySearch(numbers, target, mid1 + 1, mid2 - 1);: Falls back to the middle segment when the target lies between the two midpoint values.
  • Alternative and performance comparison: Although Ternary Search divides the range into three parts instead of two, it needs two comparisons per level to decide which segment to recurse into, compared to Binary Search’s one comparison per level. Ternary Search reduces the range to one-third each time, giving a recursion depth of about log base 3 of n, but the extra comparison per level means the total number of comparisons ends up comparable to, or slightly worse than, Binary Search’s log base 2 of n. In practice, Binary Search remains the more efficient and simpler choice for searching a sorted array.

Problem Statement: Implement Interpolation Search for a uniformly distributed sorted array. Instead of always probing the exact middle, calculate a probing position based on the value of the bounds, similar to how a person might flip directly toward the right page when looking up a name in a phone book.

Purpose: This exercise helps you practice using the actual values in the array, not just their positions, to make a smarter guess about where the target is likely to be, which can outperform Binary Search on evenly spread data.

Given Input: int[] numbers = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; int target = 70;

Expected Output: Index = 6

▼ Hint
  • Instead of always checking the middle index, estimate the probing position using the proportion of the target’s value between the values at low and high.
  • Guard against dividing by zero when numbers[high] equals numbers[low], since that would mean every element in the range is identical.
  • Adjust low or high based on whether the probed value is smaller or larger than the target, just as in Binary Search.
▼ Solution & Explanation
public class Main {
    public static int interpolationSearch(int[] numbers, int target) {
        int low = 0;
        int high = numbers.length - 1;
        while (low <= high && target >= numbers[low] && target <= numbers[high]) {
            if (numbers[high] == numbers[low]) {
                if (numbers[low] == target) {
                    return low;
                }
                return -1;
            }
            int pos = low + (int) ((long) (target - numbers[low]) * (high - low) / (numbers[high] - numbers[low]);
            if (numbers[pos] == target) {
                return pos;
            } else if (numbers[pos] < target) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        int target = 70;
        System.out.println("Index = " + interpolationSearch(numbers, target));
        // Usage:
        // interpolationSearch(new int[]{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}, 70) returns 6
    }
}Code language: Java (java)

Explanation:

  • int pos = low + (target - numbers[low]) * (high - low) / (numbers[high] - numbers[low]);: Estimates where the target is likely to be based on its value relative to the values at the current bounds, rather than always guessing the midpoint.
  • (long) cast: Prevents integer overflow during the multiplication step when working with large values or wide ranges.
  • if (numbers[high] == numbers[low]): Handles the edge case where every remaining element has the same value, avoiding a division by zero in the position formula.
  • Alternative: You could use standard Binary Search instead, which performs consistently at O(log n) regardless of data distribution, while Interpolation Search can degrade to O(n) on non-uniformly distributed data despite averaging O(log log n) on uniform data.

Exercise 33: Remove Duplicates from a Sorted Array In-Place

Problem Statement: Given a sorted array, remove the duplicate elements in-place so that each element appears only once, and return the new length of the array. Do not allocate extra space for another array.

Purpose: This exercise helps you practice the two-pointer technique for in-place array compaction, a pattern used whenever you need to filter or deduplicate data without allocating additional memory.

Given Input: int[] numbers = {1, 1, 2, 2, 3, 4, 4, 5};

Expected Output:

New length = 5
Array up to new length = [1, 2, 3, 4, 5]
▼ Hint
  • Use a writeIndex pointer that tracks where the next unique element should be placed, and a readIndex pointer that scans through the entire array.
  • Since the array is sorted, duplicates are always adjacent, so compare each element only to the most recently written unique value.
  • Whenever a new unique value is found, write it at writeIndex and advance that pointer.
▼ Solution & Explanation
import java.util.Arrays;
public class Main {
    public static int removeDuplicates(int[] numbers) {
        if (numbers.length == 0) {
            return 0;
        }
        int writeIndex = 1;
        for (int readIndex = 1; readIndex < numbers.length; readIndex++) {
            if (numbers[readIndex] != numbers[writeIndex - 1]) {
                numbers[writeIndex] = numbers[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }
    public static void main(String[] args) {
        int[] numbers = {1, 1, 2, 2, 3, 4, 4, 5};
        int newLength = removeDuplicates(numbers);
        System.out.println("New length = " + newLength);
        System.out.println("Array up to new length = " + Arrays.toString(Arrays.copyOf(numbers, newLength)));
        // Usage:
        // removeDuplicates(new int[]{1, 1, 2, 2, 3, 4, 4, 5}) returns 5
        // and the first 5 elements of the array become [1, 2, 3, 4, 5]
    }
}Code language: Java (java)

Explanation:

  • int writeIndex = 1;: Starts at index 1 since the first element is always unique by definition, having no earlier element to compare against.
  • if (numbers[readIndex] != numbers[writeIndex - 1]): Compares the current element only to the last written unique value, which works because duplicates in a sorted array are always adjacent.
  • numbers[writeIndex] = numbers[readIndex]; writeIndex++;: Writes the new unique value into its compacted position and advances the write pointer, all without allocating a second array.
  • Alternative: You could copy unique elements into a new array or a LinkedHashSet, but that uses O(n) extra space, unlike the O(1) space used by the in-place two-pointer approach here.

Exercise 34: Merge Two Sorted Arrays In-Place

Problem Statement: Given two sorted arrays, arr1 of size m + n with enough empty space at the end to hold n additional elements, and arr2 of size n, merge arr2 into arr1 so the resulting array is sorted. Do not use an auxiliary array.

Purpose: This exercise helps you practice merging from the back of an array rather than the front, a technique that avoids overwriting values in arr1 that have not been read yet.

Given Input: int[] arr1 = {1, 3, 5, 0, 0, 0}; int m = 3; int[] arr2 = {2, 4, 6}; int n = 3;

Expected Output: [1, 2, 3, 4, 5, 6]

▼ Hint
  • Merging from the front would require shifting already-placed elements in arr1 to make room, so instead start filling from the very last index of arr1 and work backward.
  • Compare the last real element of arr1 (before its empty space) with the last element of arr2, placing the larger one at the current end position.
  • If arr2 still has remaining elements after arr1‘s original elements are exhausted, copy them directly, since any remaining elements in arr1 are already smaller and already in place.
▼ Solution & Explanation
import java.util.Arrays;

public class Main {

    public static void merge(int[] arr1, int m, int[] arr2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (arr1[i] > arr2[j]) {
                arr1[k--] = arr1[i--];
            } else {
                arr1[k--] = arr2[j--];
            }
        }

        while (j >= 0) {
            arr1[k--] = arr2[j--];
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 0, 0, 0};
        int m = 3;
        int[] arr2 = {2, 4, 6};
        int n = 3;

        merge(arr1, m, arr2, n);

        System.out.println(Arrays.toString(arr1));

        // Usage:
        // merge(new int[]{1, 3, 5, 0, 0, 0}, 3, new int[]{2, 4, 6}, 3)
        // modifies arr1 to [1, 2, 3, 4, 5, 6]
    }
}Code language: Java (java)

Explanation:

  • int k = m + n - 1;: Starts writing from the very last index of arr1, the natural place to build the merged result from the back forward.
  • if (arr1[i] > arr2[j]): Places the larger of the two current candidates at the current end position, moving backward through whichever array it came from.
  • while (j >= 0) arr1[k--] = arr2[j--];: Copies any remaining elements from arr2 once arr1‘s original elements are exhausted, since a remaining i >= 0 case would already have its elements correctly in place.
  • Alternative: You could merge into a separate temporary array and copy the result back into arr1, but that requires O(m + n) extra space compared to the O(1) space used by merging from the back in-place.

Exercise 35: Search a 2D Matrix

Problem Statement: Implement an efficient algorithm that searches for a value in an m x n matrix where each row and each column is individually sorted in ascending order.

Purpose: This exercise helps you practice the staircase search technique, which takes advantage of row and column ordering together to eliminate an entire row or column with every comparison, without needing the whole matrix to be sorted as one continuous sequence.

Given Input:

int[][] matrix = {
    {1, 4, 7, 11},
    {2, 5, 8, 12},
    {3, 6, 9, 16},
    {10, 13, 14, 17}
};
int target = 5;

Expected Output: Found = true

▼ Hint
  • Start at the top-right corner of the matrix, since that position has the useful property of being the largest value in its row and the smallest value in its column.
  • If the current value is greater than the target, the entire column can be eliminated, so move one step to the left.
  • If the current value is less than the target, the entire row can be eliminated, so move one step down. Repeat until the target is found or you move outside the matrix bounds.
▼ Solution & Explanation
public class Main {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 4, 7, 11},
            {2, 5, 8, 12},
            {3, 6, 9, 16},
            {10, 13, 14, 17}
        };
        int target = 5;
        System.out.println("Found = " + searchMatrix(matrix, target));
        // Usage:
        // searchMatrix(matrix, 5) returns true
        // searchMatrix(matrix, 15) returns false
    }
}Code language: Java (java)

Explanation:

  • int col = matrix[0].length - 1;: Starts the search at the top-right corner, the only position guaranteed to be both the maximum of its row and the minimum of its column.
  • else if (matrix[row][col] > target) col--;: Eliminates the entire current column when its top value already exceeds the target, since every value below it in that column is even larger.
  • else row++;: Eliminates the entire current row when its rightmost value is still smaller than the target, since every value to its left in that row is even smaller.
  • Alternative: You could run a separate Binary Search on each row independently, giving O(m log n) time overall, but the staircase approach shown here runs in O(m + n) time by using both row and column ordering together in a single pass.

TweetF  sharein  shareP  Pin

About Vishal

I’m Vishal Hule, the Founder of PYnative.com. As a Python developer, I enjoy assisting students, developers, and learners. Follow me on Twitter.

Related Tutorial Topics:

Java Exercises

All Coding Exercises:

C Exercises
C++ Exercises
Python Exercises
Java Exercises
C# Exercises

Python Exercises and Quizzes

Free coding exercises and quizzes cover Python basics, data structure, data analytics, and more.

  • 15+ Topic-specific Exercises and Quizzes
  • Each Exercise contains 25+ questions
  • Each Quiz contains 25 MCQ
Exercises
Quizzes

Leave a Reply

your email address will NOT be published. all comments are moderated according to our comment policy.

Use <pre> tag for posting code. E.g. <pre> Your entire code </pre>

About PYnative

PYnative.com is for Python lovers. Here, You can get Tutorials, Exercises, and Quizzes to practice and improve your Python skills.

Follow Us

To get New Python Tutorials, Exercises, and Quizzes

Explore Python

Coding Exercises

Legal Stuff

We use cookies to improve your experience. While using PYnative, you agree to have read and accepted our:

Copyright © 2018–2026 pynative.com