Frequency Queries

  • + 7 comments

    JavaScript solution (passes all tests):

    const func = arr => {
      const result = [];
      const hash = {};
      const freq = [];
    
      for (let i = 0; i < arr.length; i += 1) {
        const [action, value] = arr[i];
        const initValue = hash[value] || 0;
    
        if (action === 1) {
          hash[value] = initValue + 1;
    
          freq[initValue] = (freq[initValue] || 0) - 1;
          freq[initValue + 1] = (freq[initValue + 1] || 0) + 1;
        }
    
        if (action === 2 && initValue > 0) {
          hash[value] = initValue - 1;
    
          freq[initValue - 1] += 1;
          freq[initValue] -= 1;
        }
    
        if (action === 3) result.push(freq[value] > 0 ? 1 : 0);
      }
    
      return result;
    };
    

    The idea is that we count 3 things: 1. Creating a dictionary with all added/removed values as keys and number of elements as values 2. Updating a frequency table 3. Result that we return in the end

    Obvious solution would be to keep only the dictionary. However, then in case 3 every time we need to traverse the whole dictionary to check if there is a key with value that equals the search value;

    It works fine on the initial tests but fails on the main set of tests because traversal of the whole dictionary is expensive.

    OK, then we need to keep an extra list of frequencies. I used a simple array where the index is the number of occurencies, for example [0,2,3] means that there are 2 values which occur twice and 3 values that occur 3 times (dictionary in this case would be something like: {12: 2, 14: 3}

    This way in case 3 I need only to check freq[number of occurencies]