Buildings

#include <bits/stdc++.h>
using namespace std;

int apartmentHunting(vector<unordered_map<string, bool>> blocks, vector<string> reqs){
    if(blocks.empty()) return -1;

    vector<pair<unordered_map<string, int>, int>> distance(blocks.size());


    // distance[i].first[building] returns minimum distance of building from block[i]
    // distance[i].second returns the maximum distance among all building from block[i]
    // we have to return the i which has minimum distance[i].second

    unordered_map<string, int> aboveMaxIndex;

    for(int i=0; i<blocks.size(); i++){
        for(auto &x: reqs){
            if(blocks[i][x]){
                distance[i].first[x] = 0;
            }
            else if(aboveMaxIndex.count(x)){
                distance[i].first[x] = i-aboveMaxIndex[x];
            }
        }

        // aboveMinIndex[building] contains the maximum index < i at which contains the building
        for(auto it=blocks[i].begin(); it!=blocks[i].end(); it++){
            if(it->second){
                //i.e current block has building it->first
                aboveMaxIndex[it->first] = i;
            }
        }

    }

    unordered_map<string, int> bottomMinIndex;
    for(int i=blocks.size()-1; i>=0; i--){

        for(auto &x: reqs){
            if(bottomMinIndex.count(x)){
                if(distance[i].first.count(x)){
                    distance[i].first[x] = min(distance[i].first[x], bottomMinIndex[x]-i);
                }
                else{
                    distance[i].first[x] = bottomMinIndex[x]-i;
                }
            }
        }

        // bottomMinIndex[building] contains the minimum index > i at which contains the building
        for(auto it=blocks[i].begin(); it!=blocks[i].end(); it++){
            if(it->second){
                //i.e current block has building it->first
                bottomMinIndex[it->first] = i;
            }
        }
    }

    if(distance[0].first.size() < reqs.size()){
        //i.e there is atleast one requirement present in none of the buildings
        cout << distance[0].first.size() << endl;
        return -1;
    }

    for(int i=0; i<distance.size(); i++){
        int farthestDistance = 0;
        for(auto it=distance[i].first.begin(); it!=distance[i].first.end(); it++){
            farthestDistance = max(farthestDistance, it->second);
        }
        distance[i].second = farthestDistance;
    }

    int answer = -1;
    int minFarthestDistance = INT_MAX;
    for(int i=0; i<distance.size(); i++){
        if(distance[i].second < minFarthestDistance){
            minFarthestDistance = distance[i].second;
            answer = i;
        }
    }

    return answer;
}

int main(){
    vector<unordered_map<string, bool>> blocks(5);
    blocks[0]["gym"] = false;
    blocks[0]["school"] = true;
    blocks[0]["store"] = false;

    blocks[1]["gym"] = true;
    blocks[1]["school"] = false;
    blocks[1]["store"] = false;

    blocks[2]["gym"] = true;
    blocks[2]["school"] = true;
    blocks[2]["store"] = false;

    blocks[3]["gym"] = false;
    blocks[3]["school"] = true;
    blocks[3]["store"] = false;

    blocks[4]["gym"] = false;
    blocks[4]["school"] = true;
    blocks[4]["store"] = true;

    vector<string> reqs = {"gym", "school", "store"};
    cout << apartmentHunting(blocks, reqs) << endl;

}