Can you please break down and explain these two lines ? I am really curious to know how you did it with just two lines of code !

Here's mine in Python.

import collections

values = collections.defaultdict(int)
for _ in range(int(input())):
    values[input()] += 1
for _ in range(int(input())):
    print(values[input()])

You can use an unordered_multiset (C++11) and its count method to make this easier:

#include <iostream>
#include <iterator>
#include <unordered_set>
using namespace std;

int main() {
    int n, q, i;
    string str;
    unordered_multiset<string> s;
    cin >> n;
    for (i = 0; i < n; ++i) {
        cin >> str;
        s.insert(str);
    }
    cin >> q;
    for (i = 0; i < q; ++i) {
        cin >> str;
        cout << s.count(str) << '\n';
    }
}

ArrayList<String> a = new ArrayList<String>();
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0; i < n; i++) {
            a.add(scan.next());
        }
        int q = scan.nextInt();
        for(int i = 0; i < q; i++) {
            int count = 0;
            String s = scan.next();
            for(String str : a) {
                if(str.equals(s))
                    count++;
            }
            System.out.println(count);
        }

LOL

Your solution is very inefficient.

Here I suggest you functional approach, better efficiency and readability.

Scanner sc = new Scanner(System.in);

Map<String, Long> counterMap = Stream.generate(sc::next)
    .limit(sc.nextInt())
    .collect(groupingBy(identity(), counting()));

Stream.generate(sc::next)
    .limit(sc.nextInt())
    .map(query -> counterMap.getOrDefault(query, 0L))
    .forEach(System.out::println);

P.S. imports are omitted.

The complexity of your algorithm is very big

My solution:

str_seq = [input() for s in range(int(input()))]
qry_seq = [input() for q in range(int(input()))]
print(*(sum(q == s for s in str_seq) for q in qry_seq), sep='\n')

I like my third line.

This is concise, but not performant. You are iterating through the entire array on every query: O(NQ) when O(N+Q) is possible with the same memory usage O(N).

Yeah, I have no idea what the intention was with the naming. The intro is also very clumsy...

Your solution runs in O(n*q). It is possible to do O(n+q). Here is a faster algorithm.

Create a HashMap<String,Integer>
for each string in the first set
    if the map contains the string increment the associated int
    else put it in the map associated with 1
for each string in the second set
    if the map contains the string print the associated int
    else print 0

I believe this also could be implemented in two lines of code, but that's not my style. I used 7, thought it easier to read.

Agreed. I don't see what this problem has to do with sparse arrays either. I implemented to simplest solution using an array and iterating thorugh it to get the counts (since it is in the array problem section), but obviously there are other solutions that are much more efficient such as leveraging a hash table/map, or even a trie if you want to save space. Eitherway, not a very challenging problem.

If you're going to use a Trainwreck, at least format it more like this:

Scanner in = new Scanner(System.in);
List<String> strings = IntStream.range(0,in.nextInt())
    .mapToObj(i -> in.next())
    .collect(Collectors.toList());
IntStream.range(0, in.nextInt())
    .mapToObj(i -> in.next())  // over here, you can comment individual functions where appropriate.
    .mapToLong(q -> strings.stream()
               .filter(q::equals)
               .count())
    .forEach(System.out::println);

The line count metric is such a poor one.

Looks good for bragging right, but am sure it's not efficient , a hashMap would be faster

And here's in kotlin:

return queries.flatMap { s -> listOf(strings.count { it==s }) }.toTypedArray()

JavaScript :)

const matchingStrings = (strings, queries) =>
    queries.map(el => strings.filter(item => item === el).length)

def matchingStrings(strings: Array[String], queries: Array[String]): Array[Int] = {
  val lookupTable = strings.groupBy(s => s)
  queries.foldLeft(Array[Int]())((acc, next) => {
    val matches = lookupTable.get(next).map(_.length).getOrElse(0)
    acc :+ matches
  })
}

Functional style also :D

hello coding lover,

I have uploaded a tutorial on this problem which can solve this problem in O(N+Q) time.

I hope this comment will help you to optimize your solution.

https://www.hackerrank.com/challenges/sparse-arrays/forum/comments/598644

jesus chris. if you write code like that in a company, do you think that will ever pass code review for production?

C++ solution :

vector<int> matchingStrings(vector<string> strings, vector<string> queries) {
    map<string, int> m;
    vector<int> v;
    for (string s:strings)  m[s]++;
    for (string q:queries) v.push_back(m[q]);
    return v;
}

def matchingStrings(strings, queries):

data = {e: strings.count(e) for e in strings}
result = [data[q] if q in data else 0 for q in queries]

return result

I have solved this using my code, which is using a Tree to find an ultra fast and efficient solution, based on pattern matching of an tree based algorithm, something that is industry proven and a standard to be fast and efficient to solving pattern matching problems.

I have seen all the codes in comments, manipulating main methods to get your answer. By avoiding the reading time of inputs into string arrays, saves you time, but that time saved isn't actually meant to be saved, that isn't the way these challenges are supposed to be answered. You are asked to implement it in a method after receiving the input arrays in the method code. YOU MUST IMPLEMENT IT IN THE METHOD. Otherwise your answers are just useless.

Mine in C++ using solution involving sorting, lower_bound, and upper_bound

std::vector<int> matchingStrings(
    std::vector<std::string> strings,
    const std::vector<std::string>& queries)
{
    std::sort(strings.begin(), strings.end());
    std::vector<int> result;
    result.reserve(queries.size());
    for (const auto& query : queries)
    {
        auto lower = std::lower_bound(strings.begin(), strings.end(), query);
        auto upper = std::upper_bound(strings.begin(), strings.end(), query);
        int diff = (lower == strings.end()) ? 0 : std::distance(lower, upper);
        result.push_back(diff);
    }
    return result;
}

Agree. not sure what this "medium" difficulty quesion is aiming at.

Shorter description: Given an array of strings FOO and a an array of strings BAR find the count of string in BAR that occurs in FOO.

C#. Linq is your friend.

var results = new int[queries.Length];

        var index = 0;

        foreach (string s in queries)
        {
             results[index++] = strings.Where(i => i == s).Count();
        }

        return results;

My thoughts indeed

It's a nice thought but I wish it had been approached like e.g. the Insertion Sort series, where the challenges steer you towards the correct solution rather than setting a problem with no reference to the subject except the title

Can you tell how to use sparse arrays for this problem?

speak for yourself. your arrogance is extremely demeaning. nobody cares how fast you solved it you coding monkey.

After some light research, it seems like SparseArrays are a memory lighter alternative to HashMaps in a subset of circumstances. However, HashMaps are faster and work for larger collections. I have no idea how to use SparseArrays, and since I already know how to use HashMaps, I also found the problem rather easy. I'm a little surprised the O(n^2) loop worked, but that's exactly the reason I came here (because at 1000x1000 it seemed feasible). This problem could use some improvement. Rather than re-classifying the difficulty, the problem statement and test cases should be improved to better illustrate the point, which may also raise the difficulty and block out the brute force method. Additionally, the problem statement would probably need to block the use of HashMaps, again, to illustrate the lesson on using SparseArrays.

hi,guy,I totally agree with you, i dont't think i learned anything about data structure or sparse arrays.

You deserve a medal. I had no problems with this either, but you could have just said "it had nothing to do with sparse arrays" without bragging. I think @ adfsdfadsf was a little pissed, and I don't name call but I kind of agree. Your ego is getting away with you and for newcomers, it can intimidate them. Maybe you're the class bully, or some affluent person, I don't know your circumstances, but you are not being helpful to learners with your comment. I don't think your comment was constructive. We're all trying to learn here, so maybe in future comments lose the bravado, and concentrate on substance. All comments here should be content related, not a forum to brag about how quickly you performed a task.

Well, I guess the idea was to search about Sparse Arrays (hence the title) and implement the challenge using it. Hashmaps are the obvious choice, even though Sparse Arrays will have the best compromise IMHO (storage space vs performance).

You still can go ahead and learn about sparse arrays and perhaps re-implement the solution in order to learn something out of this challenge :)

I think the goal was to teach us about sparse arrays but without sufficient memory or speed constraints we can freely decide to go with either a hash/dictionary or a sparse array.

For me the quickest solution with c++ was obviously using std::map. I'll try to implement it in sparse arrays and see what the differences are time and memory wise.

It's been changed to Medium. Still, it's the easiest Medium I've seen.

Can you do it using a hashmap in the same time complexity as a trie where I think that each query takes constant time to process as it has a max length of 20 char?

How the flag variable is able to output an array of integers when it is just a normal variable ?

This is exactly what I did. Bonus points if you used the unordered version since ordering isn't needed here.

What does it mean? Could you explain it in detail? What is a map in C++, how to implement it, what is being mapped and to what? Would be really helpful. Thanks :)

Yes and this approach is actually O(n) unlike some comments above who have achieved this in O(n^2)

This is really cool. I wouldn't have thought of using the iSNaN property.

Any way to do it in O(n) ?

Nice one!

The problem is reffering to sparse array. Prefix tree differs is totaly different structure. Main usage of the prefix tree (trie) is dymanic string matching, while space arrays are good for storing big sparse data in a compact form. Sparse array and matrixes are very common in leaner solvers.

Maybe merge the last 2 for loops into 1?

for _ in range(int(input())):
	print(N.count(input()))

With so many answers pertaining to HashMap and actually using SparseArray, I found yours being quite elegant solution. Also I don't understand how this problem is related to sparse map. If it was it should include couple of empty/null entries.

very nice implementation

What's the time complexity of "Collections.frequency"?