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.
  1. Frequency Queries
  2. Discussions

Frequency Queries

  • ivanduka + 5 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]

    • hristod + 2 comments

      I have almost the same code as you, but I have a few tests failing, all in the test cases with 100000 operations :( If I pastge your code directly, it works. I've optimised my code to be as close as yours, just to try and see what happens, and it doesn't work. Can you see any difference?

      function freqQuery(queries) {
    let result = [];
    let freq = [];
    let map = {};

    for (let i = 0; i < queries.length; i++) {
        const [op, x] = queries[i];
        const f = map[x] || 0;

        if (op === 1) {
            map[x] = f + 1;
            freq[f] = (freq[f] || 0) - 1;
            freq[f+1] = (freq[f+1] || 0) + 1;
        }
        if (op === 2) {
            map[x] = f - 1;
            freq[f-1] += 1;
            freq[f] -= 1;
        }
        if (op === 3) {
            result.push(freq[x] > 0 ? 1 : 0);
        }
    }

    return result;
}
      • nitishchandel13 + 1 comment

        I have only put 1 condition in second case for if map[x] > 0 then execute the code.

        let result = [];
let freq = [];
let map = {};

for (let i = 0; i < queries.length; i++) {
    const [op, x] = queries[i];
    const f = map[x] || 0;

    if (op === 1) {
        map[x] = f + 1;
        freq[f] = (freq[f] || 0) - 1;
        freq[f + 1] = (freq[f + 1] || 0) + 1;
    }
    if (op === 2) {
        if (map[x] > 0) { 
            map[x] = f - 1;
            freq[f - 1] += 1;
            freq[f] -= 1;
        }
    }
    if (op === 3) {
        result.push(freq[x] > 0 ? 1 : 0);
    }
}
return result;
      • cchan1613 + 0 comments

        Learned something that I never used before: javascript engine can increase the size of an array with previous value intialized to undefined. Also the speed of accessing an array element using index, is way faster than the properties of an object. Thank you, ivanduka!

    • kinghuthman + 0 comments

      you're appreciated

    • jj_erlich155 + 1 comment

      It doesn't pass all test cases. Just ran it and got the same errors as with my code. It doesn't pass 7 through 13.

      • lxl6996 + 0 comments

        My solution is slightly more verbose but does more or less the same thing but also doesn't pass 7 - 13.

        // Complete the freqQuery function below.
function freqQuery(queries) {
    let hashMap = {};
    let freqMap = [];
    let results = [];

    for(let q in queries) {
        let action = queries[q][0];
        let actionValue = queries[q][1];
        let oldValue = hashMap[actionValue] || 0

        if(action === 1) {
            hashMap[actionValue] = oldValue + 1;
            setFreqMapValue(oldValue, hashMap[actionValue], freqMap);
        } else if(action === 2) {
            hashMap[actionValue] = oldValue - 1
            setFreqMapValue(oldValue, hashMap[actionValue], freqMap);
        } else if (action === 3) {
            results.push(freqMap[actionValue] > 0 ? 1 : 0);
        }
    }

    return results;

}

function setFreqMapValue(oldValue, newValue, freqMap) {
    let oldFreq = freqMap[oldValue] || 0;
    let newFreq = freqMap[newValue] || 0;
    if(oldFreq > 0) {
        freqMap[oldValue] -= 1;
    }
    freqMap[newValue] = newFreq +1;
}
    • mc002 + 0 comments
      [deleted]
    • mc002 + 0 comments

      Nice solution! I used a similar approach, only more messy. I kept a separate array for values and updated that arary based on a query.

      Passed all tests though.

      function freqQuery(queries) {
	const result = [];
	const dict = {};
	const values = [];
	queries.forEach((queryArr) => {
		if (queryArr[0] === 1) {
			const index = values.indexOf(dict[queryArr[1]]);
			if (index > -1) values.splice(index, 1);
			dict[queryArr[1]] = (dict[queryArr[1]] || 0) + 1;
			values.push(dict[queryArr[1]]);
		} else if (queryArr[0] === 2) {
			if (dict[queryArr[1]]) {
				const index = values.indexOf(dict[queryArr[1]]);
				dict[queryArr[1]] > 1 ? --dict[queryArr[1]] : delete dict[queryArr[1]];
				if (dict[queryArr[1]]) {
					values.splice(index, 1, dict[queryArr[1]]);
				} else {
					values.splice(index, 1);
				}
			}
		} else if (queryArr[0] === 3) {
			if (values.includes(queryArr[1])) {
				result.push(1);
			} else {
				result.push(0);
			}
		}
	});
	return result;
}