Efficient random element from weighted array

random-weighted-element.js

//get a random weighted element in O(n) time and O(n) space
const randomWeightedElement = (elems, weightFn) => {
  if(!elems || !elems.length) return;
	const weighted = [];
	let sum = 0;
	for (let elem of elems) {
		const weight = weightFn(elem);
		if (weight > 0) {
			sum += weight;
			weighted.push({ elem, boundary: sum });
		}
	}
	const rand = random() * sum;
	for (let elem of weighted) {
		if (elem.boundary >= rand) {
			return elem.elem;
		}
	}
  //last element
	return elems[elems.length-1];
};

//depending on the nature of weightFn, could also do this in constant space without building the array by just looping twice
const randomWeightedElement2 = (elems, weightFn) => {
  if(!elems || !elems.length) return;
	let sum = 0;
	for (let elem of elems) {
		const weight = weightFn(elem);
		if (weight > 0) {
			sum += weight;
		}
	}
	const rand = random() * sum;
	sum = 0;
	for (let elem of elems) {
		const weight = weightFn(elem);
		if (weight > 0) {
			sum += weight;
		}
    if (sum >= rand) {
			return elem.elem;
		}
  }
  //last element
	return elems[elems.length-1];
};