#CodeChallenge Aparment hunting

AparmentHunting.cpp

#include <vector>
#include <unordered_map>

using namespace std;

int distanceBetwen(int a, int b) {
	return abs(a - b);
}

int getIndexOfMinValue(vector<int>& arr) {
	int minValue = INT_MAX;
	int minIndex =  -1;
	for (int i = 0; i < arr.size(); i++) {
		int numb = arr[i];
		if (minValue > numb) {
			minValue = numb;
			minIndex = i;
		}
	}
	return minIndex;
}

vector <int> getMinDistances(vector<unordered_map<string, bool>> blocks, string req) {
	vector<int> minDistances(blocks.size(), INT_MAX);
	// Get from left to right
	int closesReqIdx = INT_MAX;
	for (int i = 0; i < blocks.size(); i++) {
		// Save the history of the last element found
		if(blocks[i][req]) {
			closesReqIdx = i;
		}
		// The min  distance from left to right, left might be a invalid valie (MAX)
		minDistances[i] = min(minDistances[i], distanceBetwen(i, closesReqIdx));
	}
	// EXPERIMENTOS, NO ES ENCESARIO CORRERLO AL INICIO, I was right
	// Get from right to left
	int closesReqIdxRight = INT_MAX;
	for (int i = blocks.size() - 1; i >= 0; i--) {
		// Save the history of the last element found
		if(blocks[i][req]) {
			closesReqIdxRight = i;
		}
		// The min  distance from left to right, left might be a invalid valie (MAX)
		minDistances[i] = min(minDistances[i], distanceBetwen(i, closesReqIdxRight));
	}
	for (int x : minDistances) cout << x << endl;
	return minDistances;
}

vector<int> getTheMaxValueForEachIndex(int blocks, vector<vector<int>>& reqs) {
	vector<int> maxForBlock(blocks, INT_MIN);
	for (int b = 0; b < blocks; b++) {
		cout << "block " << b << endl;
		int maxValue = INT_MIN;
		for (int r = 0; r < reqs.size(); r++) {
			cout << reqs[r][b] << endl;
			maxValue = max(maxValue, reqs[r][b]);
		}
		cout << "max total= " << maxValue << endl;
		maxForBlock[b] = maxValue;
	}
	return maxForBlock;
}

// O(BR) time | (BR) space
int apartmentHunting(vector<unordered_map<string, bool>> blocks, vector<string> reqs) {
  vector<vector<int>> minDistancesFromBlocks;
	// Precompute distances
	for (string req : reqs) {
			cout << req << endl;
			minDistancesFromBlocks.push_back(getMinDistances(blocks, req));
	}
	// Pick the max from each precumputation
	vector<int> maxForEachBlock = getTheMaxValueForEachIndex(blocks.size(), minDistancesFromBlocks);
	int minIndex = getIndexOfMinValue(maxForEachBlock);
	return minIndex;
}

/** Naiv Solution O(B^2 R) time | (BR) space
int apartmentHunting(vector<unordered_map<string, bool>> blocks, vector<string> reqs) {
	vector<int> maxStepsTotal(blocks.size(), INT_MIN);
  // For each block.
	for (int b = 0; b < blocks.size(); b++) {
		// Check every request.
		for (string req : reqs) {
			// From corner to center == max to min.
			int closestDistanceForRequest = INT_MAX;
			// Look for req in every book.
			for (int b2 = 0; b2 < blocks.size(); b2++) {
				if (blocks[b2][req]) {
					// Because we go FROM corners to CENTERS
					closestDistanceForRequest = min(closestDistanceForRequest, distanceBetwen(b, b2));
				}
			}
			// Pick the MAX of all the closes distances.
			maxStepsTotal[b] = max(maxStepsTotal[b], closestDistanceForRequest);
		}
	}
  return getIndexOfMinValue(maxStepsTotal);
} */