Array & String Problems

Binary Search Variants (15 points)

Create a class BinarySearchVariants.java with the following methods:

1. int firstOccurrence(int[] arr, int target) - Find the first occurrence of target in a sorted array
2. int lastOccurrence(int[] arr, int target) - Find the last occurrence of target in a sorted array
3. int countOccurrences(int[] arr, int target) - Count total occurrences using the above methods
4. int searchRotatedArray(int[] arr, int target) - Search in a rotated sorted array

// Example usage:
int[] arr = {1, 2, 2, 2, 3, 4, 5};
firstOccurrence(arr, 2);  // Returns: 1
lastOccurrence(arr, 2);   // Returns: 3
countOccurrences(arr, 2); // Returns: 3

int[] rotated = {4, 5, 6, 7, 0, 1, 2};
searchRotatedArray(rotated, 0); // Returns: 4

Sorting Algorithms (15 points)

Create a class SortingAlgorithms.java that implements:

1. void bubbleSort(int[] arr) - Bubble sort with optimization for already sorted arrays
2. void selectionSort(int[] arr) - Selection sort implementation
3. void insertionSort(int[] arr) - Insertion sort implementation
4. void mergeSort(int[] arr, int left, int right) - Merge sort (divide and conquer)

For each algorithm, add a counter to track the number of comparisons and swaps made.

// Each method should print:
// "Bubble Sort: X comparisons, Y swaps"
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
// Output: Bubble Sort: 21 comparisons, 16 swaps
// Array: [11, 12, 22, 25, 34, 64, 90]

Two-Pointer Problems (15 points)

Create a class TwoPointerProblems.java with:

1. int[] twoSum(int[] arr, int target) - Find two numbers in a sorted array that sum to target. Return their indices.
2. void reverseArray(int[] arr, int start, int end) - Reverse array in-place between indices
3. int removeDuplicates(int[] arr) - Remove duplicates from sorted array in-place, return new length
4. void moveZeroes(int[] arr) - Move all zeroes to end while maintaining order of non-zero elements

// Example usage:
int[] arr1 = {2, 7, 11, 15};
twoSum(arr1, 9); // Returns: [0, 1] (arr1[0] + arr1[1] = 9)

int[] arr2 = {1, 1, 2, 2, 3};
removeDuplicates(arr2); // Returns: 3, arr2 becomes [1, 2, 3, ...]

int[] arr3 = {0, 1, 0, 3, 12};
moveZeroes(arr3); // arr3 becomes [1, 3, 12, 0, 0]

Sliding Window Problems (15 points)

Create a class SlidingWindowProblems.java with:

1. int maxSumSubarray(int[] arr, int k) - Find maximum sum of any contiguous subarray of size k
2. int minSubarrayLength(int[] arr, int target) - Find minimum length subarray with sum ≥ target
3. int longestSubarrayWithKDistinct(int[] arr, int k) - Longest subarray with at most k distinct elements

// Example usage:
int[] arr1 = {2, 1, 5, 1, 3, 2};
maxSumSubarray(arr1, 3); // Returns: 9 (subarray [5, 1, 3])

int[] arr2 = {2, 3, 1, 2, 4, 3};
minSubarrayLength(arr2, 7); // Returns: 2 (subarray [4, 3])

int[] arr3 = {1, 2, 1, 2, 3};
longestSubarrayWithKDistinct(arr3, 2); // Returns: 4 ([1, 2, 1, 2])

Array Manipulation Challenge (15 points)

Create a class ArrayChallenge.java with:

1. int[] productExceptSelf(int[] nums) - Return array where each element is product of all other elements (without using division)
2. int findMissingNumber(int[] arr, int n) - Find missing number in array containing 1 to n with one missing
3. int majorityElement(int[] arr) - Find element appearing more than n/2 times (Boyer-Moore voting)
4. int[][] mergeIntervals(int[][] intervals) - Merge overlapping intervals

// Example usage:
int[] arr1 = {1, 2, 3, 4};
productExceptSelf(arr1); // Returns: [24, 12, 8, 6]

int[] arr2 = {1, 2, 4, 5, 6};
findMissingNumber(arr2, 6); // Returns: 3

int[] arr3 = {3, 2, 3};
majorityElement(arr3); // Returns: 3

int[][] intervals = {{1,3}, {2,6}, {8,10}, {15,18}};
mergeIntervals(intervals); // Returns: {{1,6}, {8,10}, {15,18}}

String Basics (15 points)

Create a class StringBasics.java with:

1. String reverseString(String s) - Reverse a string without using StringBuilder.reverse()
2. String reverseWords(String s) - Reverse order of words in a sentence
3. boolean isPalindrome(String s) - Check if string is palindrome (ignore non-alphanumeric, case-insensitive)
4. String longestPalindromicSubstring(String s) - Find longest palindromic substring

// Example usage:
reverseString("hello"); // Returns: "olleh"
reverseWords("the sky is blue"); // Returns: "blue is sky the"
isPalindrome("A man, a plan, a canal: Panama"); // Returns: true
longestPalindromicSubstring("babad"); // Returns: "bab" or "aba"

Anagram Problems (15 points)

Create a class AnagramProblems.java with:

1. boolean isAnagram(String s1, String s2) - Check if two strings are anagrams
2. List<List<String>> groupAnagrams(String[] strs) - Group anagrams together
3. List<Integer> findAnagramIndices(String s, String p) - Find all start indices of p's anagrams in s

// Example usage:
isAnagram("anagram", "nagaram"); // Returns: true
isAnagram("rat", "car"); // Returns: false

String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
groupAnagrams(strs); 
// Returns: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

findAnagramIndices("cbaebabacd", "abc"); 
// Returns: [0, 6] ("cba" at 0, "bac" at 6)

Pattern Matching (15 points)

Create a class PatternMatching.java with:

1. int naivePatternSearch(String text, String pattern) - Find first occurrence using brute force O(n*m)
2. List<Integer> findAllOccurrences(String text, String pattern) - Find all occurrences of pattern in text
3. int kmpSearch(String text, String pattern) - Implement KMP algorithm for pattern matching
4. int[] computeLPSArray(String pattern) - Helper method to compute LPS (Longest Proper Prefix Suffix) array for KMP

// Example usage:
naivePatternSearch("AABAACAADAABAAABAA", "AABA"); // Returns: 0
findAllOccurrences("AABAACAADAABAAABAA", "AABA"); // Returns: [0, 9, 13]

// KMP is more efficient for repeated searches
kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"); // Returns: 10
computeLPSArray("ABABCABAB"); // Returns: [0, 0, 1, 2, 0, 1, 2, 3, 4]

Character Frequency Problems (15 points)

Create a class CharacterFrequency.java with:

1. char firstNonRepeatingChar(String s) - Find first non-repeating character
2. String removeDuplicates(String s) - Remove duplicate characters keeping first occurrence
3. boolean canFormPalindrome(String s) - Check if characters can be rearranged to form palindrome
4. String frequencySort(String s) - Sort string by character frequency (most frequent first)

// Example usage:
firstNonRepeatingChar("leetcode"); // Returns: 'l'
firstNonRepeatingChar("aabb"); // Returns: '_' or '\0' (none found)

removeDuplicates("abracadabra"); // Returns: "abrcd"

canFormPalindrome("carrace"); // Returns: true ("racecar")
canFormPalindrome("hello"); // Returns: false

frequencySort("tree"); // Returns: "eert" or "eetr"

String Sliding Window (15 points)

Create a class StringSlidingWindow.java with:

1. int lengthOfLongestSubstring(String s) - Length of longest substring without repeating characters
2. String minWindow(String s, String t) - Minimum window in s containing all characters of t
3. int characterReplacement(String s, int k) - Longest substring with same letters after at most k replacements

// Example usage:
lengthOfLongestSubstring("abcabcbb"); // Returns: 3 ("abc")
lengthOfLongestSubstring("bbbbb"); // Returns: 1 ("b")
lengthOfLongestSubstring("pwwkew"); // Returns: 3 ("wke")

minWindow("ADOBECODEBANC", "ABC"); // Returns: "BANC"

characterReplacement("AABABBA", 1); // Returns: 4 ("AABA" or "ABBA")