Sparse Array using HashMap

Question

Sparse Array

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. For example, given input strings=['ab','ab','abc'] and queries=['ab','abc','bc'] we find 2 instances of 'ab',1 of 'ab' and 0 of 'bc'. For each query, we add an element to our return array, result=[2,1,0] .

https://www.hackerrank.com/challenges/sparse-arrays/problem?isFullScreen=true

I tried this solution but it passes 3 test cases only.

static int[] matchingStrings(String[] strings, String[] queries) {
        int[] result_arr=new int[queries.length];
        HashMap<String,Integer> map=new HashMap<>();
        for(int i=0;i<queries.length;i++)
        {
            map.put(queries[i],i);
        }
        for(int i=0;i<strings.length;i++)
        {
            if(map.containsKey(strings[i]))
            {
                int index=map.get(strings[i]);
                System.out.println(index);
                result_arr[index]+=1;
            }
        }
        return result_arr;
    }

Use the following input to your algorithm: strings = {"ab", "ab", "abc"} and queries = {"ab", "ab"} — emil
– emil, Commented Apr 19, 2020 at 8:31
it outputs 2 and 0, but it has to be 2 and 2 I think @emil . thanks, got it. — mystica
– mystica, Commented Apr 19, 2020 at 8:36

user11935734 · Accepted Answer · 2020-04-19 08:35:21Z

1

It will break in case when your queries array has duplicate values.

So, instead of creating hashmap of queries array you should create it for strings array. This is because for each query , you need to check how many time that string is present in strings array. Currently in case of duplicate value in your queries array your hashmap itself does not get populated properly.

Here is the updated code :

static int[] matchingStrings(String[] strings, String[] queries) {
        int[] result_arr=new int[queries.length];
        HashMap<String,Integer> map=new HashMap<>();
        for(int i=0;i<strings.length;i++)
        {
            if(map.containsKey(strings[i])) {
                map.put(strings[i], map.get(strings[i])+1);
            } else {
                map.put(strings[i],1);
            }
        } 
        for(int i=0;i<queries.length;i++)
        {
            if(map.containsKey(queries[i]))
            {
                result_arr[i]+=map.get(queries[i]);
            }
        }
        return result_arr;

    }

answered Apr 19, 2020 at 8:35

user11935734

Sign up to request clarification or add additional context in comments.

1 Comment

Holger Over a year ago

Instead of

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

you can use for(String s: strings) map.merge(s,1, Integer::num);. And in the second loop, you can replace if(map.containsKey(queries[i])) { result_arr[i]+=map.get(queries[i]); } with the simpler result_arr[i]+=map.getOrDefault(queries[i], 0);

Collectives™ on Stack Overflow

Sparse Array using HashMap

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related