Maximum Product Subarray

 Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

public class MaximumProductSubArray {

    public static void main(String[] args) {

        int[] arr = {-2,1,-4};

        int result = arr[0];

        int max = arr[0];

        int min = arr[0];

        for(int i=1;i<arr.length;i++){

          int  tempMax = Math.max(arr[i], Math.max(max*arr[i],min*arr[i]));

          min = Math.min(arr[i], Math.min(max*arr[i],min*arr[i]));

          max = tempMax;

          result = Math.max(result,max);

        }

        System.out.println(result);

    }

}

Result:8

Maximum Subarray

 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [ − 2,1, − 3,4, − 1,2,1, − 5,4], the contiguous subarray [4, − 1,2,1] has the largest sum =

6.

public class MaximumSumSubarray {

    public static void main(String[] args) {

        int[] arr = {4,3,-2,6,-14,7,-1,4,5,7,-10,2,9,-10,-5,-9,6,1};

        int maxSum =Integer.MIN_VALUE;

        int tempSum = 0;

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

            tempSum+=arr[i];

            if(tempSum<arr[i]){

                tempSum = arr[i];

            }

            maxSum = Math.max(maxSum,tempSum);

        }

        System.out.println(maxSum);

    }

}

Result: 23

Subarray Sum Equals K

 Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals to

k.

Example 1:

Input:nums = [1,1,1], k = 2 Output: 2

Note that empty array is not considered as a subarray.

public class CountSubarraySumEqualsK {

    public static void main(String[] args) {

        int arr[] = {3,9,-2,4,1,-7,2,6,-5,8,-3,-7,6,2,1};

        //int arr[] = {1,1,2};

        Map<Integer,Integer> map= new HashMap<>();

        int sum = 0;

        int count = 0;

        int k = 5;

       // int k =2;

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

            sum+=arr[i];

            if(sum==k){

                count++;

            }

            int diff = sum-k;

            if(map.containsKey(diff)){

                count = count + map.get(diff);

            }

            if(map.containsKey(sum)){

                map.put(sum,map.get(sum)+1);

            }else{

                map.put(sum,1);

            }

        }

        System.out.println(count);

    }

}

Result: 7

Maximum Size Subarray Sum Equals k

 Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t

one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1: Given nums = [1, -1, 5, -2, 3], k = 3, return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the

longest)

public class MaxSizeSubArraySumK {

    public static void main(String[] args) {

        int arr[] = {2,1,-1,3,5,2,-5,1,-3};

        int k = 3;

        int max = 0;

        int sum = 0;

        Map<Integer, Integer> map = new HashMap<>();

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

            sum+=arr[i];

            if(sum==k){

                max = Math.max(max,i);

            }

            int diff = sum-k;

            if(map.containsKey(diff)){

                max= Math.max(max,i-map.get(diff));

            }

            if(!map.containsKey(sum)){

                map.put(sum,i);

            }

        }

        System.out.println(max);

    }

result: 8

Group Shifted Strings

 

import java.util.*;

//https://www.youtube.com/watch?v=uEXJSRLqoKY&t=54s

public class GroupShiftedStrings {

    public static void main(String[] args) {

        String arr[] = {"abc","bcd","acef","xyz","az","ba","a","z","pqr","ace","jln"};

        List<List<String>> result = groupStrings(arr);

        System.out.println(result);

    }

    private static List<List<String>> groupStrings(String[] arr) {

        Map<String, List<String>> map = new HashMap<>();

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

            char[] charArr = arr[i].toCharArray();

            String key = "";

            if(charArr.length==1){

               key = "#";

            }else{

                for(int j=1; j<charArr.length;j++){

                    int diff  = (int)(charArr[j]-charArr[j-1]);

                    if(diff<0){

                        diff = diff+26;

                    }

                    key  = key + diff+"#";

                }

            }

            List<String> list = null;

            if(map.containsKey(key)){

               list = map.get(key);

            }else{

                list = new ArrayList<>();

            }

            list.add(arr[i]);

            map.put(key,list);

        }

        System.out.println(map);

        List< List<String>> result = new ArrayList<>();

        map.forEach((k,v)-> Collections.sort(v));

        result.addAll(map.values());

        return result;

    }

}

output:

{25#=[az, ba], 1#1#=[abc, bcd, xyz, pqr], 2#2#1#=[acef], #=[a, z], 2#2#=[ace, jln]}

[[az, ba], [abc, bcd, pqr, xyz], [acef], [a, z], [ace, jln]]

HIndex || Sorted Array

 //sorted arr

public class HIndex2 {

    public static void main(String[] args) {

        int[] arr  = {0,1,3,5,6};

        int start = 0;

        int end = arr.length-1;

        int n = arr.length;

        if(n==0){

            System.out.println(0);

            return;

        }

        if(n==1){

            if(arr[0]==0){

                System.out.println(0);

            }else{

                System.out.println(1);

            }

            return;

        }

        while (start<=end){

            int mid = start+(end-start)/2;

            if(arr[mid]==n-mid){

                System.out.println(n-mid);

               return;

            }else if(arr[mid]>n-mid){

                end = mid-1;

            }else{

                start = mid+1;

            }

        }

        System.out.println(n-start);

    }

}

HIndex

 

//https://www.youtube.com/watch?v=fVAR6SiATgI

public class HIndex {

    public static void main(String[] args) {

        //int arr[] = {3,1,2,3,2};//out put 2

        int arr[] = {3,6,7,8,9}; //output 4 //bucket {0,0,0,1,0,4}

        int bucket[] = new int[arr.length+1];

        int n = arr.length;

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

            if(arr[i]>=n){

                bucket[n]++;

            }else{

                bucket[arr[i]]++;

            }

        }

        int count = 0;

        for(int i= bucket.length-1;i>=0;i--){

            count = count+bucket[i];

            if(count>=i){

                System.out.println(i);

                break;

            }

        }

    }

}