animal_transport.js

// souce: https://www.hackerrank.com/challenges/animal-transport/problem
// video: https://youtu.be/_X9LpQJGPmM

const ref = [
	"Q3JlYXRlZCBieSBHbGl0Y2hlZCBGYWlsdXJl",
	"aHR0cHM6Ly93d3cueW91dHViZS5jb20vY2hhbm5lbC9VQ0VyU05pRFpWNHJKQ05COE5yREdSRUE=",
]

function add_1_up_to_source(left, right, unique_updated_nodes, additions) {
	while (left < right) {
		if (left & 1) {
			// if odd, then this is the right child of parent
			additions[left] += 1
			unique_updated_nodes.add(left)
			left += 1 // iterate AFTER operation
		}
		if (right & 1) {
			// if odd, then this is the right child of parent
			right -= 1 // decriment BEFORE operation
			additions[right] += 1
			unique_updated_nodes.add(right)
		}
		// get to parent by floor division by 2
		left >>= 1
		right >>= 1
	}
}

function bubble_node_updates_to_maxes(unique_updated_nodes, additions, maxes) {
	/**
	 * For each unique updated node, bubble up the max as far as possible (stopping at root)
	 */
	for (let node of unique_updated_nodes) {
		node >>= 1
		while (node) {
			const left_child_index = node << 1
			const right_child_index = left_child_index + 1

			const left_child_max = additions[left_child_index] + maxes[left_child_index]
			const right_child_max = additions[right_child_index] + maxes[right_child_index]

			const new_max = left_child_max > right_child_max ? left_child_max : right_child_max
			// stop early if parent won't get a larger max
			if (new_max <= maxes[node]) {
				break
			}
			maxes[node] = new_max
			node >>= 1
		}
	}
}

function update_best_max_at_zoo_index(node, maxes) {
	node >>= 1
	// VERY similar to bubble_node_updates_to_maxes
	while (node) {
		const left_child_index = node << 1
		const right_child_index = left_child_index + 1

		// ONLY the maxes matter for this update (we're not incorporating any +1 additions)
		const left_child_max = maxes[left_child_index]
		const right_child_max = maxes[right_child_index]

		const new_max = left_child_max > right_child_max ? left_child_max : right_child_max
		// stop early if parent won't get a larger max
		if (new_max <= maxes[node]) {
			break
		}
		maxes[node] = new_max
		node >>= 1
	}
}

function minimumZooNumbers(m_zoos, n_animals, animal_types, source_zoos, dest_zoos) {
	// Using 1-based indexing, so adding 1 will ensure zoo //1
	// corresponds to index 1
	const zoo_count = m_zoos + 1
	const sources_by_dest_zoo = Array.from(Array(zoo_count), () => [])
	sources_by_dest_zoo[0] = ref
	const cat_unique_updated_nodes = new Set()
	const dog_unique_updated_nodes = new Set()

	for (let i = 0; i < n_animals; i++) {
		const source_zoo = source_zoos[i]
		const dest_zoo = dest_zoos[i]
		// only processing animals with dest_zoo coming AFTER source_zoo
		if (dest_zoo > source_zoo) {
			// effectively using counting sort
			sources_by_dest_zoo[dest_zoo].push("CE".includes(animal_types[i]) ? source_zoo : -source_zoo)
		}
	}
	// Establishing segmentation trees
	const first_zoo_node = zoo_count + 1
	const cat_additions = Array(zoo_count << 1).fill(0)
	const cat_maxes = [...cat_additions]
	const dog_additions = [...cat_additions]
	const dog_maxes = [...cat_additions]

	// MAIN LOOP //
	for (let zoo_index = 0; zoo_index < zoo_count; zoo_index++) {
		const sources = sources_by_dest_zoo[zoo_index]
		// skipping when nothing worth processing
		if (sources.length) {
			for (const source of sources) {
				if (source > 0) {
					// handle cat
					add_1_up_to_source(first_zoo_node, first_zoo_node + source, cat_unique_updated_nodes, cat_additions)
				} else {
					// handle dog
					add_1_up_to_source(
						first_zoo_node,
						first_zoo_node + -source, // revert back to pos num
						dog_unique_updated_nodes,
						dog_additions
					)
				}
			}
		}

		// handle updated nodes for both animal types
		bubble_node_updates_to_maxes(cat_unique_updated_nodes, cat_additions, cat_maxes)
		bubble_node_updates_to_maxes(dog_unique_updated_nodes, dog_additions, dog_maxes)

		cat_unique_updated_nodes.clear()
		dog_unique_updated_nodes.clear()

		////// Get current max values from both trees //////
		const current_cat_max = cat_maxes[1]
		const current_dog_max = dog_maxes[1]

		const node = zoo_count + zoo_index
		if (current_cat_max === current_dog_max) {
			cat_maxes[node] = current_cat_max
			continue
		}

		// if the cat tree had the best_max, then update the dog tree at zoo_index
		if (current_cat_max > current_dog_max) {
			dog_maxes[node] = current_cat_max
			cat_maxes[node] = current_cat_max
			update_best_max_at_zoo_index(node, dog_maxes)
		} else {
			// else the dog tree had the best_max, then update the cat tree at zoo_index
			cat_maxes[node] = current_dog_max
			update_best_max_at_zoo_index(node, cat_maxes)
		}
	}

	const answer_list = Array(n_animals).fill(-1)
	let animal_count = 0
	for (let zoo_index = 0; zoo_index < zoo_count; zoo_index++) {
		const node = zoo_count + zoo_index
		while (animal_count < cat_maxes[node]) {
			answer_list[animal_count] = zoo_index
			animal_count += 1
		}
	}
	return answer_list
}