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 1s, 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).

Minimize Total Manhattan Distance to a Store

Return the minimum total Manhattan distance from all demand cells to one chosen store cell.

Examples

Example 1

Input: ([[1,0,0],[0,0,1],[0,1,0]],)
Output: 4

Explanation: Median row/column.

Example 2

Input: ([[0,0]],)
Output: 0

Explanation: No demand.

Hints

1. Use deterministic tie-breaking for prompts with multiple valid outputs.
2. For design-style APIs, simulate operations with explicit inputs.

Earliest Best Shop Closing Time

Return the earliest closing time with minimum open/closed penalty.

Examples

Example 1

Input: ('YYNY',)
Output: 2

Explanation: Classic example.

Example 2

Input: ('NNN',)
Output: 0

Explanation: Close immediately.

Hints

1. Use deterministic tie-breaking for prompts with multiple valid outputs.
2. For design-style APIs, simulate operations with explicit inputs.