1️⃣ Find Second Highest Number in a List

javaCopyEditList<Integer> numbers = Arrays.asList(5, 1, 9, 2, 9, 7);
Optional<Integer> secondHighest = numbers.stream()
    .distinct()
    .sorted(Comparator.reverseOrder())
    .skip(1)
    .findFirst();

System.out.println(secondHighest.orElse(null)); // Output: 7

✅ Concepts Used: distinct(), sorted(), skip(), findFirst()

2️⃣ Find First Non-Repeating Character in a String

javaCopyEditString str = "swiss";
Optional<Character> firstNonRepeat = str.chars()
    .mapToObj(c -> (char) c)
    .collect(Collectors.groupingBy(c -> c, LinkedHashMap::new, Collectors.counting()))
    .entrySet().stream()
    .filter(e -> e.getValue() == 1)
    .map(Map.Entry::getKey)
    .findFirst();

System.out.println(firstNonRepeat.orElse(null)); // Output: 'w'

✅ Concepts Used: groupingBy(), LinkedHashMap, filter(), findFirst()

3️⃣ Find Frequency of Each Word in a Sentence

javaCopyEditString sentence = "java is awesome and java is powerful";
Map<String, Long> wordCount = Arrays.stream(sentence.split(" "))
    .collect(Collectors.groupingBy(word -> word, Collectors.counting()));

System.out.println(wordCount); 
// Output: {java=2, is=2, awesome=1, and=1, powerful=1}

✅ Concepts Used: split(), groupingBy(), counting()

4️⃣ Find the Longest Word in a List

javaCopyEditList<String> words = Arrays.asList("apple", "banana", "cherry", "strawberry");
String longestWord = words.stream()
    .max(Comparator.comparingInt(String::length))
    .orElse(null);

System.out.println(longestWord); // Output: "strawberry"

✅ Concepts Used: max(), comparingInt()

5️⃣ Find Duplicate Elements in a List

javaCopyEditList<Integer> numbers = Arrays.asList(1, 2, 3, 2, 4, 5, 1, 6);
Set<Integer> seen = new HashSet<>();
List<Integer> duplicates = numbers.stream()
    .filter(n -> !seen.add(n)) // If already present, it's a duplicate
    .collect(Collectors.toList());

System.out.println(duplicates); // Output: [2, 1]

✅ Concepts Used: filter(), HashSet, collect()

6️⃣ Find Employees With Highest Salary (GroupBy)

javaCopyEditclass Employee {
    String name;
    int salary;
    Employee(String name, int salary) { this.name = name; this.salary = salary; }
    public int getSalary() { return salary; }
}

List<Employee> employees = Arrays.asList(
    new Employee("Alice", 7000),
    new Employee("Bob", 9000),
    new Employee("Charlie", 9000)
);

int maxSalary = employees.stream().mapToInt(Employee::getSalary).max().orElse(0);
List<String> highestPaidEmployees = employees.stream()
    .filter(e -> e.getSalary() == maxSalary)
    .map(e -> e.name)
    .collect(Collectors.toList());

System.out.println(highestPaidEmployees); // Output: [Bob, Charlie]

✅ Concepts Used: mapToInt(), max(), filter(), map()

7️⃣ Find Sum and Average of List Elements (Reduce)

javaCopyEditList<Integer> numbers = Arrays.asList(10, 20, 30, 40);
int sum = numbers.stream().reduce(0, Integer::sum);
double avg = numbers.stream().mapToInt(Integer::intValue).average().orElse(0.0);

System.out.println("Sum: " + sum + ", Average: " + avg);
// Output: Sum: 100, Average: 25.0

✅ Concepts Used: reduce(), mapToInt(), average()

8️⃣ Convert List of Strings to Uppercase

javaCopyEditList<String> words = Arrays.asList("java", "spring", "aws");
List<String> upperCaseWords = words.stream()
    .map(String::toUpperCase)
    .collect(Collectors.toList());

System.out.println(upperCaseWords); // Output: [JAVA, SPRING, AWS]

✅ Concepts Used: map(), collect()

9️⃣ Flatten a List of Lists

javaCopyEditList<List<Integer>> listOfLists = Arrays.asList(
    Arrays.asList(1, 2, 3),
    Arrays.asList(4, 5),
    Arrays.asList(6, 7, 8)
);

List<Integer> flattenedList = listOfLists.stream()
    .flatMap(List::stream)
    .collect(Collectors.toList());

System.out.println(flattenedList); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

✅ Concepts Used: flatMap(), collect()

🔟 Sort a List of Objects by Multiple Fields

javaCopyEditclass Person {
    String name;
    int age;
    Person(String name, int age) { this.name = name; this.age = age; }
}

List<Person> people = Arrays.asList(
    new Person("Alice", 25),
    new Person("Bob", 20),
    new Person("Charlie", 25)
);

List<Person> sortedPeople = people.stream()
    .sorted(Comparator.comparing(Person::getAge).thenComparing(p -> p.name))
    .collect(Collectors.toList());

sortedPeople.forEach(p -> System.out.println(p.name + " - " + p.age));
// Output: Bob - 20, Alice - 25, Charlie - 25

✅ Concepts Used: sorted(), comparing(), thenComparing()

---

Bonus: Find nth Highest Number in a List

javaCopyEditint n = 3;
List<Integer> numbers = Arrays.asList(10, 5, 8, 3, 9, 12);
Optional<Integer> nthHighest = numbers.stream()
    .distinct()
    .sorted(Comparator.reverseOrder())
    .skip(n - 1)
    .findFirst();

System.out.println(nthHighest.orElse(null)); // Output: 9 (3rd highest)

✅ Concepts Used: distinct(), sorted(), skip(), findFirst()

📌 Summary: Key Stream API Concepts Used

1. Filtering & Searching: filter(), findFirst(), findAny()

2. Sorting & Mapping: sorted(), map(), flatMap()

3. Aggregation: reduce(), count(), sum(), average()

4. Grouping & Collecting: groupingBy(), collect(), counting()

5. Parallel Streams for Performance Optimization

---

1️⃣ Parallel Stream: Find Sum of Large Numbers Efficiently

🔹 Use Case: Summing up a large dataset efficiently with parallelStream().

javaCopyEditList<Integer> numbers = IntStream.rangeClosed(1, 1_000_000).boxed().collect(Collectors.toList());

long sum = numbers.parallelStream().mapToInt(Integer::intValue).sum();

System.out.println("Sum: " + sum); // Output: 500000500000

✅ Concepts Used: parallelStream(), mapToInt(), sum()

2️⃣ Group Employees by Department and Find Highest Salary

🔹 Use Case: Finding the highest-paid employee per department.

javaCopyEditclass Employee {
    String name, department;
    int salary;
    Employee(String name, String department, int salary) {
        this.name = name; this.department = department; this.salary = salary;
    }
    public int getSalary() { return salary; }
}

List<Employee> employees = Arrays.asList(
    new Employee("Alice", "IT", 7000),
    new Employee("Bob", "HR", 5000),
    new Employee("Charlie", "IT", 9000),
    new Employee("David", "HR", 6000)
);

Map<String, Optional<Employee>> highestPaid = employees.stream()
    .collect(Collectors.groupingBy(e -> e.department,
        Collectors.maxBy(Comparator.comparingInt(Employee::getSalary))));

highestPaid.forEach((dept, emp) -> 
    System.out.println(dept + " -> " + emp.get().name + " (" + emp.get().salary + ")")
);
// Output: IT -> Charlie (9000), HR -> David (6000)

✅ Concepts Used: groupingBy(), maxBy(), comparingInt()

3️⃣ Compute Running Sum of a List (Cumulative Sum)

🔹 Use Case: Implementing a prefix sum (used in financial calculations).

javaCopyEditList<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);

List<Integer> runningSum = IntStream.range(0, numbers.size())
    .mapToObj(i -> numbers.subList(0, i + 1).stream().mapToInt(Integer::intValue).sum())
    .collect(Collectors.toList());

System.out.println(runningSum); // Output: [1, 3, 6, 10, 15]

✅ Concepts Used: IntStream.range(), subList(), mapToInt(), sum()

4️⃣ Find Most Frequent Word in a List

🔹 Use Case: Finding the most occurring word in logs, tweets, or chat messages.

javaCopyEditList<String> words = Arrays.asList("java", "python", "java", "c", "java", "c", "python");

String mostFrequent = words.stream()
    .collect(Collectors.groupingBy(w -> w, Collectors.counting()))
    .entrySet().stream()
    .max(Map.Entry.comparingByValue())
    .map(Map.Entry::getKey)
    .orElse(null);

System.out.println(mostFrequent); // Output: "java"

✅ Concepts Used: groupingBy(), counting(), max()

5️⃣ Find k Largest Elements (Efficient)

🔹 Use Case: Extracting top K elements without sorting entire list.

javaCopyEditList<Integer> numbers = Arrays.asList(10, 4, 8, 20, 15, 2);
int k = 3;

List<Integer> topK = numbers.stream()
    .sorted(Comparator.reverseOrder())
    .limit(k)
    .collect(Collectors.toList());

System.out.println(topK); // Output: [20, 15, 10]

✅ Concepts Used: sorted(), reverseOrder(), limit()

6️⃣ Flatten & Sort Nested Lists

🔹 Use Case: Flattening a JSON-like structure and sorting.

javaCopyEditList<List<Integer>> nested = Arrays.asList(
    Arrays.asList(3, 5, 1), Arrays.asList(8, 7, 2), Arrays.asList(4, 6)
);

List<Integer> flatSorted = nested.stream()
    .flatMap(List::stream)
    .sorted()
    .collect(Collectors.toList());

System.out.println(flatSorted); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

✅ Concepts Used: flatMap(), sorted()

7️⃣ Find Median of a List Using Streams

🔹 Use Case: Finding the middle value in datasets like salary distribution.

javaCopyEditList<Integer> numbers = Arrays.asList(12, 4, 5, 3, 8, 7);
List<Integer> sorted = numbers.stream().sorted().collect(Collectors.toList());
int size = sorted.size();

double median = size % 2 == 0 ?
    (sorted.get(size / 2 - 1) + sorted.get(size / 2)) / 2.0
    : sorted.get(size / 2);

System.out.println("Median: " + median); // Output: 6.5

✅ Concepts Used: sorted(), get(), size()

8️⃣ Convert List to Map (Handling Duplicates)

🔹 Use Case: Converting a list of objects into a Map, handling duplicate keys.

javaCopyEditList<Employee> employees = Arrays.asList(
    new Employee("Alice", "IT", 7000),
    new Employee("Bob", "HR", 5000),
    new Employee("Charlie", "IT", 9000)
);

Map<String, List<Employee>> departmentMap = employees.stream()
    .collect(Collectors.groupingBy(e -> e.department));

System.out.println(departmentMap); 
// Output: {IT=[Alice, Charlie], HR=[Bob]}

✅ Concepts Used: groupingBy()

9️⃣ Count Words in a Paragraph (Ignore Case & Special Characters)

🔹 Use Case: Used in text analytics, search engines.

javaCopyEditString paragraph = "Java is awesome! Java streams are powerful. Streams help in Java.";

Map<String, Long> wordCount = Arrays.stream(paragraph.toLowerCase().replaceAll("[^a-z ]", "").split(" "))
    .collect(Collectors.groupingBy(word -> word, Collectors.counting()));

System.out.println(wordCount);
// Output: {java=3, is=1, awesome=1, streams=2, are=1, powerful=1, help=1, in=1}

✅ Concepts Used: replaceAll(), split(), groupingBy(), counting()

🔟 Filter Top N% Salary Employees

🔹 Use Case: Used in HR analytics, salary benchmarking.

javaCopyEditList<Employee> employees = Arrays.asList(
    new Employee("Alice", "IT", 7000),
    new Employee("Bob", "HR", 5000),
    new Employee("Charlie", "IT", 9000),
    new Employee("David", "Finance", 10000)
);

int topPercent = 50;
List<Employee> topEmployees = employees.stream()
    .sorted(Comparator.comparingInt(Employee::getSalary).reversed())
    .limit((employees.size() * topPercent) / 100)
    .collect(Collectors.toList());

topEmployees.forEach(e -> System.out.println(e.name + " - " + e.salary));
// Output: David - 10000, Charlie - 9000

✅ Concepts Used: sorted(), limit(), comparingInt()

some real-world and advanced Stream API coding problems often asked in Interview

1️⃣ Find Second Highest Salary

🔹 Use Case: Common SQL-based problem in hiring platforms.

javaCopyEditList<Integer> salaries = Arrays.asList(4000, 5000, 3000, 7000, 5000);

Optional<Integer> secondHighest = salaries.stream()
    .distinct()
    .sorted(Comparator.reverseOrder())
    .skip(1)
    .findFirst();

System.out.println(secondHighest.orElse(-1)); // Output: 5000

✅ Concepts Used: distinct(), sorted(), skip(), findFirst()

2️⃣ Find Employees with Highest Salary in Each Department

🔹 Use Case: Grouping data and finding max values efficiently.

javaCopyEditrecord Employee(String name, String department, int salary) {}

List<Employee> employees = Arrays.asList(
    new Employee("Alice", "IT", 7000),
    new Employee("Bob", "HR", 5000),
    new Employee("Charlie", "IT", 9000),
    new Employee("David", "HR", 6000)
);

Map<String, Employee> topEmployees = employees.stream()
    .collect(Collectors.toMap(
        Employee::department,
        e -> e,
        (e1, e2) -> e1.salary() > e2.salary() ? e1 : e2
    ));

topEmployees.forEach((dept, emp) -> 
    System.out.println(dept + " -> " + emp.name() + " (" + emp.salary() + ")")
);
// Output: IT -> Charlie (9000), HR -> David (6000)

✅ Concepts Used: toMap(), groupingBy(), max()

3️⃣ Find Most Frequent Character in a String

🔹 Use Case: Used in spell checkers, analytics, chat applications.

javaCopyEditString str = "streamstream";

char mostFrequent = str.chars()
    .mapToObj(c -> (char) c)
    .collect(Collectors.groupingBy(c -> c, Collectors.counting()))
    .entrySet().stream()
    .max(Map.Entry.comparingByValue())
    .map(Map.Entry::getKey)
    .orElse(null);

System.out.println(mostFrequent); // Output: 't'

✅ Concepts Used: chars(), mapToObj(), groupingBy(), max()

4️⃣ Find Common Elements in Two Lists

🔹 Use Case: Used in recommendation engines, social networks.

javaCopyEditList<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> list2 = Arrays.asList(3, 4, 5, 6, 7);

List<Integer> commonElements = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

System.out.println(commonElements); // Output: [3, 4, 5]

✅ Concepts Used: filter(), contains()

5️⃣ Convert a List to a Map (Handling Duplicates)

🔹 Use Case: Converting API responses into a structured Map.

javaCopyEditList<Employee> employees = Arrays.asList(
    new Employee("Alice", "IT", 7000),
    new Employee("Bob", "HR", 5000),
    new Employee("Charlie", "IT", 9000)
);

Map<String, List<Employee>> departmentMap = employees.stream()
    .collect(Collectors.groupingBy(Employee::department));

System.out.println(departmentMap);

✅ Concepts Used: groupingBy()

6️⃣ Find Median in a List

🔹 Use Case: Used in data analytics, salary benchmarking.

javaCopyEditList<Integer> numbers = Arrays.asList(12, 4, 5, 3, 8, 7);
List<Integer> sorted = numbers.stream().sorted().collect(Collectors.toList());
int size = sorted.size();

double median = size % 2 == 0 ?
    (sorted.get(size / 2 - 1) + sorted.get(size / 2)) / 2.0
    : sorted.get(size / 2);

System.out.println("Median: " + median); // Output: 6.5

✅ Concepts Used: sorted(), get(), size()

7️⃣ Find kth Largest Element

🔹 Use Case: Used in real-time ranking, leaderboards.

javaCopyEditList<Integer> numbers = Arrays.asList(10, 4, 8, 20, 15, 2);
int k = 3;

List<Integer> topK = numbers.stream()
    .sorted(Comparator.reverseOrder())
    .limit(k)
    .collect(Collectors.toList());

System.out.println(topK); // Output: [20, 15, 10]

✅ Concepts Used: sorted(), reverseOrder(), limit()

8️⃣ Count Word Frequency in a Sentence

🔹 Use Case: Used in search engines, NLP, analytics.

javaCopyEditString text = "Java is great and Java streams are powerful";

Map<String, Long> wordCount = Arrays.stream(text.toLowerCase().split(" "))
    .collect(Collectors.groupingBy(w -> w, Collectors.counting()));

System.out.println(wordCount);
// Output: {java=2, is=1, great=1, and=1, streams=1, are=1, powerful=1}

✅ Concepts Used: split(), groupingBy(), counting()

9️⃣ Find Duplicate Elements in a List

🔹 Use Case: Used in data validation, fraud detection.

javaCopyEditList<Integer> numbers = Arrays.asList(1, 2, 3, 4, 2, 5, 1, 6, 3);

Set<Integer> seen = new HashSet<>();
Set<Integer> duplicates = numbers.stream()
    .filter(n -> !seen.add(n))
    .collect(Collectors.toSet());

System.out.println(duplicates); // Output: [1, 2, 3]

✅ Concepts Used: filter(), Set

🔟 Find Longest Word in a Sentence

🔹 Use Case: Used in spell checkers, language processing.

javaCopyEditString sentence = "Streams in Java are very powerful";

String longestWord = Arrays.stream(sentence.split(" "))
    .max(Comparator.comparingInt(String::length))
    .orElse("");

System.out.println(longestWord); // Output: "powerful"

✅ Concepts Used: split(), max(), comparingInt()

Hard problems

1️⃣ Find the Longest Consecutive Sequence in an Unsorted List

🔹 Use Case: Used in leaderboards, activity streaks.

javaCopyEditList<Integer> nums = Arrays.asList(100, 4, 200, 1, 3, 2);

int longestStreak = nums.stream()
    .collect(Collectors.toSet()) // Convert to Set for O(1) lookup
    .stream()
    .filter(n -> !nums.contains(n - 1)) // Start from the smallest in a sequence
    .mapToInt(n -> {
        int count = 1;
        while (nums.contains(n + count)) count++;
        return count;
    })
    .max()
    .orElse(0);

System.out.println(longestStreak); // Output: 4 (Sequence: 1, 2, 3, 4)

✅ Concepts Used: Set, filter(), mapToInt(), max()

2️⃣ Find Top K Frequent Words in a List

🔹 Use Case: Used in search engines, text analytics.

javaCopyEditList<String> words = Arrays.asList("apple", "banana", "apple", "orange", "banana", "apple");
int k = 2;

List<String> topKWords = words.stream()
    .collect(Collectors.groupingBy(w -> w, Collectors.counting()))
    .entrySet().stream()
    .sorted(Map.Entry.<String, Long>comparingByValue().reversed())
    .limit(k)
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

System.out.println(topKWords); // Output: [apple, banana]

✅ Concepts Used: groupingBy(), counting(), sorted(), limit()

3️⃣ Find All Anagrams in a List

🔹 Use Case: Used in autocomplete systems, text matching.

javaCopyEditList<String> words = Arrays.asList("listen", "silent", "enlist", "rat", "tar", "art", "java");

Map<String, List<String>> anagrams = words.stream()
    .collect(Collectors.groupingBy(w -> w.chars().sorted()
        .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
        .toString()));

System.out.println(anagrams);
// Output: {aeilst=[listen, silent, enlist], art=[rat, tar, art], aajv=[java]}

✅ Concepts Used: groupingBy(), chars(), sorted(), collect()

4️⃣ Find All Pairs That Sum to a Target

🔹 Use Case: Used in financial transactions, fraud detection.

javaCopyEditList<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);
int target = 7;

List<List<Integer>> pairs = numbers.stream()
    .flatMap(a -> numbers.stream().filter(b -> a < b && a + b == target).map(b -> List.of(a, b)))
    .collect(Collectors.toList());

System.out.println(pairs); // Output: [[1, 6], [2, 5], [3, 4]]

✅ Concepts Used: flatMap(), filter(), map()

5️⃣ Parallel Processing for Large Data Sets

🔹 Use Case: Used in big data, high-performance computing.

javaCopyEditList<Integer> largeNumbers = IntStream.range(1, 1_000_000).boxed().collect(Collectors.toList());

long sum = largeNumbers.parallelStream()
    .mapToLong(Integer::longValue)
    .sum();

System.out.println("Sum: " + sum); // Output: 499999500000

✅ Concepts Used: parallelStream(), mapToLong(), sum()

6️⃣ Find the Most Repeated Character in a String

🔹 Use Case: Used in data compression, NLP.

javaCopyEditString str = "javastream";

char mostFrequent = str.chars()
    .mapToObj(c -> (char) c)
    .collect(Collectors.groupingBy(c -> c, Collectors.counting()))
    .entrySet().stream()
    .max(Map.Entry.comparingByValue())
    .map(Map.Entry::getKey)
    .orElse('\0');

System.out.println(mostFrequent); // Output: 'a'

✅ Concepts Used: chars(), mapToObj(), groupingBy(), max()

7️⃣ Find k Largest Numbers in an Efficient Way

🔹 Use Case: Used in leaderboards, real-time ranking.

javaCopyEditList<Integer> numbers = Arrays.asList(10, 4, 8, 20, 15, 2);
int k = 3;

List<Integer> topK = numbers.stream()
    .sorted(Comparator.reverseOrder())
    .limit(k)
    .collect(Collectors.toList());

System.out.println(topK); // Output: [20, 15, 10]

✅ Concepts Used: sorted(), reverseOrder(), limit()

8️⃣ Remove Duplicates Without Using Set

🔹 Use Case: Used in data cleaning, analytics.

javaCopyEditList<Integer> numbers = Arrays.asList(1, 2, 2, 3, 4, 4, 5);

List<Integer> uniqueNumbers = numbers.stream()
    .distinct()
    .collect(Collectors.toList());

System.out.println(uniqueNumbers); // Output: [1, 2, 3, 4, 5]

✅ Concepts Used: distinct()

9️⃣ Merge Multiple Lists into One Sorted List

🔹 Use Case: Used in data aggregation, distributed computing.

javaCopyEditList<Integer> list1 = Arrays.asList(1, 3, 5);
List<Integer> list2 = Arrays.asList(2, 4, 6);

List<Integer> mergedSorted = Stream.concat(list1.stream(), list2.stream())
    .sorted()
    .collect(Collectors.toList());

System.out.println(mergedSorted); // Output: [1, 2, 3, 4, 5, 6]

✅ Concepts Used: concat(), sorted()

🔟 Find First Non-Repeating Character in a String

🔹 Use Case: Used in natural language processing, error detection.

javaCopyEditString str = "swiss";

char firstNonRepeating = str.chars()
    .mapToObj(c -> (char) c)
    .collect(Collectors.groupingBy(c -> c, LinkedHashMap::new, Collectors.counting()))
    .entrySet().stream()
    .filter(e -> e.getValue() == 1)
    .map(Map.Entry::getKey)
    .findFirst()
    .orElse('\0');

System.out.println(firstNonRepeating); // Output: 'w'

✅ Concepts Used: groupingBy(), LinkedHashMap, filter(), findFirst()

DP:

1️⃣ Fibonacci Series Using Streams (Recursive + DP)

🔹 Use Case: Used in mathematical computations, financial modeling.

javaCopyEditimport java.util.stream.IntStream;

public class FibonacciStream {
    public static int fibonacci(int n) {
        return IntStream.rangeClosed(0, n)
            .reduce((a, b) -> b < 2 ? b : a + fibonacci(b - 1) + fibonacci(b - 2))
            .orElse(0);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10)); // Output: 55
    }
}

✅ Concepts Used: IntStream.rangeClosed(), reduce(), recursion

🔴 Issue: This has exponential time complexity (O(2ⁿ)). Let's optimize it with Memoization + Streams 👇

2️⃣ Optimized Fibonacci Using Memoization + Streams (DP)

🔹 Use Case: Used in large-scale computations, AI, and simulations.

javaCopyEditimport java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.IntStream;

public class FibonacciDP {
    private static final Map<Integer, Integer> memo = new ConcurrentHashMap<>();

    public static int fibonacci(int n) {
        return memo.computeIfAbsent(n, k -> (k < 2) ? k : fibonacci(k - 1) + fibonacci(k - 2));
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(50)); // Output: 12586269025 (Fast!)
    }
}

✅ Concepts Used: ConcurrentHashMap, computeIfAbsent(), Memoization

🟢 Optimized Complexity: O(n) instead of O(2ⁿ)

3️⃣ Find nth Ugly Number Using DP + Streams

🔹 Use Case: Used in number theory, AI computations.

javaCopyEditimport java.util.HashSet;
import java.util.PriorityQueue;
import java.util.stream.IntStream;

public class UglyNumber {
    public static int nthUglyNumber(int n) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        HashSet<Long> seen = new HashSet<>();
        pq.add(1L);
        seen.add(1L);

        return IntStream.rangeClosed(1, n)
            .mapToObj(i -> pq.poll())
            .peek(num -> {
                for (int factor : new int[]{2, 3, 5}) {
                    long next = num * factor;
                    if (seen.add(next)) pq.add(next);
                }
            })
            .reduce((first, second) -> second)
            .orElse(1)
            .intValue();
    }

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10)); // Output: 12
    }
}

✅ Concepts Used: PriorityQueue, HashSet, reduce()

🟢 Time Complexity: O(n log n)

4️⃣ Longest Increasing Subsequence (LIS) Using DP + Streams

🔹 Use Case: Used in stock market analysis, AI predictions.

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        IntStream.range(0, nums.length).forEach(i -> 
            IntStream.range(0, i).filter(j -> nums[j] < nums[i])
                .forEach(j -> dp[i] = Math.max(dp[i], dp[j] + 1))
        );

        return Arrays.stream(dp).max().orElse(1);
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums)); // Output: 4 (2,3,7,101)
    }
}

✅ Concepts Used: range(), filter(), max(), Bottom-Up DP

🟢 Time Complexity: O(n²)

5️⃣ Coin Change Problem Using DP + Streams

🔹 Use Case: Used in finance, transaction processing.

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        IntStream.rangeClosed(1, amount).forEach(i ->
            Arrays.stream(coins).filter(coin -> coin <= i)
                .forEach(coin -> dp[i] = Math.min(dp[i], dp[i - coin] + 1))
        );

        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount)); // Output: 3 (5+5+1)
    }
}

✅ Concepts Used: rangeClosed(), filter(), min(), Bottom-Up DP

🟢 Time Complexity: O(n * amount)

---

6️⃣ Edit Distance (Levenshtein Distance)

🔹 Use Case: Spell checkers, DNA sequence alignment
🔹 Problem: Find the minimum operations (insert, delete, replace) to convert word1 into word2.
🔹 Time Complexity: O(M * N), where M = word1.length(), N = word2.length()
🔹 Space Complexity: O(M * N), due to DP table

javaCopyEditimport java.util.stream.IntStream;

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        IntStream.rangeClosed(0, m).forEach(i -> dp[i][0] = i);
        IntStream.rangeClosed(0, n).forEach(j -> dp[0][j] = j);

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j -> 
                dp[i][j] = (word1.charAt(i - 1) == word2.charAt(j - 1)) ? 
                           dp[i - 1][j - 1] : 
                           1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]))
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // Output: 3
    }
}

✅ Concepts Used: 2D DP, Stream.range(), Min()

---

Advanced Dynamic Programming (DP) problems using Java Streams

1️⃣ Parallel Fibonacci (Multi-threaded Stream)

🔹 Use Case: Used in parallel computing, financial modeling.

javaCopyEditimport java.util.stream.IntStream;

public class ParallelFibonacci {
    public static int fibonacci(int n) {
        return IntStream.rangeClosed(0, n)
            .parallel()
            .reduce((a, b) -> b < 2 ? b : a + fibonacci(b - 1) + fibonacci(b - 2))
            .orElse(0);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10)); // Output: 55
    }
}

✅ Concepts Used: parallelStream(), reduce(), recursion

2️⃣ Traveling Salesman Problem (TSP) Using Bitmask DP

🔹 Use Case: Used in route optimization, logistics, delivery services.

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class TSP {
    private static final int INF = 1_000_000;
    private static int[][] dp;
    private static int[][] dist;

    public static int tsp(int mask, int pos, int n) {
        if (mask == (1 << n) - 1) return dist[pos][0]; // Return to start
        if (dp[mask][pos] != -1) return dp[mask][pos];

        return dp[mask][pos] = IntStream.range(0, n)
            .filter(city -> (mask & (1 << city)) == 0) // City not visited
            .map(city -> dist[pos][city] + tsp(mask | (1 << city), city, n))
            .min()
            .orElse(INF);
    }

    public static void main(String[] args) {
        int n = 4;
        dist = new int[][]{
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };
        dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, -1);

        System.out.println(tsp(1, 0, n)); // Output: 80
    }
}

✅ Concepts Used: Bitmask DP, min(), filter(), map(), reduce()

3️⃣ Count Ways to Reach the Nth Stair Using DP + Streams

🔹 Use Case: Used in game development, AI pathfinding.

javaCopyEditimport java.util.stream.IntStream;

public class Staircase {
    public static int countWays(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

        IntStream.rangeClosed(2, n)
            .forEach(i -> dp[i] = dp[i - 1] + dp[i - 2]);

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(countWays(5)); // Output: 8
    }
}

✅ Concepts Used: rangeClosed(), forEach(), Bottom-Up DP

4️⃣ Subset Sum Problem Using DP + Streams

🔹 Use Case: Used in financial calculations, cryptography.

javaCopyEditimport java.util.stream.IntStream;

public class SubsetSum {
    public static boolean isSubsetSum(int[] nums, int sum) {
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int num : nums) {
            IntStream.iterate(sum, i -> i >= num, i -> i - 1)
                .forEach(i -> dp[i] |= dp[i - num]);
        }

        return dp[sum];
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int sum = 9;
        System.out.println(isSubsetSum(nums, sum)); // Output: true
    }
}

✅ Concepts Used: iterate(), forEach(), Bottom-Up DP

5️⃣ Longest Common Subsequence (LCS) Using Streams

🔹 Use Case: Used in DNA sequencing, NLP, plagiarism detection.

javaCopyEditimport java.util.stream.IntStream;

public class LCS {
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j ->
                dp[i][j] = (text1.charAt(i - 1) == text2.charAt(j - 1)) ?
                    dp[i - 1][j - 1] + 1 :
                    Math.max(dp[i - 1][j], dp[i][j - 1])
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // Output: 3
    }
}

✅ Concepts Used: rangeClosed(), forEach(), charAt(), Bottom-Up DP

6️⃣ Maximum Subarray Sum (Kadane’s Algorithm Using Streams)

🔹 Use Case: Used in stock market predictions, signal processing.

javaCopyEditimport java.util.stream.IntStream;

public class MaxSubarray {
    public static int maxSubArray(int[] nums) {
        int[] maxSum = new int[]{nums[0]};
        IntStream.range(1, nums.length).forEach(i ->
            maxSum[0] = Math.max(nums[i], nums[i] + maxSum[0])
        );
        return maxSum[0];
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums)); // Output: 6 (Subarray: [4, -1, 2, 1])
    }
}

✅ Concepts Used: range(), forEach(), Kadane’s Algorithm

7️⃣ Parallel Knapsack Problem Using Streams

🔹 Use Case: Used in resource allocation, financial portfolio selection.

javaCopyEditimport java.util.stream.IntStream;

public class Knapsack {
    public static int knapsack(int W, int[] wt, int[] val) {
        int n = wt.length;
        int[][] dp = new int[n + 1][W + 1];

        IntStream.rangeClosed(1, n).parallel().forEach(i ->
            IntStream.rangeClosed(1, W).parallel().forEach(w ->
                dp[i][w] = (wt[i - 1] <= w) ?
                    Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]) :
                    dp[i - 1][w]
            )
        );

        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] wt = {2, 3, 4, 5}, val = {3, 4, 5, 6};
        int W = 5;
        System.out.println(knapsack(W, wt, val)); // Output: 7
    }
}

✅ Concepts Used: parallelStream(), max(), Parallel DP

8️⃣ Longest Increasing Subsequence (LIS) Using Streams

🔹 Use Case: Used in stock price prediction, AI, competitive programming

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class LIS {
    public static int longestIncreasingSubsequence(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        IntStream.range(1, nums.length).forEach(i ->
            IntStream.range(0, i).forEach(j -> {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            })
        );

        return Arrays.stream(dp).max().orElse(1);
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(longestIncreasingSubsequence(nums)); // Output: 4 (LIS: [2, 3, 7, 101])
    }
}

✅ Concepts Used: max(), range(), Bottom-Up DP

9️⃣ Word Break Problem Using Streams

🔹 Use Case: Used in Natural Language Processing (NLP), chatbots

javaCopyEditimport java.util.*;
import java.util.stream.IntStream;

public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        IntStream.range(1, s.length() + 1).forEach(i ->
            IntStream.range(0, i).forEach(j -> {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            })
        );

        return dp[s.length()];
    }

    public static void main(String[] args) {
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak("leetcode", wordDict)); // Output: true
    }
}

✅ Concepts Used: contains(), substring(), String DP

🔟 Matrix Chain Multiplication Using Streams

🔹 Use Case: Used in computational geometry, optimizing query execution

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class MatrixChainMultiplication {
    public static int matrixChainOrder(int[] p) {
        int n = p.length;
        int[][] dp = new int[n][n];

        IntStream.range(1, n).forEach(len ->
            IntStream.range(1, n - len).forEach(i -> {
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                IntStream.range(i, j).forEach(k ->
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j])
                );
            })
        );

        return dp[1][n - 1];
    }

    public static void main(String[] args) {
        int[] matrices = {1, 2, 3, 4};
        System.out.println(matrixChainOrder(matrices)); // Output: 18
    }
}

✅ Concepts Used: min(), range(), DP on Intervals

---

1️⃣1️⃣ Coin Change Problem Using Streams

🔹 Use Case: Used in cryptocurrency, vending machines, transaction handling

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        IntStream.rangeClosed(1, amount).forEach(i ->
            Arrays.stream(coins).forEach(coin -> {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            })
        );

        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        System.out.println(minCoins(coins, 11)); // Output: 3 (5 + 5 + 1)
    }
}

✅ Concepts Used: min(), stream(), Unbounded Knapsack DP

1️⃣2️⃣ Edit Distance (Levenshtein Distance) Using Streams

🔹 Use Case: Used in spell-checking, DNA sequence alignment, NLP

javaCopyEditimport java.util.stream.IntStream;

public class EditDistance {
    public static int minEditDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        IntStream.rangeClosed(0, m).forEach(i -> dp[i][0] = i);
        IntStream.rangeClosed(0, n).forEach(j -> dp[0][j] = j);

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j -> 
                dp[i][j] = (s1.charAt(i - 1) == s2.charAt(j - 1)) ?
                    dp[i - 1][j - 1] :
                    1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]))
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minEditDistance("horse", "ros")); // Output: 3
    }
}

✅ Concepts Used: min(), charAt(), String DP

---

1️⃣3️⃣ Parallel Floyd-Warshall Algorithm Using Streams

🔹 Use Case: Used in shortest path calculations in maps, network routing

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class FloydWarshall {
    private static final int INF = 99999;

    public static void floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = Arrays.stream(graph).map(int[]::clone).toArray(int[][]::new);

        IntStream.range(0, n).parallel().forEach(k ->
            IntStream.range(0, n).parallel().forEach(i ->
                IntStream.range(0, n).parallel().forEach(j ->
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])
                )
            )
        );

        printSolution(dist);
    }

    private static void printSolution(int[][] dist) {
        for (int[] row : dist) {
            System.out.println(Arrays.toString(row));
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 3, INF, INF},
            {2, 0, INF, INF},
            {INF, 7, 0, 1},
            {6, INF, INF, 0}
        };
        floydWarshall(graph);
    }
}

✅ Concepts Used: parallelStream(), min(), Graph DP

1️⃣4️⃣ Partition Equal Subset Sum (Subset Sum DP)

🔹 Use Case: Used in load balancing, scheduling problems, financial portfolio splitting

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class PartitionSubsetSum {
    public static boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        Arrays.stream(nums).forEach(num ->
            IntStream.iterate(target, i -> i >= num, i -> i - 1).forEach(i -> 
                dp[i] = dp[i] || dp[i - num]
            )
        );

        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums)); // Output: true
    }
}

✅ Concepts Used: sum(), iterate(), Subset Sum DP

1️⃣5️⃣ Longest Palindromic Subsequence

🔹 Use Case: Used in bioinformatics (DNA sequencing), NLP (text similarity)

javaCopyEditimport java.util.stream.IntStream;

public class LongestPalindromeSubseq {
    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        IntStream.range(0, n).forEach(i -> dp[i][i] = 1);

        IntStream.range(1, n).forEach(len ->
            IntStream.range(0, n - len).forEach(i -> {
                int j = i + len;
                dp[i][j] = (s.charAt(i) == s.charAt(j)) ?
                    dp[i + 1][j - 1] + 2 :
                    Math.max(dp[i + 1][j], dp[i][j - 1]);
            })
        );

        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(longest
eSubseq("bbbab")); // Output: 4 (bbbb)
    }
}

✅ Concepts Used: charAt(), max(), 2D DP

1️⃣6️⃣ Count Distinct Subsequences

🔹 Use Case: Used in genome analysis, database compression, cryptography

javaCopyEditimport java.util.*;
import java.util.stream.IntStream;

public class CountDistinctSubsequences {
    public static int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];

        IntStream.rangeClosed(0, m).forEach(i -> dp[i][0] = 1);

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j -> 
                dp[i][j] = dp[i - 1][j] + 
                           (s.charAt(i - 1) == t.charAt(j - 1) ? dp[i - 1][j - 1] : 0)
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(numDistinct("rabbbit", "rabbit")); // Output: 3
    }
}

✅ Concepts Used: charAt(), 2D DP, Subsequence Count DP

1️⃣7️⃣ Minimum Path Sum in Grid

🔹 Use Case: Used in robotic navigation, game AI pathfinding, logistics

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class MinPathSum {
    public static int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        IntStream.range(1, m).forEach(i -> dp[i][0] = dp[i - 1][0] + grid[i][0]);
        IntStream.range(1, n).forEach(j -> dp[0][j] = dp[0][j - 1] + grid[0][j]);

        IntStream.range(1, m).forEach(i ->
            IntStream.range(1, n).forEach(j -> 
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
            )
        );

        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(minPathSum(grid)); // Output: 7
    }
}

✅ Concepts Used: min(), 2D DP, Grid-Based DP

1️⃣8️⃣ Paint House Problem

🔹 Use Case: Used in budget allocation, AI decision making, manufacturing

javaCopyEditimport java.util.stream.IntStream;

public class PaintHouse {
    public static int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n][3];

        IntStream.range(0, 3).forEach(i -> dp[0][i] = costs[0][i]);

        IntStream.range(1, n).forEach(i ->
            IntStream.range(0, 3).forEach(j ->
                dp[i][j] = costs[i][j] + Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3])
            )
        );

        return IntStream.of(dp[n - 1]).min().orElse(0);
    }

    public static void main(String[] args) {
        int[][] costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
        System.out.println(minCost(costs)); // Output: 10
    }
}

✅ Concepts Used: min(), modulo arithmetic, Decision-Based DP

1️⃣9️⃣ Wildcard Pattern Matching

🔹 Use Case: Used in text search, regex engines, firewall rules

javaCopyEditimport java.util.stream.IntStream;

public class WildcardMatching {
    public static boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        IntStream.rangeClosed(1, n).forEach(j -> {
            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
        });

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j -> 
                dp[i][j] = (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') ? 
                           dp[i - 1][j - 1] : 
                           (p.charAt(j - 1) == '*' && (dp[i - 1][j] || dp[i][j - 1]))
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(isMatch("adceb", "*a*b")); // Output: true
    }
}

✅ Concepts Used: charAt(), boolean DP, Pattern Matching DP

2️⃣0️⃣ Word Break II (Backtracking + Memoization)

🔹 Use Case: NLP, spell checking, sentence segmentation
🔹 Problem: Given a string s and a dictionary wordDict, return all possible sentences formed by breaking s into words from wordDict.
🔹 Time Complexity: O(N * 2^N), exponential because of recursion
🔹 Space Complexity: O(N^2), due to memoization and substring storage

javaCopyEditimport java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class WordBreakII {
    static Map<String, List<String>> memo = new HashMap<>();

    public static List<String> wordBreak(String s, List<String> wordDict) {
        if (memo.containsKey(s)) return memo.get(s);
        List<String> result = new ArrayList<>();

        if (wordDict.contains(s)) result.add(s);

        IntStream.range(1, s.length()).forEach(i -> {
            String left = s.substring(0, i);
            if (wordDict.contains(left)) {
                List<String> subList = wordBreak(s.substring(i), wordDict);
                result.addAll(subList.stream().map(str -> left + " " + str).collect(Collectors.toList()));
            }
        });

        memo.put(s, result);
        return result;
    }

    public static void main(String[] args) {
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
        System.out.println(wordBreak("catsanddog", wordDict)); 
        // Output: ["cats and dog", "cat sand dog"]
    }
}

✅ Concepts Used: Substring, Stream Collectors, Memoization

Maximum Rectangle in Binary Matrix (Largest 1’s Area)

🔹 Use Case: Image processing, computer vision
🔹 Problem: Given a binary matrix, find the largest rectangle of 1s.
🔹 Time Complexity: O(M * N), using a histogram-based approach
🔹 Space Complexity: O(N), because we use only one row's histogram

javaCopyEditimport java.util.Arrays;
import java.util.Stack;
import java.util.stream.IntStream;

public class MaxRectangle {
    public static int maxArea(int[][] matrix) {
        if (matrix.length == 0) return 0;
        int maxArea = 0, n = matrix[0].length;
        int[] height = new int[n];

        for (int[] row : matrix) {
            IntStream.range(0, n).forEach(j -> height[j] = row[j] == 0 ? 0 : height[j] + 1);
            maxArea = Math.max(maxArea, largestHistogram(height));
        }
        return maxArea;
    }

    private static int largestHistogram(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, n = heights.length;

        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 0, 1, 0, 0}, {1, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0}};
        System.out.println(maxArea(matrix)); // Output: 6
    }
}

✅ Concepts Used: Histogram + Stack, Max(), Stream.range()

Russian Doll Envelopes (Nested Sequences)

🔹 Use Case: Scheduling, packing problems
🔹 Problem: Find the longest chain of envelopes that can fit inside each other.
🔹 Time Complexity: O(N log N), sorting + LIS
🔹 Space Complexity: O(N), storing LIS sequence

javaCopyEditimport java.util.Arrays;
import java.util.stream.IntStream;

public class RussianDoll {
    public static int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] dp = new int[envelopes.length];
        int len = 0;

        for (int[] env : envelopes) {
            int index = Arrays.binarySearch(dp, 0, len, env[1]);
            if (index < 0) index = -(index + 1);
            dp[index] = env[1];
            if (index == len) len++;
        }

        return len;
    }

    public static void main(String[] args) {
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
        System.out.println(maxEnvelopes(envelopes)); // Output: 3
    }
}

✅ Concepts Used: Binary Search, Sorting, LIS with DP

Count of Palindromic Subsequences

🔹 Use Case: DNA sequence analysis, text processing
🔹 Problem: Given a string s, return the number of distinct palindromic subsequences.
🔹 Time Complexity: O(N^2), due to DP table
🔹 Space Complexity: O(N^2), for storing DP results

javaCopyEditimport java.util.stream.IntStream;

public class CountPalindromicSubseq {
    public static int countPalindromicSubsequences(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        IntStream.range(0, n).forEach(i -> dp[i][i] = 1);

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];

                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] += dp[i + 1][j - 1] + 1;
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(countPalindromicSubsequences("abcb")); // Output: 6
    }
}

✅ Concepts Used: 2D DP, String Processing, Functional Loops

Partition Array for Maximum Sum

🔹 Use Case: Image segmentation, financial planning
🔹 Problem: Given an array arr[] and k, partition it into subarrays of length ≤ k to maximize sum.
🔹 Time Complexity: O(N*K), iterating N elements with K choices
🔹 Space Complexity: O(N), for DP table

javaCopyEditimport java.util.stream.IntStream;

public class PartitionArrayMaxSum {
    public static int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];

        IntStream.rangeClosed(1, n).forEach(i -> {
            int max = 0;
            for (int j = 1; j <= k && i - j >= 0; j++) {
                max = Math.max(max, arr[i - j]);
                dp[i] = Math.max(dp[i], dp[i - j] + max * j);
            }
        });

        return dp[n];
    }

    public static void main(String[] args) {
        int[] arr = {1, 15, 7, 9, 2, 5, 10};
        System.out.println(maxSumAfterPartitioning(arr, 3)); // Output: 84
    }
}

✅ Concepts Used: 1D DP, Sliding Window, Streams

Minimum ASCII Delete Sum for Two Strings

🔹 Use Case: Text comparison, NLP
🔹 Problem: Find minimum ASCII sum of characters to delete to make s1 and s2 equal.
🔹 Time Complexity: O(M*N), filling DP table
🔹 Space Complexity: O(M*N), storing DP results

javaCopyEditimport java.util.stream.IntStream;

public class MinAsciiDeleteSum {
    public static int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        IntStream.rangeClosed(1, m).forEach(i -> dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1));
        IntStream.rangeClosed(1, n).forEach(j -> dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1));

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j -> 
                dp[i][j] = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 
                           dp[i - 1][j - 1] : 
                           Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1))
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minimumDeleteSum("sea", "eat")); // Output: 231
    }
}

✅ Concepts Used: 2D DP, Min(), ASCII Processing

Paint Fence Problem

🔹 Use Case: Combinatorics, construction scheduling
🔹 Problem: n fences, k colors, find number of ways to paint them so that no more than 2 adjacent fences have the same color.
🔹 Time Complexity: O(N), using simple DP
🔹 Space Complexity: O(1), since only two variables are used

javaCopyEditimport java.util.stream.IntStream;

public class PaintFence {
    public static int numWays(int n, int k) {
        if (n == 1) return k;
        int same = k, diff = k * (k - 1);

        IntStream.range(2, n).forEach(i -> {
            int temp = diff;
            diff = (same + diff) * (k - 1);
            same = temp;
        });

        return same + diff;
    }

    public static void main(String[] args) {
        System.out.println(numWays(3, 2)); // Output: 6
    }
}

✅ Concepts Used: DP Optimization, Combinatorics, Streams

Interleaving String

🔹 Use Case: Merging two sequences while maintaining order
🔹 Problem: Given three strings s1, s2, and s3, check if s3 is an interleaving of s1 and s2.
🔹 Time Complexity: O(M*N), due to DP table
🔹 Space Complexity: O(M*N), storing DP states

javaCopyEditimport java.util.stream.IntStream;

public class InterleavingString {
    public static boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        IntStream.rangeClosed(1, m).forEach(i -> dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1));
        IntStream.rangeClosed(1, n).forEach(j -> dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1));

        IntStream.rangeClosed(1, m).forEach(i ->
            IntStream.rangeClosed(1, n).forEach(j -> 
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                           (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1))
            )
        );

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("abc", "def", "adbcef")); // Output: true
    }
}

✅ Concepts Used: 2D DP, Boolean Logic, Streams