We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Arrays
  4. Sparse Arrays
  5. Discussions

Sparse Arrays

  • porglezomp + 12 comments

    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()])
    • polmki99 + 4 comments

      Python brofist! Here's my python.

      from collections import defaultdict

words = defaultdict(lambda: 0)

for _ in range(int(input().strip())):
    words[input().strip()] += 1
    
for _ in range(int(input().strip())):
    print(words[input().strip()])
      • Xarmanla + 0 comments

        Even python women wrote similar code. Now I will relearn sparse arrays.

      • hgnisrednivrug + 0 comments
        [deleted]
      • a2_darwazeh + 1 comment

        Wow i really went the hard route ay, forgot about dictionaries.

        import re

no_strings = int(input())
strings = []
no_q = 0
queries = []

for _ in range(no_strings):
    strings.append(input())

no_q = int(input())
for _ in range(no_q):
    queries.append(re.compile(r'^'+input()+'$'))

for pattern in queries:
    found = 0
    for s in strings:
        found += len(pattern.findall(s))
    print(found)
        • mounikavas + 0 comments

          Can you please explain your code

      • Arviy + 1 comment

        this will not work if you have queries with same element, as there was in test cases!

        • kakadiyaraj1999 + 0 comments

          it passes all the test cases :)

    • CleverChuk + 0 comments

      Can you explain your code please

    • pdog1111 + 2 comments

      Counter makes it even easier

      from collections import Counter, defaultdict

counter = defaultdict(int, Counter([raw_input() for _ in range(input())]))

for _ in range(input()):
    print counter[raw_input()]
      • DanHaggard + 2 comments

        I haven't checked in python2 - but in 3 you don't need defaultdict if you use Counter.

        from collections import Counter, defaultdict

cnt = Counter([input().strip() for _ in range(int(input().strip()))]) 

for _ in range(int(input().strip())):
    print(cnt[input().strip()])
        • PapaThor + 1 comment

          Condensed down to 2 statements (plus the import):

          from collections import Counter

d = Counter([input().strip() for _ in range(int(input()))])
print(*[d[input().strip()] for _ in range(int(input()))], sep='\n')
          • chucklesoclock + 0 comments

            Lovely!

        • tusharkailash29 + 1 comment

          I am new to python and I had difficulty understanding the code. Why are two same two for-loops needed? And how does this statement get us the solution : print(cnt[input().strip()]) ? Thanks.

          • CaptnCrunchCode + 0 comments

            @tusharkailash29 ... or anyone else currently wondering.

            We are comparing two variable input ranges in this question, and the ranges may vary in length. The "for loops" are used to organize the inputs as "S" strings followed by "Q" queries.

            cnt = Counter([input().strip() for _ in range(int(input()))])

            The Counter() function creates a dictionary (key,value) pairs. The "S" string inputs are the keys, and their occurences (a.k.a counts) are the value. For every duplicate key that appears in this loop, it's value (count) increases by one.

            for _ in range(int(input().strip())): print(cnt[input().strip()])

            In the second & third lines, "Q" query inputs are the keys we search in the "cnt" dictionary. Think of "input().strip()" in print(cnt[input().strip()]) as the key in (key,value) pair. Searching by cnt[key] provides the dictionary value associated with it. The second "for loop" repeats the cnt[key] search step for the remaining "Q" query inputs.

      • philippkipp + 3 comments

        Python 3: You don't really need to import anything additionally:

        result = [] for q in queries: result.append(strings.count(q)) return result

        I don't know how to put a codeblock into the comments

        • kakadiyaraj1999 + 0 comments

          Same! :)

        • Tej_Pratap_Singh + 1 comment

          Wow, this is amazing

          • qh5ny8wni40i + 1 comment

            Or you could just condense it to:

              return [strings.count(q) for q in queries]
            • syedasjadsyed + 0 comments

              Nice! That list comprehension is much more readable than the map I ended up with:

              return map(lambda query: strings.count(query), queries)

              Edit: but a lot of these one-liners could really benefit from using better data structures

        • sanjaybisht8999 + 0 comments

          You can by typing three times ` key

          `

    • rishabh_ags + 2 comments

      Here's mine :)

      N = int(input())
strArray = []
for _ in range(N):
    strArray.append(input().strip())
Q = int(input())
for _ in range(Q):
    query = input()
    print(strArray.count(query)) #count how many times query occured in strArray
      • szimmer1 + 0 comments

        Much worse than hashmap-based solutions because you do linear search, so O(NQ). Hashmap-based solution is constant time complexity for queries, so O(N).

      • pratik_nalage + 1 comment

        What is the use of underscore in for loop?

        • kikirki + 0 comments

          It is the way you name variable which will not be used, so it is in accordance with PEP8 style guide.

    • kevyn_liang + 1 comment

      Python with no external libraries.

      lst = []
for i in range(int(input())):
    lst.append(input())
for i in range(int(input())):
    query_string = input()
    count = 0
    for i in range(len(lst)):
        if query_string == lst[i]:
            count += 1
    print(count)
      • hbruno + 1 comment

        Here's mine 

        s = [input() for _ in range(int(input()))] 
for _ in range(int(input())):
    print(s.count(input()))
        • appu_b + 0 comments
          s1 = [input().strip() for _ in range(int(input()))]
[print(s1.count(input().strip())) for _ in range(int(input()))]
    • pratik_nalage + 0 comments

      Can you elobrate the code.

    • reasonet + 0 comments

      That is nearly identical to my solution. Python is pretty great.

    • eloyekunle + 0 comments

      Here's mine:

      from collections import Counter

def matchingStrings(strings, queries):
    occurs = Counter(strings)
    return [occurs[query] for query in queries]
    • Maximus12793 + 0 comments

      I notice alot of these solutions process 2x. an easy way is to just use Counter and collect values that have keys in the counter.

      ex: (Psuedo)

      result = [] c = Counter(strings)

      for q in queries: c[q] ? result.append(c[q]) : result.append(0)

    • Ghostxzxz + 0 comments

      Here's mine in Python 3.6

      def matchingStrings(strings, queries):
    d = {}
    l = []
    for i in strings:
        d[i] = d.get(i,0) + 1
    for i in queries:
        l.append(d.get(i,0))
    return l
    • ruc_hitman + 0 comments
      [deleted]
    • Himan10 + 0 comments

      Hey .. Here's my python code to sove that problem .. but i don't think it's best for large inputs 

      count_occurance = []
for i in queries:           # O(n)
    if i in strings:        # O(n)
        count_occurance.append(strings.count(i))    # O(1)
    else:
        count_occurance.append(0)