0

I have two solutions to a leetcode problem (jewels and stones) in javascript. One solution is linear time complexity by my estimation, while the other is quadratic, and yet the latter has a slightly better runtime according to leetcode. Is that a common occurance?

problem: https://leetcode.com/problems/jewels-and-stones/

solution 1 (using a hash table)

var numJewelsInStones = function(jewels, stones) {
  let obj = {}
  const jewelsArr = jewels.split('')
  let count = 0
  jewelsArr.forEach((el, i) => {
      obj[el] ? obj[el]++ : obj[el] = 1   
  })
  const stonesArr = stones.split('')
  stonesArr.forEach((el, i) => {
    if (obj[el]) {
      count++
    } })
  return count
};

As far as I can tell this is linear time complexity because accessing an object key is said to be constant time complexity (Time complexity to check if a key exists in an object using "in" property)

solution 2 (using array methods)

var numJewelsInStones = function(J, S) {

  return S.split('').reduce((a, c) => a += Number(J.includes(c)), 0);
};

I believe the time complexity of this solution is quadratic because reduce is linear time complexity as well as includes

Runtime of solution 2 is 109ms, while runtime of solution 1 is 126ms

klondike
  • 383
  • 3
  • 13
  • 1
    The computation cost of arrays is relatively lower than objects. Because objects needs more resources allocated to save the key and the value, meanwhile array just need to save the values. – Dhana D. Aug 26 '21 at 04:20
  • 3
    If you take Memory usage out of the loop, and this is pure computation I would believe your object will outperform. I just think other operations like mem alloc is racing and taking more time, because your sizes here are small. Try with at least 50-100k entries and see the performance difference. – Iceman Aug 26 '21 at 04:31
  • 2
    The answer is straight-forwardly **no**. Complexity analysis is about *asymptotic behavior*. It says nothing about when your inputs are small, or even quite large - only about how your algorithm *scales*. This is a crucial point to understand. – juanpa.arrivillaga Aug 26 '21 at 05:57

0 Answers0