My Notes some of this and some of that

Kadane's Algo

Problem Statement: This is one of my favorite algorithms! Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.

Reference URL: Kadane’s Algo

Example:

Input: 1 2 3 Output: 6

Input: -1 -2 -3 -4 Output: -1

import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0
//Description: Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.
public class Kadane {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(maxSum(arr));
        }
    }

    public static int maxSum(int[] arr) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            //keep track of maximum sum
            maxSum = Math.max(sum, maxSum);

            //if sum is negative then reset sum
            //this ensures that we consider any sub-array which yield positive sum
            if (sum < 0) {
                sum = 0;
            }
        }

        return maxSum;
    }
}

Minimum Window Substring

Problem Statement: Given a string S and text t. Output the smallest window in the string having all characters of the text. Both the string and text contains small case letters.

Reference URL: Minimum Window Substring

Example:

Input: String: “timetopractice”, Pattern: “toc” Output: “toprac”

Input: String: “zoomlazapzo”, Pattern: “oza” Output: “apzo”

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

//URL: https://practice.geeksforgeeks.org/problems/smallest-window-in-a-string-containing-all-the-characters-of-another-string/0
//Description: Given a string S and text t. Output the smallest window in the string having all characters of the text. Both the string and text contains small case letters.
public class SmallestWindow {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            String str = scanner.next();
            String text = scanner.next();
            System.out.println(getSmallestWindow(str, text));
        }
    }

    public static String getSmallestWindow(String longString, String pattern) {
        if (pattern.length() > longString.length()) {
            return "-1";
        }

        //left and right pointers to create sliding window
        int left = 0;
        int right = pattern.length();

        String minWindow = "-1";
        int minLen = Integer.MAX_VALUE;

        char[] chars = longString.toCharArray();
        while (right <= chars.length) {
            String substring = longString.substring(left, right);

            //if long string contain pattern, then increment left pointer until pattern is found to find minimum window string
            while (doesStringContainsPattern(substring, pattern)) {

                //keep track of minimum length of window and minimum window string found so far
                if (substring.length() < minLen) {
                    minLen = substring.length();
                    minWindow = substring;
                }
                left++;
                substring = longString.substring(left, right);
            }

            //increment right pointer
            right++;
        }

        return minWindow;
    }

    //to check whether long string contains the pattern, also check count of each character
    private static boolean doesStringContainsPattern(String str, String text) {
        Map<Character, Integer> strMap = getCharCountMap(str);
        Map<Character, Integer> textMap = getCharCountMap(text);

        Set<Character> set = textMap.keySet();

        for (Character ch : set) {
            if (!strMap.containsKey(ch) || strMap.get(ch) < textMap.get(ch)) {
                return false;
            }
        }

        return true;
    }

    //create a map of character counts in the string
    private static Map<Character, Integer> getCharCountMap(String str) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = str.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            if (map.containsKey(chars[i])) {
                map.put(chars[i], map.get(chars[i]) + 1);
            } else {
                map.put(chars[i], 1);
            }
        }

        return map;
    }

}

Zero Sum Subarrays

Problem Statement: Given an array of size N , print the total count of sub-arrays having their sum equal to 0

Reference URL: Zero Sum Subarrays

Example:

Input: 0 0 5 5 0 0 Output: 6

Input: 6 -1 -3 4 -2 2 4 6 -12 -7 Output: 4

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/zero-sum-subarrays/0
//Description: Given an array of size N , print the total count of sub-arrays having their sum equal to 0
public class ZeroSumSubArrays {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(zeroSumSubArrays(arr));
        }
    }

    public static int zeroSumSubArrays(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();

        int sum = 0;
        int zeroSumSubArraysCount = 0;

        //add a entry in map to handle zero sum
        map.put(0, 1);

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            //if the sum repeats then count all the subarrays between occurences of sum
            //for example if the sum s repeats once then count = 1, but if it repeats twice then count = 1+2 = 3
            //if it repeats thrice then count=1+2+3 = 6 (n * n+1)/2 where n is the number of occurence and that's what below logic does
            if (map.containsKey(sum)) {
                zeroSumSubArraysCount += map.get(sum);
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }

        }

        return zeroSumSubArraysCount;
    }
}

Longest consecutive sub-sequence

Problem Statement: Given an array of integers, find the length of the longest sub-sequence such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

Reference URL: Longest consecutive sub-sequence

Example:

Input: 2 6 1 9 4 5 3 Output: 6

Input: 1 9 3 10 4 20 2 Output: 4

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence/0
//Description: Given an array of integers, find the length of the longest sub-sequence
//such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

public class LongestConsecutiveSubSequence {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int testCases = scanner.nextInt();
        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(getLengthOfLongestConsecutiveSubSequence(arr));
        }
    }

    //Logic: is to add all array elements to map
    //Then iterate array, and for any element, increment by 1 and find in map, decrement by 1 and find in map
    //increment counter if found, and remove entry from hashmap if found
    //keep track of max count and return once all elements are iterated
    public static int getLengthOfLongestConsecutiveSubSequence(int[] arr) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int count = 0, maxCount = 0, key = 0;

        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], 1);
        }

        for (int i = 0; i < arr.length; i++) {
            key = arr[i];
            count = 1;
            map.remove(key);

            //keep on adding 1 to key and incrementing counter if found
            while (true) {
                ++key;
                if (map.containsKey(key)) {
                    count++;
                    map.remove(key);
                } else {
                    break;
                }
            }

            key = arr[i];
            //keep on subtracting 1 from key and incrementing counter if found
            while (true) {
                --key;
                if (map.containsKey(key)) {
                    count++;
                    map.remove(key);
                } else {
                    break;
                }
            }

            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}

Array Subset of another array

Problem Statement: Given two arrays: arr1[0..m-1] of size m and arr2[0..n-1] of size n. Task is to check whether arr2[] is a subset of arr1[] or not. Both the arrays can be both unsorted or sorted. It may be assumed that elements in both array are distinct.

Reference URL: Array Subset

Example:

Input: arr1: 11 1 13 21 3 7 arr2: 11 3 7 1 Output: Yes

Input: arr1: 10 5 2 23 19 arr2: 19 5 3 Output: No

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/array-subset-of-another-array/0
//Description: Given 2 array, check whether arr2[] is a subset of arr1[] or not
public class ArraySubset {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int arr1Length = scanner.nextInt();
            int arr2Length = scanner.nextInt();

            int[] arr1 = new int[arr1Length];
            int[] arr2 = new int[arr2Length];

            for (int j = 0; j < arr1Length; j++) {
                arr1[j] = scanner.nextInt();
            }
            for (int j = 0; j < arr2Length; j++) {
                arr2[j] = scanner.nextInt();
            }

            System.out.println(isSubset(arr1, arr2));
        }
    }

    //Logic: put first array arr1 in map. Then iterate arr2 and for each element check if it is present in map.
    //if even a single element is not present then return No, else Yes
    public static String isSubset(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr1.length; i++) {
            map.put(arr1[i], 1);
        }

        for (int i = 0; i < arr2.length; i++) {
            if (!map.containsKey(arr2[i])) {
                return "No";
            }
        }

        return "Yes";
    }
}