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...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Data Structures
  3. Arrays
  4. Sparse Arrays
  5. Discussions

Sparse Arrays

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

    You are viewing a single comment's thread. Return to all comments →

  • beefbong 2 years ago+ 1 comment

    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).

    0|
    ParentPermalink
    • raggzy 2 years ago+ 0 comments

      Imagine all strings in test have same hashCodes. String length <= 100. It's very easy to achieve. If author wanted, he could've made such a test. Every hash algorithm is vulnerable to that kind of test. And your O(N+Q) hashtable solution will degrade to O(N*Q).

      So when talking about "big O", which is upper bound, "hashtable" solution has same complexity, which is O(N*Q).

      Better and stable algorithm would be to use TreeMap with lexicographic comparator. Which would give you O(Q*logN).

      By the way, starging from Java8 they combined the "best of two worlds". HashMap class uses binary tree (if keys are "comparable") instead of linked list in case there are a lots of keys with same hashCode. So in java8 it would give you O(Q*logN) if using HashMap solution.

      1|
      ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature