Minimize total distance to a store

Question 1: Choose a CVS location to minimize total distance

You are given an M x N grid grid containing only 0 and 1.

• grid[r][c] = 1 means there is demand at cell (r, c) (e.g., a customer/home).
• grid[r][c] = 0 means no demand.
• You may place one CVS store on any cell (including on a 1 cell).
• Distance is Manhattan distance :

$d((r_1,c_1),(r_2,c_2)) = |r_1-r_2| + |c_1-c_2|$

Goal: Choose the store location that minimizes the total distance from every demand cell (1) to the store.

Input

• grid : M x N matrix of 0/1.

Output

• Return the minimum possible total distance .

Notes

• If there are no 1 s, the minimum total distance is 0 .
• Be prepared to discuss a brute-force approach vs. an optimal approach.

Question 2: Pick the best shop closing time

You are given a string customers of length n consisting only of 'Y' and 'N'.

• customers[i] = 'Y' means at hour i at least one customer arrives.
• customers[i] = 'N' means no customers arrive at hour i .

A shop chooses a closing time t where t is an integer in [0, n]:

• The shop is open during hours [0, t-1] .
• The shop is closed during hours [t, n-1] .

The penalty is:

• +1 for every hour the shop is open and customers[i] = 'N' (wasted open hour)
• +1 for every hour the shop is closed and customers[i] = 'Y' (missed customer hour)

Task: Return the earliest closing time t that achieves the minimum penalty.

Input

• customers : string of 'Y' / 'N'

Output

• Integer t (earliest minimizer).