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

  • wryan42675 + 1 comment

    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.

    • raggzy + 0 comments

      Best you can do with map-based is O((n+q)*logN). Think about HashMap performance when all strings have same hashcodes, your solution is O(n*q) as well. Only in java8 they introduced "treemap inside hashmap" for equi-hash comparable objects.

      Here is reference to a 3-liner for hashmap solution in java8, maybe you'll like it https://www.hackerrank.com/challenges/sparse-arrays/forum/comments/304466