What long code I have to write today to get my solution accepted. Ohh God!! But I did it.
class Solution {
public:
int binarySearch(vector<int>& costs, int budget, int start, int end) {
int ans = -1;
while (start <= end) {
int mid = end - (end - start) / 2;
if (costs[mid] <= budget) {
ans = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return ans;
}
int maxCapacity(vector<int>& costs, vector<int>& capacity, int budget) {
// sort the cost aligned with capacity
// build the prefix array for capacity corresponding to costs.
int n = costs.size();
vector<pair<int, int>> costCapacity;
for (int i = 0; i < n; i++) {
costCapacity.push_back({costs[i], capacity[i]});
}
sort(costCapacity.begin(), costCapacity.end());
// fill the values again to costs and capacity
for (int i = 0; i < n; i++) {
costs[i] = costCapacity[i].first;
capacity[i] = costCapacity[i].second;
}
vector<int> prefixCapacity(n, 0);
for (int i = 0; i < n; i++) {
if (i == 0) {
prefixCapacity[i] = capacity[0];
} else {
prefixCapacity[i] = max(prefixCapacity[i - 1], capacity[i]);
}
}
int maxCapacityForSingleMachine = 0;
// if we are choosing only one machine then the answer will be
// the highest capacity in bound to budget
for (int i = 0; i < n; i++) {
if (costs[i] < budget) {
maxCapacityForSingleMachine = max(maxCapacityForSingleMachine, capacity[i]);
}
}
int maxCapacityForTwoMachines = 0;
// if we are choosing two machines then we will fix one machine and
// find the best capacity for other machine with remaining budget with the help of Binary Search.
for (int i = 0; i < n; i++) {
if (costs[i] >= budget) {
break;
}
int limit = budget - costs[i] - 1;
int j = binarySearch(costs, limit, 0, i - 1);
if (j >= 0) {
maxCapacityForTwoMachines = max(maxCapacityForTwoMachines, prefixCapacity[j] + capacity[i]);
}
}
return max(maxCapacityForTwoMachines, maxCapacityForSingleMachine);
}
};From past few day geting square question only, it want only the largest square. Can't you think of something else engineers.
class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
int magicSize = 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> rowsPrefixSum(m, vector<int>(n,0));
vector<vector<int>> colsPrefixSum(m, vector<int>(n,0));
// caculate row prefix sum matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) {
rowsPrefixSum[i][j] = grid[i][j];
continue;
}
rowsPrefixSum[i][j] = rowsPrefixSum[i][j - 1] + grid[i][j];
}
}
// calculate col prefix sum matrix
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
if (i == 0) {
colsPrefixSum[i][j] = grid[i][j];
continue;
}
colsPrefixSum[i][j] = colsPrefixSum[i - 1][j] + grid[i][j];
}
}
// so now take squares size from 1 to min(m, n)
for (int k = 1; k <= min(m, n); k++) {
// traverse the grid and the point at which we are currently will be considered the left-top point of the k size square
// also validate that this size square can exist by finding the bottom-right coordinate and checking if this point lie in the grid.
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// i and j are the left top
int p = i + k - 1;
int q = j + k - 1;
if (!(p < m && q < n)) {
break;
}
// now square is there in the grid
// check if it is magic.
// create the set and push the rows, cols, diagonals sum
// if the size is still one then consider for max.
// whenever the size become more than 1 break, this cann't be magic square
unordered_set<int> st;
int invalidSquare = false;
// putting the rows sum in the set
int rowSum = 0;
for (int row = i; row <= p; row++) {
int toRemove = 0;
if (j - 1 >= 0) {
toRemove = rowsPrefixSum[row][j - 1];
}
rowSum = rowsPrefixSum[row][q] - toRemove;
st.insert(rowSum);
if (st.size() > 1) {
invalidSquare = true;
break;
}
}
if (invalidSquare) {
continue;
}
for (int col = j; col <= q; col++) {
int toRemove = 0;
if (i - 1 >= 0) {
toRemove = colsPrefixSum[i - 1][col];
}
int colSum = colsPrefixSum[p][col] - toRemove;
st.insert(colSum);
if (st.size() > 1) {
invalidSquare = true;
break;
}
}
if (invalidSquare) {
continue;
}
int diagonal1Sum = 0;
for (int row = i, col = j; row <= p && col <= q; row++, col++) {
diagonal1Sum += grid[row][col];
}
int diagonal2Sum = 0;
for (int row = i, col = q; row <= p && col >= j; row++, col--) {
diagonal2Sum += grid[row][col];
}
st.insert(diagonal1Sum);
st.insert(diagonal2Sum);
if (st.size() == 1) {
magicSize = max(magicSize, k);
}
}
}
}
return magicSize;
}
};class AuctionSystem {
public:
// itemId -> {userId, bidAmount}
unordered_map<int, map<int, int, greater<int>>> auctionDS;
// itemId -> {bidAmount, userId}
unordered_map<int, set<pair<int, int>, greater<pair<int, int>>>> auctionDS2; // this is used for effectivity of highest bidder.
AuctionSystem() {
}
void addBid(int userId, int itemId, int bidAmount) {
// do we have item with this itemId
auto itemIt = auctionDS.find(itemId);
auto itemIt2 = auctionDS2.find(itemId); // if itemIt will be there then itemIt2 will also be there so don't check in if condition
if (itemIt != auctionDS.end()) {
// now check if the same user already present for this itemId.
auto userIt = itemIt->second.find(userId);
if (userIt != itemIt->second.end()) {
// only update the bid amound user already exist with this item
// before updating serach this pair in auctionDS2 and then update.
auto bidAmountIt = itemIt2->second.find({auctionDS[itemId][userId], userIt->first});
itemIt2->second.erase(bidAmountIt);
itemIt2->second.insert({bidAmount, userId});
auctionDS[itemId][userId] = bidAmount;
return;
} else {
// add new item in with its' bid amount
auctionDS[itemId].insert({userId, bidAmount});
// also add in the auctionDS2
auctionDS2[itemId].insert({bidAmount, userId});
return;
}
}
// otherwise add the bid in Auction
map<int, int, greater<int>> mp;
mp.insert({userId, bidAmount});
auctionDS[itemId] = mp;
// add in auctionDS2
set<pair<int, int>, greater<pair<int,int>>> st;
st.insert({bidAmount, userId});
auctionDS2[itemId] = st;
return;
}
void updateBid(int userId, int itemId, int newAmount) {
auto itemIt = auctionDS.find(itemId);
int oldAmount = itemIt->second[userId];
itemIt->second[userId] = newAmount;
// update in auctionDS2
auto itemIt2 = auctionDS2.find(itemId);
auto bidAmountIt = itemIt2->second.find({oldAmount, userId});
itemIt2->second.erase(bidAmountIt);
itemIt2->second.insert({newAmount, userId});
return;
}
void removeBid(int userId, int itemId) {
auto itemIt = auctionDS.find(itemId);
auto userIt = itemIt->second.find(userId);
int bidAmount = userIt->second;
itemIt->second.erase(userIt);
if (auctionDS[itemId].size() == 0) {
auctionDS.erase(itemIt);
}
// remove from auctionDS2
auto itemIt2 = auctionDS2.find(itemId);
itemIt2->second.erase({bidAmount, userId});
if (auctionDS2[itemId].size() == 0) {
auctionDS2.erase(itemIt2);
}
return;
}
int getHighestBidder(int itemId) {
auto itemIt2 = auctionDS2.find(itemId);
if (itemIt2 == auctionDS2.end()) {
return -1;
}
return itemIt2->second.begin()->second;
}
};
/**
* Your AuctionSystem object will be instantiated and called as such:
* AuctionSystem* obj = new AuctionSystem();
* obj->addBid(userId,itemId,bidAmount);
* obj->updateBid(userId,itemId,newAmount);
* obj->removeBid(userId,itemId);
* int param_4 = obj->getHighestBidder(itemId);
*/