Question 1. Sparse Arrays

*There is a collection of Nstrings ( There can be multiple occurences of a particular string ). Each string's length is no more than

characters. There are also Q queries. For each query, you are given a string, and you need to find out how many times this string occurs in the given collection of N strings

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<String, Integer> map = new HashMap<String, Integer>();

        while(n>0){
            String str = sc.next();
            if(!map.containsKey(str)){
                map.put(str, 1);
            }else{
                map.put(str, map.get(str)+1);
            }
            n--;
        }
        int t = sc.nextInt();

        while(t>0){
            String str = sc.next();
            System.out.println(map.get(str) == null ? 0 : map.get(str));
            t--;
        }
        sc.close();
    }
}

Question 2. Array Manipulation - Get difference between each elements

URL : https://www.hackerrank.com/challenges/crush

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        long[] arr = new long[n];

        for(int a0 =  0; a0 < m; a0++){
            int start = in.nextInt();
            int end = in.nextInt() ;
            int value = in.nextInt();

            arr[start-1] += value;
            if(end < n) arr[end] -= value;

        }
        long temp = 0;
        long max = 0;
        for(long l : arr){
            temp += l;
            max = temp < max ? max : temp;
        }
        System.out.println(max);
        in.close();
    }
}

• solution :
  • S1 : use inner for loop and store sum on each element by each iteration.
    • This solution may take O(m*n) time complexity.
  • S2 : Not store real value of each element, but store differences between element N and N+1.
    • This solution may take O(m + n) time complexity.
    • You can get max value by searching array arr. Not add all posivite values, but add if difference is more than last difference.